(1+1) EA on Generalized Dynamic OneMax

Timo Kötzing, Andrei Lissovoi, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

224 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 languageEnglish
Title of host publicationProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)
PublisherAssociation for Computing Machinery
Publication date2015
Pages40-51
ISBN (Print)978-1-4503-3434-1
DOIs
Publication statusPublished - 2015
Event13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15) - Aberystwyth, Wales, United Kingdom
Duration: 17 Jan 201520 Jan 2015
Conference number: 13
http://foga2015.dcs.aber.ac.uk/index.html

Conference

Conference13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)
Number13
CountryUnited Kingdom
CityAberystwyth, Wales
Period17/01/201520/01/2015
Internet address

Keywords

  • Evolutionary computation
  • Dynamic Optimization
  • Drift
  • Theory

Cite this

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) (pp. 40-51). Association for Computing Machinery. https://doi.org/10.1145/2725494.2725502