# An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 72 references that are in the map.
- First posted on arXiv 7 May 2021.

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

- [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)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [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)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [First Steps Towards a Runtime Analysis When Starting With a Good Solution](https://mlsanity.com/paper/2006.12161/) (2020)
- [On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help](https://mlsanity.com/paper/1907.12438/) (2019)
- [Stagnation Detection in Highly Multimodal Fitness Landscapes](https://mlsanity.com/paper/2104.04395/) (2021)
- [The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis](https://mlsanity.com/paper/2007.08277/) (2020)
- [First Steps Towards a Runtime Comparison of Natural and Artificial Evolution](https://mlsanity.com/paper/1504.06260/) (2015)
- [Evolutionary Algorithms and Submodular Functions: Benefits of Heavy-Tailed Mutations](https://mlsanity.com/paper/1805.10902/) (2018)
- [Fast Artificial Immune Systems](https://mlsanity.com/paper/1806.00299/) (2018)
- [Lower Bounds from Fitness Levels Made Easy](https://mlsanity.com/paper/2104.03372/) (2021)
- [Standard Steady State Genetic Algorithms Can Hillclimb Faster than Mutation-only Evolutionary Algorithms](https://mlsanity.com/paper/1708.01571/) (2017)
- [On the Benefits of Populations on the Exploitation Speed of Standard Steady-State Genetic Algorithms](https://mlsanity.com/paper/1903.10976/) (2019)
- [How Crossover Speeds Up Building-Block Assembly in Genetic Algorithms](https://mlsanity.com/paper/1403.6600/) (2014)
- [Theoretical Analysis of Stochastic Search Algorithms](https://mlsanity.com/paper/1709.00890/) (2017)
- [Solving Problems with Unknown Solution Length at (Almost) No Extra Cost](https://mlsanity.com/paper/1506.05913/) (2015)

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

- [Hyper-Heuristics Can Profit From Global Variation Operators](https://mlsanity.com/paper/2407.14237/) (2024)
- [Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy](https://mlsanity.com/paper/2505.01647/) (2025)
- [Unlearning Works Better Than You Think: Local Reinforcement-Based Selection of Auxiliary Objectives](https://mlsanity.com/paper/2504.14418/) (2025)

## Abstract (arXiv)

Jump functions are the most-studied non-unimodal benchmark in the theory of randomized search heuristics, in particular, evolutionary algorithms (EAs). They have significantly improved our understanding of how EAs escape from local optima. However, their particular structure -- to leave the local optimum one can only jump directly to the global optimum -- raises the question of how representative such results are. For this reason, we propose an extended class textscJumpk,δ of jump functions that contain a valley of low fitness of width δ starting at distance k from the global optimum. We prove that several previous results extend to this more general class: for all k ≤ fracn1/3lnn and δ < k, the optimal mutation rate for the (1+1)~EA is fracδn, and the fast (1+1)~EA runs faster than the classical (1+1)~EA by a factor super-exponential in δ. However, we also observe that some known results do not generalize: the randomized local search algorithm with stagnation detection, which is faster than the fast (1+1)~EA by a factor polynomial in k on textscJumpk, is slower by a factor polynomial in n on some textscJumpk,δ instances. Computationally, the new class allows experiments with wider fitness valleys, especially when they lie further away from the global optimum.