# How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 61 references that are in the map.
- First posted on arXiv 20 Apr 2023.

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

- [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)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [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)
- [Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices](https://mlsanity.com/paper/1804.05650/) (2018)
- [A Rigorous Runtime Analysis of the (1 + (λ, λ)) GA on Jump Functions](https://mlsanity.com/paper/2004.06702/) (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)
- [First Steps Towards a Runtime Comparison of Natural and Artificial Evolution](https://mlsanity.com/paper/1504.06260/) (2015)
- [When Hypermutations and Ageing Enable Artificial Immune Systems to Outperform Evolutionary Algorithms](https://mlsanity.com/paper/1804.01314/) (2018)
- [Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima](https://mlsanity.com/paper/2304.09712/) (2023)
- [The Compact Genetic Algorithm Struggles on Cliff Functions](https://mlsanity.com/paper/2204.04904/) (2022)
- [Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm](https://mlsanity.com/paper/2302.12570/) (2023)

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

- [Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator](https://mlsanity.com/paper/2506.01107/) (2025)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems](https://mlsanity.com/paper/2605.29916/) (2026)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)
- [On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics](https://mlsanity.com/paper/2607.22036/) (2026)

## Abstract (arXiv)

In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local optimum of the multimodal cliff benchmark with remarkable efficiency. With its O(n3) runtime, for almost all cliff widths d, the MAHH massively outperforms the Theta(nd) runtime of simple elitist evolutionary algorithms (EAs). For the most prominent multimodal benchmark, the jump functions, the given runtime estimates of O(n2m m-Theta(m)) and Omega(2Omega(m)), for gap size m ≥ 2, are far apart and the real performance of MAHH is still an open question. In this work, we resolve this question. We prove that for any choice of the MAHH selection parameter~p, the expected runtime of the MAHH on a jump function with gap size m = o(n1/2) is at least Omega(n2m-1 / (2m-1)!). This renders the MAHH much slower than simple elitist evolutionary algorithms with their typical O(nm) runtime. We also show that the MAHH with the global bit-wise mutation operator instead of the local one-bit operator optimizes jump functions in time O(minm nm,fracn2m-1m!Omega(m)m-2), essentially the minimum of the optimization times of the (1+1) EA and the MAHH. This suggests that combining several ways to cope with local optima can be a fruitful approach.