Analysis of Noisy Evolutionary Optimization When Sampling Fails
This work addresses a theoretical gap in noisy optimization for researchers, but it is incremental as it builds on existing studies with artificial examples.
The paper theoretically analyzes strategies for noisy evolutionary optimization when fixed sample size sampling fails, proving that sampling is ineffective while parent or offspring populations can help in some cases, and showing that tailored adaptive sampling works when other methods fail.
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 \emph{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.