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

Evolutionary algorithms are widely used for solving multi-objective optimization problems. A prominent example is NSGA-III, which is particularly well suited for 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(n^2 \log(n) / \mu)$ generations in expectation to optimize $2$-OMM assuming the population size $\mu$ satisfies $n+1 \leq \mu =O(\log(n)^c(n+1))$ where $n$ denotes the problem size and $c