--- primary_layer: layer2 related_layers: [] page_type: concept --- # NSGA-II (Nondominated Sorting Genetic Algorithm II) 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 {cite}`deb2002nsga2`. The concrete procedure is shown in the pseudocode below. ## Pseudocode ```{prf:algorithm} NSGA-II :label: alg-nsga2 **Inputs** objective functions, population size $N$, initial population $P_0$ **Output** the Pareto front of the final generation 1. Set $t=0$; randomly generate $P_0$, then generate an offspring population $Q_0$ via binary tournament selection, crossover, and mutation 2. Form the combined population $R_t = P_t \cup Q_t$ (size $2N$) 3. Non-dominated-sort $R_t$ to obtain the front sequence $\mathcal{F} = (\mathcal{F}_1, \mathcal{F}_2, \ldots)$ 4. Set $P_{t+1} = \emptyset$, and add fronts to $P_{t+1}$ in order for as long as each $\mathcal{F}_i$ fits entirely 5. For the last front $\mathcal{F}_l$ that no longer fits in full, compute each individual's crowding distance 6. 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 7. Apply binary tournament selection (using $\prec_n$ as the selection criterion), crossover, and mutation to $P_{t+1}$ to generate $Q_{t+1}$ 8. Set $t = t+1$ and return to step 2, repeating until the termination condition is reached ``` ## Flowchart ```{mermaid} flowchart TD INIT["Initializer
Generate initial population P0
(L1)"] --> GEN subgraph GEN["One generation (DirectStrategy.step)"] direction TB ASK["GA.ask()
Binary tournament selection →
SBX crossover →
Polynomial mutation to generate Qt
(L1, L7)"] --> EVAL["True evaluation
(no surrogate involved)"] EVAL --> COMB["GA.tell()
Combine Rt = Pt ∪ Qt
(L2)"] COMB --> SORT["NSGA2Comparator.sort_population()
Non-dominated sorting →
crowding distance
(L3-6)"] SORT --> TRUNC["TruncationSelection
Take top N individuals as Pt+1
(L4-6)"] end GEN --> TERM{"Termination condition
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 | ```python 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)$ {cite}`deb2002nsga2`. **$\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 {cite}`deb2002nsga2`. **$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. ## Related - [References](../references.md): Full bibliographic details for the source - [Comparator](../concepts/problem_and_ranking/comparators.md): Detailed specification of `NSGA2Comparator` - [Crossover](../concepts/search_algorithms/crossover.md): List of crossover operators including `CrossoverSBX` - [Mutation](../concepts/search_algorithms/mutation.md): List of mutation operators including `MutationPolynomial` - [ParentSelection](../concepts/search_algorithms/parent_selection.md): Detailed usage of `TournamentSelection` - [SurvivorSelection](../concepts/search_algorithms/survivor_selection.md): Detailed usage of `TruncationSelection` - [OptimizationStrategy](../concepts/execution_and_evaluation/strategies.md): List of strategies including `DirectStrategy` - [NonDominatedSorting](../concepts/problem_and_ranking/nondominated_sorting.md): Implementation details of non-dominated sorting