Precise runtime analysis for plateaus

To gain a better theoretical understanding of how evolutionary algorithms cope with plateaus of constant fitness, we analyze how the (1 + 1) EA optimizes the n-dimensional Plateau_k function. This function has a plateau of second-best fitness in a radius of k around the optimum. As optimization 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 (formula presented), we show the surprising result that for k ≥ 2 the expected optimization time of this algorithm is (formula presented) that is, the size of the plateau times the expected waiting time for an iteration flipping between 1 and k bits. Our result implies that the optimal mutation rate for this function 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.