mlsanityData to 14 Oct 2026

A First Runtime Analysis of the NSGA-II on a Multimodal Problem

arXiv 2204.13750 ↗First posted 28 Apr 2022cs.NE cs.AI cs.DScited by 15

Not on the map. Why?

Abstract (arXiv)

Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer NSGA-II have been conducted. We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of two multimodal objectives. We prove that if the population size N is at least four times the size of the Pareto front, then the NSGA-II with four different ways to select parents and bit-wise mutation optimizes the OneJumpZeroJump benchmark with jump size~2 ≤ k ≤ n/4 in time O(N nk). When using fast mutation, a recently proposed heavy-tailed mutation operator, this guarantee improves by a factor of kOmega(k). Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 14 of its 58 references that are in the map. First posted on arXiv 28 Apr 2022.

Builds on

14 of 58 references.

References · 14

  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. 2019The Runtime of the Compact Genetic Algorithm on Jump Functionscited by 13
  5. 2020Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectivescited by 12
  6. 2021Stagnation Detection with Randomized Local Searchcited by 11
  7. 2021Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distributioncited by 11
  8. 2020Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functionscited by 10
  9. 2018Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisationcited by 9
  10. 2020First Steps Towards a Runtime Analysis When Starting With a Good Solutioncited by 9
  11. 2021Stagnation Detection in Highly Multimodal Fitness Landscapescited by 8
  12. 2022Stagnation Detection Meets Fast Mutationcited by 8
2 more
  1. 2018Evolutionary Algorithms and Submodular Functions: Benefits of Heavy-Tailed Mutationscited by 6
  2. 2022Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selectioncited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 5; 2024: 2; 2025: 1; 2026: 1.

15 papers.

Sort:

  1. 2022Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossovercited by 14
  2. 2022From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Boundscited by 13
  3. 2022A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)cited by 11
  4. 2023Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithmscited by 8
  5. 2022Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectivescited by 6
  6. 2023The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problemcited by 6
  7. 2023How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffscited by 5
  8. 2022The (1+(λ,λ)) Global SEMO Algorithmcited by 3
  9. 2024Many Objective Problems Where Crossover is Provably Essentialcited by 3
  10. 2023How Well Does the Metropolis Algorithm Cope With Local Optima?cited by 2
  11. 2023Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problemscited by 1
  12. 2024A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimizationcited by 1
3 more
  1. 2025Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategycited by 1
  2. 2022Runtime Analysis for Permutation-based Evolutionary Algorithmscited by 0
  3. 2026SPEA2^+: Improved Density Estimation in SPEA2 with Provable Runtime Guaranteescited by 0