Efficient fitness estimation in noisy environments

Abstract

In noisy environments, an individual's fitness cannot be evaluated precisely, but its tness has to be estimated. Evolutionary Algorithms are generally believed to be able to cope well with a stochastic fitness function because promising areas of the search space are sampled several times, thus an estimation error has limited effect. Nevertheless, methods to improve the estimation accuracy should help to speed up evolution. In this paper, we suggest to use local regression for estimation, taking the fitness of neighboring individuals into account. As a side-product of this approach, we also obtain information on the gradient of the fitness landscape, which may then additionally be used to perform local hill-climbing.