@inproceedings{416b9c117fc244baa3c97e778afbf3dc,
title = "Precise runtime analysis for plateaus",
abstract = "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 Plateauk 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.",
keywords = "Markov chains, Mutation, Runtime analysis, Theory",
author = "Denis Antipov and Benjamin Doerr",
note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 15th International Conference on Parallel Problem Solving from Nature, PPSN 2018 ; Conference date: 08-09-2018 Through 12-09-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-99259-4\_10",
language = "English",
isbn = "9783319992587",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "117--128",
editor = "Fonseca, \{Carlos M.\} and Nuno Lourenco and Penousal Machado and Luis Paquete and Anne Auger and Darrell Whitley",
booktitle = "Parallel Problem Solving from Nature – PPSN XV - 15th International Conference, 2018, Proceedings",
}