Conference paper
(1+1) EA on Generalized Dynamic OneMax
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.
| Language: | English |
|---|---|
| Publisher: | Association for Computing Machinery |
| Year: | 2015 |
| Pages: | 40-51 |
| Proceedings: | 13th ACM Conference on Foundations of Genetic Algorithms XIII (FOGA '15)Workshop on Foundations of Genetic Algorithms |
| ISBN: | 1450334342 and 9781450334341 |
| Types: | Conference paper |
| DOI: | 10.1145/2725494.2725502 |
| ORCIDs: | Witt, Carsten |
