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

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

doi:10.1145/3319619.3326906

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 proceeding › Conference Proceeding (Non-Journal item)

4 Citations (Scopus)

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 language	English
Title of host publication	GECCO '19
Subtitle of host publication	Proceedings of the Genetic and Evolutionary Computation Conference Companion
Editors	Manuel López-Ibáñez
Pages	2068-2071
Number of pages	4
DOIs	https://doi.org/10.1145/3319619.3326906
Publication status	Published - 13 Jul 2019
Externally published	Yes
Event	GECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 https://gecco-2019.sigevo.org

Conference

Conference	GECCO 2019: The Genetic and Evolutionary Computation Conference
Country/Territory	Czech Republic
City	Prague
Period	13 Jul 2019 → 17 Jul 2019
Internet address	https://gecco-2019.sigevo.org

Keywords

drift analysis
fixed-target analysis
resampling
runtime analysis

Access to Document

10.1145/3319619.3326906

Permanent link

Persistent link

Cite this

@inproceedings{8fde2d35262a460199479b5e8799fa5f,

title = "Fixed-target runtime analysis of the (1 + 1) EA with resampling",

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

keywords = "drift analysis, fixed-target analysis, resampling, runtime analysis",

author = "Dmitry Vinokurov and Maxim Buzdalov and Arina Buzdalova and Benjamin Doerr and Carola Doerr",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3319619.3326906",

language = "English",

isbn = "978-1-4503-6748-6",

pages = "2068--2071",

editor = "L{\'o}pez-Ib{\'a}{\~n}ez, {Manuel }",

booktitle = "GECCO '19",

note = "GECCO 2019: The Genetic and Evolutionary Computation Conference ; Conference date: 13-07-2019 Through 17-07-2019",

url = "https://gecco-2019.sigevo.org",

}

Vinokurov, D, Buzdalov, M , Buzdalova, A, Doerr, B & Doerr, C 2019, Fixed-target runtime analysis of the (1 + 1) EA with resampling. in M López-Ibáñez (ed.), GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion. pp. 2068-2071, GECCO 2019: The Genetic and Evolutionary Computation Conference, Prague, Czech Republic, 13 Jul 2019. https://doi.org/10.1145/3319619.3326906

Fixed-target runtime analysis of the (1 + 1) EA with resampling. / Vinokurov, Dmitry; Buzdalov, Maxim ; Buzdalova, Arina et al.
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion. ed. / Manuel López-Ibáñez. 2019. p. 2068-2071.

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

TY - GEN

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

AU - Vinokurov, Dmitry

AU - Buzdalov, Maxim

AU - Buzdalova, Arina

AU - Doerr, Benjamin

AU - Doerr, Carola

PY - 2019/7/13

Y1 - 2019/7/13

N2 - 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.

AB - 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.

KW - drift analysis

KW - fixed-target analysis

KW - resampling

KW - runtime analysis

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85070627818&origin=resultslist

U2 - 10.1145/3319619.3326906

DO - 10.1145/3319619.3326906

M3 - Conference Proceeding (Non-Journal item)

SN - 978-1-4503-6748-6

SP - 2068

EP - 2071

BT - GECCO '19

A2 - López-Ibáñez, Manuel

T2 - GECCO 2019: The Genetic and Evolutionary Computation Conference

Y2 - 13 July 2019 through 17 July 2019

ER -

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

Abstract

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this