Fixed-target runtime analysis of the (1 + 1) EA with resampling

Dmitry Vinokurov, Maxim Buzdalov, Arina Buzdalova, Benjamin Doerr, Carola Doerr

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

Abstract

We conduct a fixed-target runtime analysis of (1 + 1) EA with resampling on the OneMax and BinVal problems. For OneMax, our fixed-target upper bound refines the previously known bound. Our fixed-target lower bound for OneMax is the first of this kind. We also consider linear functions and show that the traditional approaches via drift analysis cannot easily be extended to yield fixed-target results. However, for the particular case of BinVal, a relatively precise fixed-target bound is obtained.
Original languageEnglish
Title of host publicationGECCO '19
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference Companion
EditorsManuel López-Ibáñez
Pages2068-2071
Number of pages4
DOIs
Publication statusPublished - 13 Jul 2019
Externally publishedYes
EventGECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019
https://gecco-2019.sigevo.org

Conference

ConferenceGECCO 2019: The Genetic and Evolutionary Computation Conference
Country/TerritoryCzech Republic
CityPrague
Period13 Jul 201917 Jul 2019
Internet address

Keywords

  • drift analysis
  • fixed-target analysis
  • resampling
  • runtime analysis

Fingerprint

Dive into the research topics of 'Fixed-target runtime analysis of the (1 + 1) EA with resampling'. Together they form a unique fingerprint.

Cite this