Robustness of Populations in Stochastic Environments

Christian Gießen, Timo Kötzing

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

Abstract

We consider stochastic versions of OneMax and Leading-Ones 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 _(log n)) 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 o_spring populations. In this sense, populations are robust in these stochastic settings.
Original languageEnglish
Title of host publicationProceedings of the 2014 conference on Genetic and evolutionary computation (GECCO'14)
PublisherAssociation for Computing Machinery
Publication date2014
Pages1383-1390
ISBN (Electronic)978-1-4503-2662-9
DOIs
Publication statusPublished - 2014
Event2014 Genetic and Evolutionary Computation Conference - Vancouver, Canada
Duration: 12 Jul 201416 Jul 2014
http://www.sigevo.org/gecco-2014/index.html

Conference

Conference2014 Genetic and Evolutionary Computation Conference
CountryCanada
CityVancouver
Period12/07/201416/07/2014
Internet address

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