Back to Search
Start Over
On the Effectiveness of Sampling for Evolutionary Optimization in Noisy Environments.
- Source :
-
Evolutionary computation [Evol Comput] 2018 Summer; Vol. 26 (2), pp. 237-267. Date of Electronic Publication: 2016 Dec 16. - Publication Year :
- 2018
-
Abstract
- In real-world optimization tasks, the objective (i.e., fitness) function evaluation is often disturbed by noise due to a wide range of uncertainties. Evolutionary algorithms are often employed in noisy optimization, where reducing the negative effect of noise is a crucial issue. Sampling is a popular strategy for dealing with noise: to estimate the fitness of a solution, it evaluates the fitness multiple ([Formula: see text]) times independently and then uses the sample average to approximate the true fitness. Obviously, sampling can make the fitness estimation closer to the true value, but also increases the estimation cost. Previous studies mainly focused on empirical analysis and design of efficient sampling strategies, while the impact of sampling is unclear from a theoretical viewpoint. In this article, we show that sampling can speed up noisy evolutionary optimization exponentially via rigorous running time analysis. For the (1[Formula: see text]1)-EA solving the OneMax and the LeadingOnes problems under prior (e.g., one-bit) or posterior (e.g., additive Gaussian) noise, we prove that, under a high noise level, the running time can be reduced from exponential to polynomial by sampling. The analysis also shows that a gap of one on the value of [Formula: see text] for sampling can lead to an exponential difference on the expected running time, cautioning for a careful selection of [Formula: see text]. We further prove by using two illustrative examples that sampling can be more effective for noise handling than parent populations and threshold selection, two strategies that have shown to be robust to noise. Finally, we also show that sampling can be ineffective when noise does not bring a negative impact.
- Subjects :
- Humans
Algorithms
Biological Evolution
Models, Genetic
Subjects
Details
- Language :
- English
- ISSN :
- 1530-9304
- Volume :
- 26
- Issue :
- 2
- Database :
- MEDLINE
- Journal :
- Evolutionary computation
- Publication Type :
- Academic Journal
- Accession number :
- 27982697
- Full Text :
- https://doi.org/10.1162/EVCO_a_00201