In noisy evolutionary optimization, sampling is a common strategy to deal with noise. By the sampling strategy, the fitness of a solution is evaluated multiple times (called sample size) independently, and its true fitness is then approximated by the average of these evaluations. Most previous studies on sampling are empirical, and the few theoretical studies mainly showed the effectiveness of sampling with a sufficiently large sample size. In this paper, we theoretically examine what strategies can work when sampling with any fixed sample size fails. By constructing a family of artificial noisy examples, we prove that sampling is always ineffective, while using parent or offspring populations can be helpful on some examples. We also construct an artificial noisy example to show that when using neither sampling nor populations is effective, a tailored adaptive sampling (i.e., sampling with an adaptive sample size) strategy can work. These findings may enhance our understanding of sampling to some extent, but future work is required to validate them in natural situations. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.
Bibliographical noteWe want to thank the anonymous reviewers of GECCO’18, TEvC and Algorithmica for their valuable comments and thank Per Kristian Lehre for helpful discussions. This work was supported by the National Key Research and Development Program of China (2017YFB1003102), the NSFC (61672478, 61876077), the Shenzhen Peacock Plan (KQTD2016112514355531), and the Fundamental Research Funds for the Central Universities.
- Adaptive sampling
- Evolutionary algorithms
- Noisy optimization
- Running time analysis