NSGA-II (Nondominated Sorting Genetic Algorithm II)#

Layer 2: Compose

NSGA-II is a genetic algorithm widely used as a selection mechanism for multi-objective optimization. It combines non-dominated sorting with crowding distance to simultaneously achieve convergence to the Pareto front and diversity maintenance in the solution set.

Overview#

Multi-objective optimization has two independent goals: convergence to the Pareto front, and maintaining diversity within the solution set.

The original NSGA (Nondominated Sorting Genetic Algorithm) achieved both with non-dominated sorting and a sharing function, but the sharing function required manually tuning a variance parameter \(\sigma_{\mathrm{share}}\), and its computational complexity was \(O(N^2)\).

NSGA-II replaces this sharing function with a crowded-comparison operator (\(\prec_n\)) based on crowding distance, achieving parameter-free diversity maintenance.

Each individual carries two attributes: a non-domination rank \(i_{\mathrm{rank}}\) and a crowding distance \(i_{\mathrm{distance}}\). \(\prec_n\) prefers individuals with a lower (better) rank, and within the same rank, prefers individuals with a larger crowding distance (i.e. in a sparser neighborhood).

NSGA-II also performs elite selection from the \(2N\) individuals formed by combining the parent population \(P_t\) and offspring population \(Q_t\), so that good solutions are not lost across generations (elitism).

The source is [3]. The concrete procedure is shown in the pseudocode below.

Pseudocode#

Algorithm 5 (NSGA-II)

Inputs objective functions, population size \(N\), initial population \(P_0\) Output the Pareto front of the final generation

Set \(t=0\); randomly generate \(P_0\), then generate an offspring population \(Q_0\) via binary tournament selection, crossover, and mutation
Form the combined population \(R_t = P_t \cup Q_t\) (size \(2N\))
Non-dominated-sort \(R_t\) to obtain the front sequence \(\mathcal{F} = (\mathcal{F}_1, \mathcal{F}_2, \ldots)\)
Set \(P_{t+1} = \emptyset\), and add fronts to \(P_{t+1}\) in order for as long as each \(\mathcal{F}_i\) fits entirely
For the last front \(\mathcal{F}_l\) that no longer fits in full, compute each individual’s crowding distance
Sort \(\mathcal{F}_l\) in descending order by \(\prec_n\), and take individuals from the front of that order until \(P_{t+1}\) reaches \(N\) individuals
Apply binary tournament selection (using \(\prec_n\) as the selection criterion), crossover, and mutation to \(P_{t+1}\) to generate \(Q_{t+1}\)
Set \(t = t+1\) and return to step 2, repeating until the termination condition is reached

Flowchart#

        flowchart TD
    INIT["Initializer<br/>Generate initial population P0<br/>(L1)"] --> GEN
    subgraph GEN["One generation (DirectStrategy.step)"]
        direction TB
        ASK["GA.ask()<br/>Binary tournament selection →<br/>SBX crossover →<br/>Polynomial mutation to generate Qt<br/>(L1, L7)"] --> EVAL["True evaluation<br/>(no surrogate involved)"]
        EVAL --> COMB["GA.tell()<br/>Combine Rt = Pt ∪ Qt<br/>(L2)"]
        COMB --> SORT["NSGA2Comparator.sort_population()<br/>Non-dominated sorting →<br/>crowding distance<br/>(L3-6)"]
        SORT --> TRUNC["TruncationSelection<br/>Take top N individuals as Pt+1<br/>(L4-6)"]
    end
    GEN --> TERM{"Termination condition<br/>reached?"}
    TERM -- "Not yet (L8)" --> GEN
    TERM -- "Reached" --> RESULT(["Pareto front"])

Configuration in saealib#

Role	saealib implementation	Corresponding step
Search algorithm	`GA` (`ask()` performs crossover and mutation; `tell()` performs combining \(R_t=P_t\cup Q_t\) and survivor selection)	L1-2, L7
Parent selection	`TournamentSelection(tournament_size=2)` (the winner is decided via `ctx.comparator.compare_population`)	L1, L7
Crossover	`CrossoverSBX(prob=0.9, eta=20.0)`	L1, L7
Mutation	`MutationPolynomial(eta=20.0)`	L1, L7
Non-dominated sorting + crowding distance	`NSGA2Comparator` (`sort_population` internally calls `non_dominated_sort` and `crowding_distance_all_fronts`)	L3-6
Survivor selection	`TruncationSelection()` (keeps the top \(N\) individuals in the order given by `comparator.sort_population`)	L4-6
Evaluation strategy	`DirectStrategy` (no surrogate involved; every candidate generated by `GA.ask()` is evaluated with the true objective function)	L2

from saealib import GA, NSGA2Comparator, Optimizer
from saealib.benchmarks import zdt1
from saealib.operators.crossover import CrossoverSBX
from saealib.operators.mutation import MutationPolynomial
from saealib.operators.selection import TournamentSelection, TruncationSelection
from saealib.strategies import DirectStrategy
from saealib.termination import Termination, max_fe


problem = zdt1(n_var=10)
problem.comparator = NSGA2Comparator()

algorithm = GA(
    CrossoverSBX(prob=0.9, eta=20.0),
    MutationPolynomial(eta=20.0),
    TournamentSelection(tournament_size=2),
    TruncationSelection(),
)

opt = (
    Optimizer(problem)
    .set_algorithm(algorithm)
    .set_strategy(DirectStrategy())
    .set_termination(Termination(max_fe(2000)))
)
ctx = opt.run()
pareto_f = ctx.pareto_archive.get_array("f")

The problem.comparator = NSGA2Comparator() line can be omitted, since it’s the same as the default when n_obj > 1. Because no surrogate is used at all, there’s no need to call set_surrogate_manager() on the Optimizer.

Differences from the source#

Relative to the original NSGA-II, the example combines GA, SBX, Polynomial mutation, binary tournament selection, and TruncationSelection. This concrete combination is an saealib configuration example, not the selection mechanism itself as defined by the original method. When individuals with the same crowding distance meet the truncation boundary, the default TruncationSelection(randomize_ties=False) preserves the deterministic order from sort_population. Only randomize_ties=True shuffles tied individuals at that boundary.

Parameters and variants#

Complexity#

Non-dominated sorting is \(O(MN^2)\) (\(M\) the number of objectives, \(N\) the population size), computing crowding distance is \(O(MN\log N)\), and sorting by \(\prec_n\) is \(O(N\log N)\).

The dominant cost per generation is non-dominated sorting, giving an overall complexity of \(O(MN^2)\) [3].

\(\eta_c\) and \(\eta_m\) (distribution indices): Adjusted via CrossoverSBX(eta=...) and MutationPolynomial(eta=...). Larger values generate offspring closer to the parents (more conservative search). The paper uses \(20\) for both in its real-valued experiments, and the example explicitly sets the same distribution indices [3].

\(p_m\) (per-variable mutation probability): The paper uses \(p_m = 1/n\) (\(n\) being the number of decision variables). This corresponds not to the individual-level prob, but to the per-variable application probability prob_var. For MutationPolynomial(prob_var=None), saealib automatically sets the default to \(\min(0.5,\, 1/\mathrm{dim})\). Therefore, the paper’s \(p_m=1/n\) is a setting from the paper and does not mean that every library configuration uses this value.