Precise Runtime Analysis for Plateaus
share
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 [α = 1] = Ω(1), we show the surprising result that for k > 2 the expected optimization time of this algorithm is n^k/k), 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.
READ FULL TEXT