The compact genetic algorithm is efficient under extreme Gaussian noise

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

Research output: Contribution to journalArticlepeer-review

49 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)
Article number7577782
Pages (from-to)477-490
Number of pages14
JournalIEEE Transactions on Evolutionary Computation
Volume21
Issue number3
DOIs
StatePublished - Jun 2017

Keywords

  • Evolutionary algorithms
  • Noisy optimization
  • Run time analysis

Fingerprint

Dive into the research topics of 'The compact genetic algorithm is efficient under extreme Gaussian noise'. Together they form a unique fingerprint.

Cite this