# Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover

arXiv: https://arxiv.org/abs/2208.08759 · HTML: https://mlsanity.com/paper/2208.08759/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 52 references that are in the map.
- First posted on arXiv 18 Aug 2022.

## Builds on (most cited first, 8 of 8)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Does Comma Selection Help To Cope With Local Optima](https://mlsanity.com/paper/2004.01274/) (2020)
- [Self-Adjusting Evolutionary Algorithms for Multimodal Optimization](https://mlsanity.com/paper/2004.03266/) (2020)
- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [A Rigorous Runtime Analysis of the (1 + (λ, λ)) GA on Jump Functions](https://mlsanity.com/paper/2004.06702/) (2020)
- [When Hypermutations and Ageing Enable Artificial Immune Systems to Outperform Evolutionary Algorithms](https://mlsanity.com/paper/1804.01314/) (2018)
- [On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling](https://mlsanity.com/paper/1504.06363/) (2015)

## Built on by (most cited first, 14 of 14)

- [A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)](https://mlsanity.com/paper/2211.08202/) (2022)
- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives](https://mlsanity.com/paper/2211.13084/) (2022)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms](https://mlsanity.com/paper/2405.04480/) (2024)
- [Unlocking the Potential of Global Human Expertise](https://mlsanity.com/paper/2411.00156/) (2024)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)
- [Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombination](https://mlsanity.com/paper/2605.17454/) (2026)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the (μ+1) genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee.