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 a the random number of bits flipped in an application of this operator and assuming Pr[alpha = 1] = Omega(1), we show the surprising result that for k >= 2 the expected optimization time of this algorithm is n(k)/k!Pr[1 <= alpha <= k] (1 + o(1)). 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.