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.
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 | |
| 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/Territory | Canada |
| City | Vancouver |
| Period | 12/07/2014 → 16/07/2014 |
| Internet address |
Keywords
- Run Time Analysis
- Stochastic Fitness Function
- Evolutionary Algorithm
- Populations, Robustness