Resampling vs recombination: A statistical run time estimation

Tobias Friedrich, Timo Kötzing, Francesco Quinzan, Andrew M. Sutton

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

2 Scopus citations

Abstract

Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noisehandling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-off between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutationonly evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.

Original languageEnglish (US)
Title of host publicationFOGA 2017 - Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
PublisherAssociation for Computing Machinery, Inc
Pages25-35
Number of pages11
ISBN (Electronic)9781450346511
DOIs
StatePublished - Jan 12 2017
Event14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA 2017 - Copenhagen, Denmark
Duration: Jan 12 2017Jan 15 2017

Other

Other14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA 2017
CountryDenmark
CityCopenhagen
Period1/12/171/15/17

Keywords

  • Ant colony optimization
  • Crossover
  • Estimation of distribution algorithm
  • Evolutionary algorithm
  • Genetic algorithm
  • Noise
  • Robustness

Fingerprint Dive into the research topics of 'Resampling vs recombination: A statistical run time estimation'. Together they form a unique fingerprint.

Cite this