# Runtime Analysis for Self-adaptive Mutation Rates

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2018.

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

- [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)
- [Already Moderate Population Sizes Provably Yield Strong Robustness to Noise](https://mlsanity.com/paper/2404.02090/) (2024)
- [Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems](https://mlsanity.com/paper/2605.29916/) (2026)

## Abstract (arXiv)

We propose and analyze a self-adaptive version of the (1,λ) evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O(nλ/logλ+nlog n) when λ is at least C ln n for some constant C > 0. For all values of λ ≥ C ln n, this performance is asymptotically best possible among all λ-parallel mutation-based unbiased black-box algorithms. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr, Giessen, Witt, and Yang~(GECCO~2017) can be replaced by our simple endogenous scheme. On the technical side, the paper contributes new tools for the analysis of two-dimensional drift processes arising in the analysis of dynamic parameter choices in EAs, including bounds on occupation probabilities in processes with non-constant drift.