Robustness of Populations in Stochastic Environments

Christian Gießen; Timo Kötzing

doi:10.1145/2576768.2598227

Robustness of Populations in Stochastic Environments

Christian Gießen, Timo Kötzing

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-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 language	English
Title of host publication	Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO'14)
Publisher	Association for Computing Machinery
Publication date	2014
Pages	1383-1390
ISBN (Electronic)	978-1-4503-2662-9
DOIs	https://doi.org/10.1145/2576768.2598227
Publication status	Published - 2014
Event	2014 Genetic and Evolutionary Computation Conference - Vancouver, Canada Duration: 12 Jul 2014 → 16 Jul 2014 http://www.sigevo.org/gecco-2014/index.html

Conference

Conference	2014 Genetic and Evolutionary Computation Conference
Country	Canada
City	Vancouver
Period	12/07/2014 → 16/07/2014
Internet address	http://www.sigevo.org/gecco-2014/index.html

Keywords

Run Time Analysis
Stochastic Fitness Function
Evolutionary Algorithm
Populations, Robustness

Access to Document

10.1145/2576768.2598227

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

Cite this

@inproceedings{16823f91c21f4323b6abc30f744b88c0,

title = "Robustness of Populations in Stochastic Environments",

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.",

keywords = "Run Time Analysis, Stochastic Fitness Function, Evolutionary Algorithm, Populations, Robustness",

author = "Christian Gie{\ss}en and Timo K{\"o}tzing",

year = "2014",

doi = "10.1145/2576768.2598227",

language = "English",

pages = "1383--1390",

booktitle = "Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO'14)",

publisher = "Association for Computing Machinery",

address = "United States",

note = "2014 Genetic and Evolutionary Computation Conference, GECCO 2014 ; Conference date: 12-07-2014 Through 16-07-2014",

url = "http://www.sigevo.org/gecco-2014/index.html",

}

TY - GEN

T1 - Robustness of Populations in Stochastic Environments

AU - Gießen, Christian

AU - Kötzing, Timo

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Run Time Analysis

KW - Stochastic Fitness Function

KW - Evolutionary Algorithm

KW - Populations, Robustness

U2 - 10.1145/2576768.2598227

DO - 10.1145/2576768.2598227

M3 - Article in proceedings

SP - 1383

EP - 1390

BT - Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO'14)

PB - Association for Computing Machinery

T2 - 2014 Genetic and Evolutionary Computation Conference

Y2 - 12 July 2014 through 16 July 2014

ER -