Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914147155836928 |
|---|---|
| author | Opris, Andre |
| author_facet | Opris, Andre |
| contents | 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 $Ω(n^2 \log(n) / μ)$ generations in expectation to optimize $2$-OMM assuming the population size $μ$ satisfies $n+1 \leq μ=O(\log(n)^c(n+1))$ where $n$ denotes the problem size and $c<1$ is a constant. Apart from~\cite{opris2025multimodal}, 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} \leq μ\in O(\sqrt{\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_07125 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds Opris, Andre Neural and Evolutionary Computing 68W05, 68Q25, 68W20, 68W50, 68T20 F.2.2 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 $Ω(n^2 \log(n) / μ)$ generations in expectation to optimize $2$-OMM assuming the population size $μ$ satisfies $n+1 \leq μ=O(\log(n)^c(n+1))$ where $n$ denotes the problem size and $c<1$ is a constant. Apart from~\cite{opris2025multimodal}, 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} \leq μ\in O(\sqrt{\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. |
| title | Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds |
| topic | Neural and Evolutionary Computing 68W05, 68Q25, 68W20, 68W50, 68T20 F.2.2 |
| url | https://arxiv.org/abs/2511.07125 |