NSGA-II: A Fast and Elitist Multiobjective Genetic Algorithm

Deb, Pratap, Agarwal & Meyarivan, IEEE Transactions on Evolutionary Computation 6(2):182–197, April 2002. The standard answer to the question this spoke has been carrying since 2026-07-26: what a population-based optimizer does once the objective is a vector and no total order exists to rank against. Closes coverage edge 5. Read from the full paper (PDF via cse.unr.edu; the IEEE page is paywalled).

What it fixed

The paper is written against its own predecessor. NSGA (Srinivas & Deb, 1995) drew three standing criticisms, and NSGA-II is one answer to each:

• Cost. Nondominated sorting ran in O(MN³) for M objectives and population N, which priced out large populations. The fast nondominated sort replaces it with O(MN²) by having each solution carry a domination count and a list of the solutions it dominates, so each is visited a bounded number of times. The saving is bought with memory: storage rises to O(N²).
• No elitism. Each generation now forms the combined pool R = P ∪ Q (parents plus offspring, size 2N) and selects the new population from it front by front. Good solutions cannot be lost by bad luck, because the parents compete directly with their own children.
• The sharing parameter. Diversity in NSGA needed a user-set niche radius σ_share. NSGA-II drops it for crowding distance. For each objective, sort the front and give each solution the normalised gap between its two neighbours, summed across objectives, with the boundary points set to infinity so the extremes always survive. No parameter, and O(MN log N).

The two are then combined into the crowded-comparison operator: prefer the lower nondomination rank; on a tie within a front, prefer the less crowded solution. Selection pressure toward the front and pressure toward spreading along it, in one partial order.

Constraints, without a penalty function

The extension the spoke's engineering-adjacent pages should note: constrained domination changes the dominance test rather than the objective. A feasible solution always beats an infeasible one; between two infeasible solutions the smaller constraint violation wins; between two feasible ones the usual dominance applies. No penalty weight to tune, and the complexity is unchanged. It was tested on four constrained problems including a five-objective, seven-constraint nonlinear one.

How it was measured — and by whom

Nine unconstrained two-objective problems (SCH, FON, POL, KUR, and ZDT1–4 and ZDT6), each run to 25,000 function evaluations — NSGA-II at population 100 for 250 generations, PAES with depth 4 and a 100-slot archive, SPEA at 80 + 20 external. Two metrics, because the paper argues one number cannot serve: Υ, mean distance from the obtained set to a known true Pareto front (convergence), and Δ, the spread of the gaps between neighbouring solutions (diversity). NSGA-II reports better spread and better convergence than both on most problems.

Note the shape of that claim before repeating it. The comparison against PAES and SPEA was run by NSGA-II's authors, on test problems the first author had proposed guidelines for, scored by two metrics defined in this same paper. That is the fourth instance in this corpus of the pattern quality-log.md currently carries as an open item, and the third inside this spoke — DOAm leading Dik's own suite and adam-optimizer are the others. It does not make the result wrong; twenty-plus years of use have not overturned it. It does mean the 2002 numbers are the authors' numbers.

Where it sits

hypervolume-indicator is the metric that displaced Υ and Δ as the field's default, and it arrived nineteen years later: strictly monotonic with dominance, so one number does what the paper needed two for. Together they are the instrument and the algorithm for the multi-objective open question, and this spoke still has not scored its own algorithms on a multi-objective suite, which is what growth edge 3 asks for.

Mechanically NSGA-II is a genetic-algorithm whose selection operator has been replaced; the crossover (SBX) and polynomial mutation are ordinary real-coded GA machinery. What the paper demonstrates is the pattern no-free-lunch-theorem keeps producing here from the other direction: the useful move was not a new metaphor but a change to how solutions are compared.