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 language||English (US)|
|Title of host publication||GECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference|
|Publisher||Association for Computing Machinery, Inc|
|Number of pages||2|
|State||Published - Jul 20 2016|
|Event||2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion - Denver, United States|
Duration: Jul 20 2016 → Jul 24 2016
|Name||GECCO 2016 Companion - Proceedings of the 2016 Genetic and Evolutionary Computation Conference|
|Other||2016 Genetic and Evolutionary Computation Conference, GECCO 2016 Companion|
|Period||7/20/16 → 7/24/16|
Bibliographical notePublisher Copyright:
© 2016 Copyright held by the owner/author(s).
Copyright 2017 Elsevier B.V., All rights reserved.
- Evolutionary algorithms
- Noisy optimization
- Run time analysis