 |
    |
On the Effectiveness of Sampling for Evolutionary Optimization in Noisy Environments*
Chao Qian1, Yang Yu1, Yaochu Jin2, and Zhi-Hua Zhou1
1National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China
qianc@lamda.nju.edu.cn
yuy@lamda.nju.edu.cn
zhouzh@lamda.nju.edu.cn
2Department of Computing, University of Surrey, Guildford, Surrey, GU2 7XH, UK
yaochu.jin@surrey.ac.uk
Abstract. Sampling has been often employed by evolutionary algorithms to cope with noise when solving noisy real-world optimization problems. It can improve the estimation accuracy by averaging over a number of samples, while also increasing the computation cost. Many studies focused on designing efficient sampling methods, and conflicting empirical results have been reported. In this paper, we investigate the effectiveness of sampling in terms of rigorous running time, and find that sampling can be ineffective. We provide a general sufficient condition under which sampling is useless (i.e., sampling increases the running time for finding an optimal solution), and apply it to analyzing the running time performance of (1+1)-EA for optimizing OneMax and Trap problems in the presence of additive Gaussian noise. Our theoretical analysis indicates that sampling in the above examples is not helpful, which is further confirmed by empirical simulation results.
*This research was supported by the National Science Foundation of China (61375061, 61333014) and the Jiangsu Science Foundation (BK2012303).
LNCS 8672, p. 302 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014