mlsanityData to 7 Oct 2026

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

arXiv 2208.08759 ↗First posted 18 Aug 2022cs.NE cs.AI cs.DScited by 14

Not on the map. Why?

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.

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

Builds on

8 of 52 references.

References · 8

  1. 2017Fast Genetic Algorithmscited by 29
  2. 2020Does Comma Selection Help To Cope With Local Optimacited by 15
  3. 2020Self-Adjusting Evolutionary Algorithms for Multimodal Optimizationcited by 15
  4. 2022A First Runtime Analysis of the NSGA-II on a Multimodal Problemcited by 15
  5. 2020Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectivescited by 12
  6. 2020A Rigorous Runtime Analysis of the (1 + (λ, λ)) GA on Jump Functionscited by 8
  7. 2018When Hypermutations and Ageing Enable Artificial Immune Systems to Outperform Evolutionary Algorithmscited by 5
  8. 2015On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Schedulingcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 4; 2025: 1; 2026: 3.

14 papers.

Sort:

  1. 2022A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)cited by 11
  2. 2023Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithmscited by 8
  3. 2022Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectivescited by 6
  4. 2023The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problemcited by 6
  5. 2023How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffscited by 4
  6. 2024Many Objective Problems Where Crossover is Provably Essentialcited by 3
  7. 2023How Well Does the Metropolis Algorithm Cope With Local Optima?cited by 2
  8. 2024A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimizationcited by 1
  9. 2025Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategycited by 1
  10. 2024Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithmscited by 0
  11. 2024Unlocking the Potential of Global Human Expertisecited by 0
  12. 2026Parent Selection Mechanisms in Elitist Crossover-Based Algorithmscited by 0
2 more
  1. 2026Multi-Party Multi-Objective Optimization as Consensus Search: Runtime Analysis of Cross-Party Recombinationcited by 0
  2. 2026SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guaranteescited by 0