# From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 30 references that are in the map.
- First posted on arXiv 28 Sep 2022.

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

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2110.09332/) (2021)
- [Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection](https://mlsanity.com/paper/2203.11550/) (2022)

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

- [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)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [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)
- [Unlocking the Potential of Global Human Expertise](https://mlsanity.com/paper/2411.00156/) (2024)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)
- [Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination](https://mlsanity.com/paper/2605.17454/) (2026)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Due to the more complicated population dynamics of the NSGA-II, none of the existing runtime guarantees for this algorithm is accompanied by a non-trivial lower bound. Via a first mathematical understanding of the population dynamics of the NSGA-II, that is, by estimating the expected number of individuals having a certain objective value, we prove that the NSGA-II with suitable population size needs Omega(Nnlog n) function evaluations to find the Pareto front of the OneMinMax problem and Omega(Nnk) evaluations on the OneJumpZeroJump problem with jump size k. These bounds are asymptotically tight (that is, they match previously shown upper bounds) and show that the NSGA-II here does not even in terms of the parallel runtime (number of iterations) profit from larger population sizes. For the OneJumpZeroJump problem and when the same sorting is used for the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.