On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

Opris, Andre

doi:10.24963/ijcai.2026/705

On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

Andre Opris

Download BibTeX Cite

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence. Main Track. Pages 6334-6342.

https://doi.org/10.24963/ijcai.2026/705

Keywords

Search: Evolutionary computation
Search: Heuristic search

Abstract

In recent years, theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical m-objective m-OneJumpZeroJump function (m-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes m-OJZJ asymptotically faster than NSGA-III without crossover for any number m of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on 4-OJZJ when crossover is turned off.

Andre Opris. 2026. On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III. In Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26. IJCAI, 6334–6342. https://doi.org/10.24963/ijcai.2026/705

@inproceedings{ijcai2026p705,
  title     = {On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III},
  author    = {Opris, Andre},
  booktitle = {Proceedings of the Thirty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-26}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Diego Calvanese},
  pages     = {6334--6342},
  year      = {2026},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2026/705},
  url       = {https://doi.org/10.24963/ijcai.2026/705},
}

TY  - CPAPER
TI  - On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III
AU  - Opris, Andre
T2  - Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-26
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2026
SP  - 6334
EP  - 6342
DO  - 10.24963/ijcai.2026/705
UR  - https://doi.org/10.24963/ijcai.2026/705
ER  -