Skip to content
Back to search results

NSGA-II — Non-dominated Sorting Genetic Algorithm II

Year
2002
Type
Evolutionary multi-objective optimisation algorithm
Font size

What does it do?

NSGA-II (Non-dominated Sorting Genetic Algorithm II) is the standard reference algorithm for multi-objective evolutionary optimisation, introduced by Deb, Pratap, Agarwal and Meyarivan in 2002.

Rather than collapsing multiple conflicting objectives into a single score, it evolves a population of candidate solutions across generations and returns a set of Pareto-optimal trade-off solutions — the Pareto front — using fast non-dominated sorting and a crowding distance metric to preserve diversity.

The intuition behind the method

Imagine you want to design a product that is simultaneously as cheap and as durable as possible. Cheaper usually means less durable, so there is no single perfect answer — there is a family of sensible compromises. NSGA-II works like a population of competing designs: each generation, weaker designs that are dominated by others on every objective are eliminated, and the survivors are spread out so they cover the full range of trade-offs rather than clustering around one corner. After enough generations, you are left with a rich menu of options — the Pareto front — from which you choose the balance that fits your priorities.

History

NSGA-II was published by Kalyanmoy Deb and colleagues at the Indian Institute of Technology Kanpur in 2002 as a corrected and substantially improved successor to the original NSGA (Srinivas & Deb, 1994). The key innovations were a fast non-dominated sorting procedure of O(MN²) complexity, an explicit crowding distance operator to maintain solution diversity without a sharing parameter, and an elitist selection mechanism. The 2002 IEEE Transactions on Evolutionary Computation paper has become one of the most highly cited works in evolutionary computation and established NSGA-II as the de facto benchmark for multi-objective evolutionary algorithms. Later variants — NSGA-III (2014) and others — extend the framework to many-objective problems.

When to use it

NSGA-II applies whenever a problem has two or more conflicting objective functions that cannot be merged into a single criterion without loss of information. The decision variables can be continuous, binary, or categorical, and no distributional assumption on the objective landscape is required. The algorithm suits engineering design, resource allocation, scheduling, and portfolio problems where a spectrum of trade-off solutions is more useful than a single optimum. A sufficient number of generations (typically several hundred or more) is needed to achieve good front coverage; running too few generations is the main failure mode.

Limitations and considerations

  • Performance degrades as the number of objectives grows beyond three or four — crowding distance becomes a poor diversity measure in high dimensions.
  • Requires careful tuning of population size and generation count; too few generations prevents adequate front coverage.
  • Evaluating objective functions that involve expensive simulations makes the algorithm computationally costly.
  • Results are stochastic: different random seeds can yield different Pareto fronts, so multiple runs and statistical comparison (e.g. hypervolume) are recommended.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Produces a diverse set of Pareto-optimal trade-off solutions in a single run, avoiding the need to repeat optimisation with different weights.
  • Fast non-dominated sorting runs in O(MN²) time (M objectives, N population size), making it tractable for moderate problem sizes.
  • Elitist selection ensures that good solutions found early are never discarded.
  • Applicable to continuous, binary, and categorical decision variables without distributional assumptions.
  • Widely validated across engineering, operations research, and computational science domains.

Applications

  • Engineering design: simultaneously minimising weight and maximising structural strength in mechanical components.
  • Environmental and energy systems: balancing cost, emissions, and reliability in power-grid or renewable-energy planning.
  • Healthcare and operations research: scheduling that optimises patient wait time, resource utilisation, and cost simultaneously.
  • Portfolio optimisation in finance and project selection in business: trading off return, risk, and liquidity.
  • Hyperparameter tuning in machine learning: optimising accuracy against model complexity or inference time.

How it works

How it works

1

A population of candidate solutions is created by sampling decision variables randomly (or by design) within their bounds. The population size is set large enough to ensure diversity across the objective space from the outset.

2

Each candidate solution is decoded into decision-variable values and every objective function is evaluated. The result is a vector of objective scores per individual. This step is often the computational bottleneck when objectives involve simulations or expensive models.

3

Solutions are ranked by non-dominated sorting: the first front contains all solutions that no other solution dominates on every objective; the second front contains solutions dominated only by those in the first front; and so on. Within each front, a crowding distance score is computed to measure how isolated a solution is from its neighbours — higher crowding distance means the solution occupies a less crowded region of the front.

4

An elitist selection strategy merges the current population with offspring and retains the best N individuals, filling fronts in order and using crowding distance to break ties within the last admissible front. This guarantees that good solutions found in previous generations are never lost.

5

Selected individuals reproduce through genetic operators — binary tournament selection, simulated binary crossover (SBX), and polynomial mutation — producing a new offspring population. These operators preserve meaningful variation while exploring the neighbourhood of promising solutions.

6

Steps evaluate through evolve repeat for a specified number of generations. Convergence is judged by visual inspection of the Pareto front or by hypervolume indicator tracking. The final output is the non-dominated solution set approximating the true Pareto front.

Common pitfalls

  • Running fewer than several hundred generations typically yields an incomplete Pareto front; if computational budget is tight, consider weighted single-objective optimisation instead.
  • Treating a problem with a single objective as multi-objective is unnecessary — use a single-objective optimiser.
  • Neglecting to set sensible variable bounds leads to populations that never reach feasible or meaningful regions of the search space.
  • Reporting only one solution from the Pareto front without disclosing the full front hides the trade-off structure that NSGA-II is designed to reveal.

Frequently asked questions

How many generations does NSGA-II need?

There is no universal rule, but running fewer than a few hundred generations typically produces an incomplete Pareto front. A practical approach is to plot the hypervolume indicator across generations and stop when it stabilises. If computational budget prevents this, a weighted single-objective optimiser is a safer alternative.

What is the Pareto front?

The Pareto front is the set of solutions where no improvement on one objective is possible without worsening at least one other. NSGA-II approximates this front, giving you the full menu of balanced compromises rather than a single answer.

Can NSGA-II handle more than two objectives?

Yes, but crowding distance — the diversity mechanism — becomes less effective as the number of objectives exceeds three or four (the 'many-objective' regime). For problems with five or more objectives, NSGA-III or decomposition-based algorithms such as MOEA/D are generally preferred.

Is NSGA-II deterministic?

No. The genetic operators and initial population involve randomness, so different runs with different random seeds can yield different Pareto-front approximations. Best practice is to run the algorithm multiple times and compare front quality using the hypervolume indicator.

Related methods

Sources

  1. Deb, K., Pratap, A., Agarwal, S. & Meyarivan, T. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.

    Open DOI reference
    Copied.
  2. Zitzler, E., Deb, K. & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173-195.

    Open DOI reference
    Copied.