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
Fields of Study & Subjects
Advanced Multi-Objective Optimization Algorithms
Metaheuristic Optimization Algorithms Research
Vehicle Routing Optimization Methods
Publication details
- Journal / source
- Proceedings of the AAAI Conference on Artificial Intelligence
- Publisher
- Association for the Advancement of Artificial Intelligence (AAAI)
- Volume
- 40
- Issue
- 43
- Pages
- 37125–37133
- Publication date
- 14 March 2026