Runtime Analyses of NSGA-III on Many-Objective Problems: Provable Exponential Speedup via Stochastic Population Update
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_ | 1866908935301103616 |
|---|---|
| author | Opris, Andre |
| author_facet | Opris, Andre |
| contents | NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is particularly well suited for optimizing problems with more than three objectives, distinguishing it from the classical NSGA-II. However, theoretical understanding of when and why NSGA-III performs well is still at an early stage. In this paper, we contribute to closing this gap by conducting rigorous runtime analyses on the classical many-objective benchmark problems $d$-\textsc{LeadingOnesTrailingZeros} ($d$-LOTZ), $d$-\textsc{CountingOnesCountingZeros} ($d$-COCZ), $d$-\textsc{OneMinMax} ($d$-OMM), and $d$-\textsc{OneJumpZeroJump} ($d$-OJZJ) for arbitrary numbers of objectives $d$. In particular, we improve upon previous results when the population size is asymptotically larger than the size of the Pareto front. Notably, in the bi-objective case, the derived upper runtime bounds are asymptotically tighter than those known for NSGA-II. For the problems $2$-OMM and $2$-OJZJ, NSGA-III even outperforms NSGA-II in terms of expected runtime for suitable population sizes $μ$. Further, we show that a stochastic population update mechanism provably yields an exponential speedup in the expected runtime on many-objective multimodal problems such as $d$-OJZJ, as well as on the function $d$-\textsc{RRMO}, a many-objective variant of the Real-Royal-Road function, for certain parameter regimes. To complement our analysis, we also establish tight runtime bounds for NSGA-III on $2$-\textsc{OJZJ} and $4$-\textsc{OJZJ}. In particular, the result for $4$-OJZJ provides, to the best of our knowledge, the first lower bound for NSGA-III on a classical benchmark problem with more than two objectives. Deriving these bounds requires a substantially deeper analysis of the population dynamics of NSGA-III than has been achieved in previous work. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01256 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Runtime Analyses of NSGA-III on Many-Objective Problems: Provable Exponential Speedup via Stochastic Population Update Opris, Andre Neural and Evolutionary Computing Primary: 68W50, Secondary: 68W40, 68W20 F.2.2; G.3 NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is particularly well suited for optimizing problems with more than three objectives, distinguishing it from the classical NSGA-II. However, theoretical understanding of when and why NSGA-III performs well is still at an early stage. In this paper, we contribute to closing this gap by conducting rigorous runtime analyses on the classical many-objective benchmark problems $d$-\textsc{LeadingOnesTrailingZeros} ($d$-LOTZ), $d$-\textsc{CountingOnesCountingZeros} ($d$-COCZ), $d$-\textsc{OneMinMax} ($d$-OMM), and $d$-\textsc{OneJumpZeroJump} ($d$-OJZJ) for arbitrary numbers of objectives $d$. In particular, we improve upon previous results when the population size is asymptotically larger than the size of the Pareto front. Notably, in the bi-objective case, the derived upper runtime bounds are asymptotically tighter than those known for NSGA-II. For the problems $2$-OMM and $2$-OJZJ, NSGA-III even outperforms NSGA-II in terms of expected runtime for suitable population sizes $μ$. Further, we show that a stochastic population update mechanism provably yields an exponential speedup in the expected runtime on many-objective multimodal problems such as $d$-OJZJ, as well as on the function $d$-\textsc{RRMO}, a many-objective variant of the Real-Royal-Road function, for certain parameter regimes. To complement our analysis, we also establish tight runtime bounds for NSGA-III on $2$-\textsc{OJZJ} and $4$-\textsc{OJZJ}. In particular, the result for $4$-OJZJ provides, to the best of our knowledge, the first lower bound for NSGA-III on a classical benchmark problem with more than two objectives. Deriving these bounds requires a substantially deeper analysis of the population dynamics of NSGA-III than has been achieved in previous work. |
| title | Runtime Analyses of NSGA-III on Many-Objective Problems: Provable Exponential Speedup via Stochastic Population Update |
| topic | Neural and Evolutionary Computing Primary: 68W50, Secondary: 68W40, 68W20 F.2.2; G.3 |
| url | https://arxiv.org/abs/2505.01256 |