# Hyper-Heuristics Can Profit From Global Variation Operators

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 40 references that are in the map.
- First posted on arXiv 19 Jul 2024.

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

- [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)
- [Stagnation Detection with Randomized Local Search](https://mlsanity.com/paper/2101.12054/) (2021)
- [Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/2006.03523/) (2020)
- [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)
- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [The Compact Genetic Algorithm Struggles on Cliff Functions](https://mlsanity.com/paper/2204.04904/) (2022)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)

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

- [Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems](https://mlsanity.com/paper/2605.29916/) (2026)
- [Unlearning Works Better Than You Think: Local Reinforcement-Based Selection of Auxiliary Objectives](https://mlsanity.com/paper/2504.14418/) (2025)
- [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. The O(n3) runtime of the MAHH, for almost all cliff widths d≥ 2, is significantly better than the Theta(nd) runtime of simple elitist evolutionary algorithms (EAs) on CLIFF. In this work, we first show that this advantage is specific to the CLIFF problem and does not extend to the JUMP benchmark, the most prominent multi-modal benchmark in the theory of randomized search heuristics. 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 is significantly slower than the O(nm) runtime of simple elitist EAs. Encouragingly, we also show that replacing the local one-bit mutation operator in the MAHH with the global bit-wise mutation operator, commonly used in EAs, yields a runtime of min1, O(fraceln(n)m)m , O(nm) on JUMP functions. This is at least as good as the runtime of simple elitist EAs. For larger values of m, this result proves an asymptotic performance gain over simple EAs. As our proofs reveal, the MAHH profits from its ability to walk through the valley of lower objective values in moderate-size steps, always accepting inferior solutions. This is the first time that such an optimization behavior is proven via mathematical means. Generally, our result shows that combining two ways of coping with local optima, global mutation and accepting inferior solutions, can lead to considerable performance gains.