  To gain a better theoretical understanding of how evolutionary algorithms
(EAs) cope with plateaus of constant fitness, we propose the $n$-dimensional
Plateau$_k$ function as natural benchmark and analyze how different variants of
the $(1 + 1)$ EA optimize it. The Plateau$_k$ 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 $\alpha$ the random number of bits flipped in an
application of this operator and assuming that $\Pr[\alpha = 1]$ has at least
some small sub-constant value, we show the surprising result that for all
constant $k \ge 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.
