The benefit of recombination in noisy evolutionary search

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Andrew M. Sutton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

20 Scopus citations

Abstract

Practical optimization problems frequently include uncertainty about the quality measure, for example due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings meta-heuristics are a popular choice for deriving good optimization algorithms, most notably evolutionary algorithms which mimic evolution in nature. Empirical evidence suggests that genetic recombination is useful in uncertain environments because it can stabilize a noisy fitness signal. With this paper we want to support this claim with mathematical rigor. The setting we consider is that of noisy optimization. We study a simple noisy fitness function that is derived by adding Gaussian noise to a monotone function. First, we show that a classical evolutionary algorithm that does not employ sexual recombination (the (μ+1)-EA) cannot handle the noise efficiently, regardless of the population size. Then we show that an evolutionary algorithm which does employ sexual recombination (the Compact Genetic Algorithm, short: cGA) can handle the noise using a graceful scaling of the population.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
EditorsKhaled Elbassioni, Kazuhisa Makino
PublisherSpringer- Verlag
Pages140-150
Number of pages11
ISBN (Print)9783662489703
DOIs
StatePublished - Jan 1 2015
Externally publishedYes
Event26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Japan
Duration: Dec 9 2015Dec 11 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9472
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other26th International Symposium on Algorithms and Computation, ISAAC 2015
CountryJapan
CityNagoya
Period12/9/1512/11/15

Fingerprint Dive into the research topics of 'The benefit of recombination in noisy evolutionary search'. Together they form a unique fingerprint.

Cite this