@inproceedings{37c1920bb79442849ffe8d9f8eae6713,
title = "First Steps Towards a Runtime Analysis When Starting with a Good Solution",
abstract = "The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of the algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the (1+1) evolutionary algorithm and the static, self-adjusting, and heavy-tailed (1+(λ,λ)) GA on the OneMax benchmark, but we are optimistic that the question how to profit from good initial solutions is interesting beyond these first examples.",
keywords = "Theory, runtime analysis, initialization of evolutionary algorithms, crossover, fast mutation",
author = "Denis Antipov and Maxim Buzdalov and Benjamin Doerr",
note = "Funding Information: Acknowledgements. This work was supported by the Government of Russian Federation, grant number 08-08, and by a public grant as part of the Investissement d{\textquoteright}avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gas-pard Monge Program for optimization, operations research and their interactions with data sciences. Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020.",
year = "2020",
month = sep,
day = "2",
doi = "10.1007/978-3-030-58115-2_39",
language = "English",
isbn = "978-3-030-58114-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer Nature",
pages = "560--573",
editor = "Thomas B{\"a}ck and Mike Preuss and Andr{\'e} Deutz and Michael Emmerich and Hao Wang and Carola Doerr and Heike Trautmann",
booktitle = "Parallel Problem Solving from Nature – PPSN XVI",
address = "Switzerland",
}