(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

454 Downloads (Pure)


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
ISBN (Print)978-1-4503-3434-1
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


Conference13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)
Country/TerritoryUnited Kingdom
CityAberystwyth, Wales
Internet address


  • Evolutionary computation
  • Dynamic Optimization
  • Drift
  • Theory


Dive into the research topics of '(1+1) EA on Generalized Dynamic OneMax'. Together they form a unique fingerprint.

Cite this