Robustness of Populations in Stochastic Environments

Christian Gießen, Timo Kötzing

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We consider stochastic versions of OneMax and LeadingOnes and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the (1+1) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses. Most surprisingly, even small populations (of size Θ(logn)) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the (1+1) EA. Larger population sizes are even more beneficial; we consider both parent and offspring populations. In this sense, populations are robust in these stochastic settings.
Original languageEnglish
JournalAlgorithmica
Volume75
Issue number3
Pages (from-to)462-489
ISSN0178-4617
DOIs
Publication statusPublished - 2016

Keywords

  • Run time analysis
  • Stochastic fitness function
  • Evolutionary algorithm
  • Populations
  • Robustness

Fingerprint

Dive into the research topics of 'Robustness of Populations in Stochastic Environments'. Together they form a unique fingerprint.

Cite this