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

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

## 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 (most cited first, 14 of 14)

- [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)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [Stagnation Detection with Randomized Local Search](https://mlsanity.com/paper/2101.12054/) (2021)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/2006.03523/) (2020)
- [Design and Analysis of Diversity-Based Parent Selection Schemes for Speeding Up Evolutionary Multi-objective Optimisation](https://mlsanity.com/paper/1805.01221/) (2018)
- [First Steps Towards a Runtime Analysis When Starting With a Good Solution](https://mlsanity.com/paper/2006.12161/) (2020)
- [Stagnation Detection in Highly Multimodal Fitness Landscapes](https://mlsanity.com/paper/2104.04395/) (2021)
- [Stagnation Detection Meets Fast Mutation](https://mlsanity.com/paper/2201.12158/) (2022)
- [Evolutionary Algorithms and Submodular Functions: Benefits of Heavy-Tailed Mutations](https://mlsanity.com/paper/1805.10902/) (2018)
- [Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection](https://mlsanity.com/paper/2203.11550/) (2022)

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

- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [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)
- [The (1+(λ,λ)) Global SEMO Algorithm](https://mlsanity.com/paper/2210.03618/) (2022)
- [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)
- [Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems](https://mlsanity.com/paper/2306.03409/) (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)
- [Runtime Analysis for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2207.04045/) (2022)
- [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 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.