Robustness of Populations in Stochastic Environments

Christian Gießen, Timo Kötzing

Research output: Contribution to journalJournal articleResearchpeer-review


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
Issue number3
Pages (from-to)462-489
Publication statusPublished - 2016


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


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

Cite this