# Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)

arXiv: https://arxiv.org/abs/2112.08581 · HTML: https://mlsanity.com/paper/2112.08581/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 62 references that are in the map.
- First posted on arXiv 16 Dec 2021.

## Builds on (most cited first, 10 of 10)

- [Probabilistic Tools for the Analysis of Randomized Optimization Heuristics](https://mlsanity.com/paper/1801.06733/) (2018)
- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [Pareto Optimization for Subset Selection with Dynamic Cost Constraints](https://mlsanity.com/paper/1811.07806/) (2018)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables](https://mlsanity.com/paper/2109.05799/) (2021)
- [Optimization of Chance-Constrained Submodular Functions](https://mlsanity.com/paper/1911.11451/) (2019)
- [An Efficient Evolutionary Algorithm for Minimum Cost Submodular Cover](https://mlsanity.com/paper/1908.01029/) (2019)
- [Faster Guarantees of Evolutionary Algorithms for Maximization of Monotone Submodular Functions](https://mlsanity.com/paper/1908.01230/) (2019)

## Built on by (most cited first, 8 of 8)

- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives](https://mlsanity.com/paper/2211.13084/) (2022)
- [Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)](https://mlsanity.com/paper/2203.02693/) (2022)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)
- [Runtime Analysis of Evolutionary Algorithms for Multi-party Multi-objective Optimization](https://mlsanity.com/paper/2501.16336/) (2025)

## Abstract (arXiv)

The non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such study exists for the NSGA-II so far. In this work, we show that mathematical runtime analyses are feasible also for the NSGA-II. As particular results, we prove that with a population size four times larger than the size of the Pareto front, the NSGA-II with two classic mutation operators and four different ways to select the parents satisfies the same asymptotic runtime guarantees as the SEMO and GSEMO algorithms on the basic OneMinMax and LeadingOnesTrailingZeros benchmarks. However, if the population size is only equal to the size of the Pareto front, then the NSGA-II cannot efficiently compute the full Pareto front: for an exponential number of iterations, the population will always miss a constant fraction of the Pareto front. Our experiments confirm the above findings.