@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",

}