# Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2025.

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

- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Evolutionary algorithms are widely used for solving multi-objective optimization problems. A prominent example is NSGA-III, which is particularly well suited for solving problems involving more than three objectives, distinguishing it from the classical NSGA-II. Despite its empirical success, the theoretical understanding of NSGA III remains very limited, especially with respect to runtime analysis. A central open problem concerns its population dynamics, which involve controlling the maximum number of individuals sharing the same fitness value during the exploration process. In this paper, we make a significant step towards such an understanding by proving tight runtime bounds for NSGA-III on the bi-objective OneMinMax (2-OMM) problem. Firstly, we prove that NSGA-III requires Omega(n2 log(n) / μ) generations in expectation to optimize 2-OMM assuming the population size μ satisfies n+1 ≤ μ =O(log(n)c(n+1)) where n denotes the problem size and c<1 is a constant. Apart from~citeopris2025multimodal, this is the first proven lower runtime bound for NSGA-III on a classical benchmark problem. Complementing this, we secondly improve the best known upper bound of NSGA-III on the m-objective OneMinMax problem (m-OMM) of O(n log(n)) generations by a factor of μ /(2n/m + 1)m/2 for a constant number m of objectives and population size (2n/m + 1)m/2 ≤ μ ∈ O(√log(n) (2n/m + 1)m/2). This yields tight runtime bounds in the case m = 2, and the surprising result that NSGA-III beats NSGA-II by a factor of μ/n in the expected runtime.