title: On the Effectiveness of Sampling for Evolutionary Optimization in Noisy Environments.
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.
authors.affiliation: UBRI, School of Computer Science and Technology, University of Science and Technology of China, Hefei, 230027, China; National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China chaoqian@ustc.edu.cn.
authors.forename: Chao
authors.initials: C
authors.lastname: Qian
authors.affiliation: National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China yuy@nju.edu.cn.
authors.forename: Yang
authors.initials: Y
authors.lastname: Yu
authors.affiliation: UBRI, School of Computer Science and Technology, University of Science and Technology of China, Hefei, 230027, China ketang@ustc.edu.cn.
authors.forename: Ke
authors.initials: K
authors.lastname: Tang
authors.affiliation: Department of Computer Science, University of Surrey, Guildford, GU2 7XH, UK yaochu.jin@surrey.ac.uk.
authors.forename: Yaochu
authors.initials: Y
authors.lastname: Jin
authors.affiliation: UBRI, School of Computer Science and Technology, University of Science and Technology of China, Hefei, 230027, China; Center of Excellence for Research in Computational Intelligence and Applications, School of Computer Science, University of Birmingham, Birmingham, B15 2TT, UK x.yao@cs.bham.ac.uk.
authors.forename: Xin
authors.initials: X
authors.lastname: Yao
authors.affiliation: National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, China zhouzh@nju.edu.cn.
authors.forename: Zhi-Hua
authors.initials: ZH
authors.lastname: Zhou
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D006801:Humans; D008957:Models, Genetic
keywords: Robust optimization; computational complexity.; evolutionary algorithms; optimization in noisy environments; running time analysis