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

Andre Opris

AAAI 2026technical0 citations

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

Abstract

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 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. We show that, for population sizes n+1 ≤ µ = O(log(n)^c (n+1)) where c

BibTeX

@inproceedings{aaai2026_towardsarigorous,
  title = {Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds},
  author = {Andre Opris},
  booktitle = {AAAI 2026},
  year = {2026}
}