(1+1) EA on Generalized Dynamic OneMax

Timo  Kötzing; Andrei Lissovoi; Carsten Witt

doi:10.1145/2725494.2725502

(1+1) EA on Generalized Dynamic OneMax

Timo Kötzing, Andrei Lissovoi, Carsten Witt

Department of Applied Mathematics and Computer Science

Friedrich Schiller University Jena

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

633 Downloads (Pure)

Abstract

Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension.

Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.

Original language	English
Title of host publication	Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)
Publisher	Association for Computing Machinery
Publication date	2015
Pages	40-51
ISBN (Print)	978-1-4503-3434-1
DOIs	https://doi.org/10.1145/2725494.2725502
Publication status	Published - 2015
Event	13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15) - Aberystwyth, Wales, United Kingdom Duration: 17 Jan 2015 → 20 Jan 2015 Conference number: 13 http://foga2015.dcs.aber.ac.uk/index.html

Conference

Conference	13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)
Number	13
Country/Territory	United Kingdom
City	Aberystwyth, Wales
Period	17/01/2015 → 20/01/2015
Internet address	http://foga2015.dcs.aber.ac.uk/index.html

Keywords

Evolutionary computation
Dynamic Optimization
Drift
Theory

Access to Document

10.1145/2725494.2725502

Dynamic onemax FinalSubmittedAccepted author manuscript, 348 KB

OpenUrl availability

Full text

Cite this

@inproceedings{54479c6ca7af4fe0afbcd9b70b62c2d8,

title = "(1+1) EA on Generalized Dynamic OneMax",

abstract = "Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension.Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.",

keywords = "Evolutionary computation, Dynamic Optimization, Drift, Theory",

author = "Timo K{\"o}tzing and Andrei Lissovoi and Carsten Witt",

year = "2015",

doi = "10.1145/2725494.2725502",

language = "English",

isbn = "978-1-4503-3434-1",

pages = "40--51",

booktitle = "Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)",

publisher = "Association for Computing Machinery",

address = "United States",

note = "13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15), FOGA 2015 ; Conference date: 17-01-2015 Through 20-01-2015",

url = "http://foga2015.dcs.aber.ac.uk/index.html",

}

Kötzing, T, Lissovoi, A & Witt, C 2015, (1+1) EA on Generalized Dynamic OneMax. in Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15). Association for Computing Machinery, pp. 40-51, 13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15), Aberystwyth, Wales, United Kingdom, 17/01/2015. https://doi.org/10.1145/2725494.2725502

TY - GEN

T1 - (1+1) EA on Generalized Dynamic OneMax

AU - Kötzing, Timo

AU - Lissovoi, Andrei

AU - Witt, Carsten

N1 - Conference code: 13

PY - 2015

Y1 - 2015

N2 - Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension.Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.

AB - Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension.Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.

KW - Evolutionary computation

KW - Dynamic Optimization

KW - Drift

KW - Theory

U2 - 10.1145/2725494.2725502

DO - 10.1145/2725494.2725502

M3 - Article in proceedings

SN - 978-1-4503-3434-1

SP - 40

EP - 51

BT - Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)

PB - Association for Computing Machinery

T2 - 13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)

Y2 - 17 January 2015 through 20 January 2015

ER -

(1+1) EA on Generalized Dynamic OneMax

Abstract

Conference

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this