# Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2023.

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

- [Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms](https://mlsanity.com/paper/2306.02611/) (2023)
- [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)
- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization](https://mlsanity.com/paper/2407.17687/) (2024)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)
- [SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guarantees](https://mlsanity.com/paper/2606.12382/) (2026)

## Abstract (arXiv)

Evolutionary algorithms are popular algorithms for multiobjective optimisation (also called Pareto optimisation) as they use a population to store trade-offs between different objectives. Despite their popularity, the theoretical foundation of multiobjective evolutionary optimisation (EMO) is still in its early development. Fundamental questions such as the benefits of the crossover operator are still not fully understood. We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover: we propose classes of "royal road" functions on which these algorithms cover the whole Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time in expectation to cover the Pareto front. The latter even holds for a large class of black-box algorithms using any elitist selection and any unbiased mutation operator. Moreover, even the expected time to create a single Pareto-optimal search point is exponential. We provide two different function classes, one tailored for one-point crossover and another one tailored for uniform crossover, and we show that immune-inspired hypermutations cannot avoid exponential optimisation times. Our work shows the first example of an exponential performance gap through the use of crossover for the widely used NSGA-II algorithm and contributes to a deeper understanding of its limitations and capabilities.