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

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion Cynhadledd › Trafodion Cynhadledd (Nid-Cyfnodolyn fathau)

4 Dyfyniadau (Scopus)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Teitl	GECCO '19
Is-deitl	Proceedings of the Genetic and Evolutionary Computation Conference Companion
Golygyddion	Manuel López-Ibáñez
Tudalennau	2068-2071
Nifer y tudalennau	4
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1145/3319619.3326906
Statws	Cyhoeddwyd - 13 Gorff 2019
Cyhoeddwyd yn allanol	Ie
Digwyddiad	GECCO 2019: The Genetic and Evolutionary Computation Conference - Prague, Y Weriniaeth Tsiec Hyd: 13 Gorff 2019 → 17 Gorff 2019 https://gecco-2019.sigevo.org

Cynhadledd

Cynhadledd	GECCO 2019: The Genetic and Evolutionary Computation Conference
Gwlad/Tiriogaeth	Y Weriniaeth Tsiec
Dinas	Prague
Cyfnod	13 Gorff 2019 → 17 Gorff 2019
Cyfeiriad rhyngrwyd	https://gecco-2019.sigevo.org

Mynediad at Ddogfen

10.1145/3319619.3326906

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

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

Dyfynnu hyn

@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. yn M López-Ibáñez (gol.), GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion. tt. 2068-2071, GECCO 2019: The Genetic and Evolutionary Computation Conference, Prague, Y Weriniaeth Tsiec, 13 Gorff 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. gol. / Manuel López-Ibáñez. 2019. t. 2068-2071.

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion Cynhadledd › Trafodion Cynhadledd (Nid-Cyfnodolyn fathau)

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

Crynodeb

Cynhadledd

Mynediad at Ddogfen

Cysylltiad parhaol

Ffeiliau eraill a chysylltiadau

Ôl bys

Dyfynnu hyn