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

1 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, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally we show that a simple EDA called the Compact Genetic Algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.

Original languageEnglish (US)
Title of host publicationGECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference
EditorsTobias Friedrich
PublisherAssociation for Computing Machinery, Inc
Pages161-162
Number of pages2
ISBN (Electronic)9781450343237
DOIs
StatePublished - Jul 20 2016
Event2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion - Denver, United States
Duration: Jul 20 2016Jul 24 2016

Publication series

NameGECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference

Other

Other2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion
CountryUnited States
CityDenver
Period7/20/167/24/16

Keywords

  • Evolutionary algorithms
  • Noisy optimization
  • Run time analysis

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

Cite this