# Precise Runtime Analysis for Plateau Functions

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

## Key facts

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

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

- [The (1+(λ,λ)) Global SEMO Algorithm](https://mlsanity.com/paper/2210.03618/) (2022)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [The Runtime of Random Local Search on the Generalized Needle Problem](https://mlsanity.com/paper/2403.08153/) (2024)
- [Frequency Fitness Assignment: Optimization without Bias for Good Solutions can be Efficient](https://mlsanity.com/paper/2112.00229/) (2021)

## Abstract (arXiv)

To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the n-dimensional Plateauk function as natural benchmark and analyze how different variants of the (1 + 1) EA optimize it. The Plateauk function has a plateau of second-best fitness in a ball of radius k around the optimum. As evolutionary algorithm, we regard the (1 + 1) EA using an arbitrary unbiased mutation operator. Denoting by α the random number of bits flipped in an application of this operator and assuming that Pr[α = 1] has at least some small sub-constant value, we show the surprising result that for all constant k ≥ 2, the runtime T follows a distribution close to the geometric one with success probability equal to the probability to flip between 1 and k bits divided by the size of the plateau. Consequently, the expected runtime is the inverse of this number, and thus only depends on the probability to flip between 1 and k bits, but not on other characteristics of the mutation operator. Our result also implies that the optimal mutation rate for standard bit mutation here is approximately k/(en). Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.