Optimization

NSGA-II

A fast elitist genetic algorithm that finds a diverse approximation of the whole Pareto front in a single run.

Evolving the whole front

The non-dominated sorting genetic algorithm II (NSGA-II) is the most widely used multi-objective evolutionary algorithm. Instead of tracing the Pareto front point by point through repeated scalarizations, it evolves a population that spreads across the entire front simultaneously, returning a diverse set of trade-off solutions in one run.

Non-dominated sorting

Kronos motion — fast proton

Each generation, the population is sorted into fronts by Pareto dominance: the non-dominated solutions form front 1, removing them and repeating gives front 2, and so on. Selection favors solutions in earlier fronts, driving the population toward the true Pareto front. This ranking replaces a single fitness value.

Crowding distance

Within a front, solutions are ranked by crowding distance, a measure of how isolated each is in objective space.
Isolated solutions are preferred over clustered ones, preserving diversity across the front.
This avoids the population collapsing onto one region and keeps the approximated front well spread.

Elitism and the loop

NSGA-II combines parents and offspring, then selects the best half by front rank and crowding distance. This elitist scheme guarantees good solutions survive across generations. The full loop is: generate offspring by crossover and mutation, merge with parents, non-dominated sort, fill the next generation front by front using crowding distance to break ties.

Strengths and successors

NSGA-II is fast (its sorting runs in O(k*N^2) for k objectives and population N), needs no scalarization weights, and handles nonconvex fronts. It struggles beyond three or four objectives, where dominance loses discriminating power; NSGA-III and decomposition-based MOEA/D address this many-objective regime using reference directions.

python

# per generation:
# 1. offspring via crossover+mutation
# 2. R = parents + offspring; fronts = fast_nondominated_sort(R)
# 3. fill next gen by front; within last front sort by crowding distance

NSGA-II delivers a full trade-off surface among conflicting engineering objectives in one run, a practical tool for early design exploration.