# A Rigorous Runtime Analysis of the (1 + (λ, λ)) GA on Jump Functions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2020.

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

- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [Using Automated Algorithm Configuration for Parameter Control](https://mlsanity.com/paper/2302.12334/) (2023)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [Runtime Analysis for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2207.04045/) (2022)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)

## Abstract (arXiv)

The (1 + (λ,λ)) genetic algorithm is a younger evolutionary algorithm trying to profit also from inferior solutions. Rigorous runtime analyses on unimodal fitness functions showed that it can indeed be faster than classical evolutionary algorithms, though on these simple problems the gains were only moderate. In this work, we conduct the first runtime analysis of this algorithm on a multimodal problem class, the jump functions benchmark. We show that with the right parameters, the ollga optimizes any jump function with jump size 2 ≤ k ≤ n/4 in expected time O(n(k+1)/2 eO(k) k-k/2), which significantly and already for constant~k outperforms standard mutation-based algorithms with their Theta(nk) runtime and standard crossover-based algorithms with their tildeO(nk-1) runtime guarantee. For the isolated problem of leaving the local optimum of jump functions, we determine provably optimal parameters that lead to a runtime of (n/k)k/2 eTheta(k). This suggests some general advice on how to set the parameters of the ollga, which might ease the further use of this algorithm.