First Steps Towards a Runtime Analysis When Starting with a Good Solution

Denis Antipov, Maxim Buzdalov, Benjamin Doerr

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

21 Citations (SciVal)
20 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI
EditorsThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
PublisherSpringer Nature
Pages560-573
Number of pages14
ISBN (Electronic)978-3-030-58115-2
ISBN (Print)978-3-030-58114-5
DOIs
Publication statusPublished - 02 Sept 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume12270
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Theory
  • runtime analysis
  • initialization of evolutionary algorithms
  • crossover
  • fast mutation

Fingerprint

Dive into the research topics of 'First Steps Towards a Runtime Analysis When Starting with a Good Solution'. Together they form a unique fingerprint.

Cite this