Module nsga2 

NSGA-II, the non-dominated sorting genetic algorithm II: a search for the designs that trade two or more goals off against each other, the Pareto front.

A design dominates another when it is no worse in any goal and better in at least one. The designs no other design dominates are the Pareto front: along it, one goal can only be improved by giving up another. NSGA-II keeps a population of designs, breeds a new generation from them, and keeps the best half of parents and children together. They are ranked first by how many fronts deep they lie, then, within a front, by how far they are from their neighbours, so the front it finds spreads along the true one instead of bunching at one place.

The method is K. Deb, A. Pratap, S. Agarwal and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II”, IEEE Transactions on Evolutionary Computation 6(2), 182–197 (2002), https://doi.org/10.1109/4235.996017:

• Fast non-dominated sorting (§III-A, p. 184): each design’s count of designs dominating it, and the set it dominates; the designs with a count of zero are the first front, and removing them gives the next. Rank 0 here is the paper’s front 1.
• Crowding distance (§III-B, p. 185): in each front and for each goal, the designs sorted by that goal; the two ends get an infinite distance, and every other design adds the gap between its two neighbours’ values divided by the goal’s range in the front, (f_m(i+1) − f_m(i−1)) / (f_m^max − f_m^min).
• Crowded comparison (p. 185): a lower rank wins; in one rank, the larger distance wins.
• The main loop (§III-C, p. 186): parents and children together, 2N designs, are sorted into fronts; whole fronts fill the next N in rank order, and the front that doesn’t fit is cut by crowding distance, largest first.
• Constraints (§VI, p. 192): design i constrained-dominates j if i keeps every constraint and j doesn’t, if neither does and i’s overall violation is smaller, or if both do and i dominates j.

Children come from parents chosen by binary tournaments with the crowded comparison, two at a time, by the paper’s real-coded operators (§IV, p. 187):

• Simulated binary crossover (SBX; K. Deb and R. B. Agrawal, “Simulated binary crossover for continuous search space”, Complex Systems 9(2), 115–148 (1995)): a child’s spread factor β = |c₂ − c₁| / |x₂ − x₁| has density ½(η_c + 1) β^η_c for β ≤ 1 and ½(η_c + 1) / β^(η_c+2) above (eqs. 19–20, pp. 125–126). Each variable of a crossing pair is crossed with probability ½ (K. Deb and H.-G. Beyer, “Self-adaptive genetic algorithms with simulated binary crossover”, report CI-61/99, Univ. Dortmund (1999), p. 8), and the two children’s values swap with probability ½.
• Polynomial mutation (K. Deb and M. Goyal, “A combined genetic adaptive search (GeneAS) for engineering design”, Computer Science and Informatics 26(4), 30–45 (1996)).

Both are cut at the variable’s bounds, so no child is placed outside and none piles up on the bound. SBX drops the density beyond the bound and scales the rest up to a whole, as Deb and Agrawal propose (p. 143). Mutation cuts each side of the value at its own bound and keeps half the probability on each side. The equations of both cuts, given with each function below, are those of Deb’s NSGA-II code as pymoo 0.6.2 (Apache-2.0) prints them, in its operators/crossover/sbx.py and operators/mutation/pm.py; no paper we could reach prints them, so each is derived again in its function’s comment.

The defaults are the paper’s real-coded settings (p. 187): crossover probability 0.9, mutation probability 1/n per variable, distribution indices η_c = η_m = 20; the population of 100 and 250 generations are its runs on the ZDT problems (p. 187).

Variables

NSGA-II draws its first population uniformly between each variable’s bounds, so every variable needs two finite bounds (Variable::within); its start and step are not used. Integer variables are not taken yet.

Reproducibility

A generation’s random numbers come from one stream keyed by the seed and the generation’s number (SeededRng::for_stream), and are drawn before its children are evaluated, so a run is bit for bit the same every time on one platform, however its children are evaluated. Ties in a sort keep the designs’ order, parents before children.

Structs

Front

What a run found: its last population’s first front, and the whole population.

Goals

What a model gives for one design: its goals, each to be made as small as it can be, and by how much it breaks the constraints, zero if it keeps them all.

Member

One design of a population: where it is, what the model gave for it, and where it ranks.

Nsga2

The optimizer’s settings: the variables, the number of goals, the population, the number of generations, and the crossover’s and mutation’s parameters. It serializes as its fields, and reads back through the same checks as Nsga2::new and its with_ methods.

Run

A run in progress: its population, ranked, and the candidates waiting to be evaluated.

Constants

MAX_BOUND

The largest bound a variable may have, in size: f64::MAX/4, so that crossover’s sums and spreads stay finite.

MAX_OBJECTIVES

The most goals a run takes.

MAX_POPULATION

The largest population a run takes, 2¹². The sort of parents and children together keeps, for each design, the list of designs it dominates: up to about (2N)²/2 indices, some 270 MB on a 64-bit machine at this size (more while the lists grow), and four times as much for each doubling.

Functions

dominates

Whether a’s goals dominate b’s: no worse in any, better in at least one. The two should be the same length; only as many goals as the shorter has are compared.

generational_distance

The generational distance of set from reference: the mean, over the points of set, of the Euclidean distance to the nearest point of reference. It is Deb et al.’s (2002) convergence metric Υ (§IV-B, p. 188), and pymoo’s GD: zero when every point lies on the reference. NaN for an empty set or reference.

inverted_generational_distance

The inverted generational distance: the mean, over the points of reference, of the Euclidean distance to the nearest point of set, as pymoo’s IGD. Small only if set both lies near the reference and covers all of it.