On the Effectiveness of Sampling
for Evolutionary Optimization in Noisy Environments
Chao Qian
1
,YangYu
1
, Yaochu Jin
2
, and Zhi-Hua Zhou
1
1
National Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing 210023, China
2
Department of Computing, University of Surrey, Guildford, Surrey, GU2 7XH, UK
{qianc,yuy,zhouzh}@lamda.nju.edu.cn, 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 in-
creasing the computation cost. Many studies focused on designing efficient sam-
pling 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 condi-
tion 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 perfor-
mance 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.
1 Introduction
Evolutionary algorithms (EAs) [4] inspired from natural phenomena are often applied
to solve real-world optimization problems, where the fitness (i.e., objective) evaluation
of a solution is usually noisy. For example, in airplane design, the fitness of every pro-
totype is evaluated by a stochastic computer simulation, and thus is a random variable
whose value can be different from the exact fitness. Handling noise in fitness evalua-
tions is important in that a poor solution can appear to be good due to the noise, which
can mislead the search direction, resulting in an inefficient optimization. Many studies
thus have focused on dealing with noise in evolutionary optimization [2,6,18].
One simple and direct way to reduce the effect of noise is sampling, which samples
the fitness of one solution several times and then uses the average to estimate the true
fitness. An n-time random sampling can reduce the standard deviation by a factor of
√
n, and thus makes the fitness estimation closer to the true value, while also increasing
the computation cost n times. Much effort has been devoted to designing smarter sam-
pling approaches, which dynamically decide the sample size for each solution so that
the sampling cost is reduced as much as possible.
This research was supported by the National Science Foundation of China (61375061,
61333014) and the Jiangsu Science Foundation (BK2012303).
T. Bartz-Beielstein et al. (Eds.): PPSN XIII 2014, LNCS 8672, pp. 302–311, 2014.
c
Springer International Publishing Switzerland 2014