Fixed-target runtime analysis

Maxim Buzdalov, Benjamin Doerr, Carola Doerr, Dmitry Vinokurov

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

11 Citations (SciVal)

Abstract

Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and a theoretical viewpoint, more fine-grained performance measures are needed. Two complementary approaches have been suggested: fixed-budget analysis and fixed-target analysis.

In this work, we conduct an in-depth study on the advantages and limitations of fixed-target analyses. We show that, different from fixed-budget analyses, many classical methods from the runtime analysis of discrete evolutionary algorithms yield fixed-target results without greater effort. We use this to conduct a number of new fixed-target analyses. However, we also point out examples where an extension of the existing runtime result to a fixed-target result is highly non-trivial.
Original languageEnglish
Title of host publicationGECCO '20
Subtitle of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Pages1295-1303
Number of pages9
ISBN (Print)978-1-4503-7128-5
DOIs
Publication statusPublished - 26 Jun 2020
Externally publishedYes
EventGECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mexico
Duration: 08 Jul 202012 Jul 2020

Conference

ConferenceGECCO 2020 - Genetic and Evolutionary Computation Conference
Country/TerritoryMexico
CityCancun
Period08 Jul 202012 Jul 2020

Keywords

  • fixed-budget analysis
  • fixed-target analysis
  • runtime analysis

Fingerprint

Dive into the research topics of 'Fixed-target runtime analysis'. Together they form a unique fingerprint.

Cite this