Analysis of Noisy Evolutionary Optimization When Sampling Fails

Chao QIAN, Chao BIAN, Yang YU, Ke TANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

9 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)940-975
Number of pages36
JournalAlgorithmica
Volume83
Issue number4
Early online date20 Jan 2020
DOIs
Publication statusPublished - Apr 2021
Externally publishedYes

Bibliographical note

We 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.

Keywords

  • Adaptive sampling
  • Evolutionary algorithms
  • Noisy optimization
  • Population
  • Running time analysis
  • Sampling

Fingerprint

Dive into the research topics of 'Analysis of Noisy Evolutionary Optimization When Sampling Fails'. Together they form a unique fingerprint.

Cite this