Genetic algorithms in noisy environments

摘要

Genetic algorithms are adaptive search techniques which have been used to learn high-performance knowledge structures in reactive environments that provide information in the form of payoff. In general, payoff can be viewed as a noisy function of the structure being evaluated, and the learning task can be viewed as an optimization problem in a noisy environment. Previous studies have shown that genetic algorithms can perform effectively in the presence of noise. This work explores in detail the tradeoffs between the amount of effort spent on evaluating each structure and the number of structures evaluated during a given iteration of the genetic algorithm. Theoretical analysis shows that, in some cases, more efficient search results from less accurate evaluations. Further evidence is provided by a case study in which genetic algorithms are used to obtain good registrations of digital images.