Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
Andre Opris · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2026
Evolutionary algorithms are widely used for multi-objective optimization, with NSGA-III being particularly effective for problems with more than three objectives, unlike NSGA-II. Despite its empirical success, its theoretical understanding remains limited, especially regarding 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 work, 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. We show that, for population sizes n +1 ≤ μ = O(log(n)c (n + 1)) where c < 1 is a constant, NSGA-III requires Ω(n2 log n/μ) generations in expectation for covering the Pareto front, providing one of the first lower bounds for NSGA-III on a classical benchmark. Complementing this, we also improve the best known upper bound for 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 constant m and [EQUATION]. This yields tight runtime bounds for m = 2, and the surprising result that NSGA-III outperforms NSGA-II by a factor of μ/n in the expected runtime. This Hot-off-the-Press paper summarises the work Andre Opris. 2026. Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds. Proceedings of the AAAI Conference on Artificial Intelligence, 40(43), 37125–37133 [9].