Genetic Algorithms and the Variance of Fitness
David E. Goldberg Department of General Engineering,
University of Illinois at Urbana-Champaign,
Urbana, IL 61801-2996, USA
Mike Rudnick Department of Computer Science and Engineering,
Oregon Graduate Institute, Beaverton, OR 97006-1999, USA
Abstract
This paper presents a method for calculating the variance of schema fitness using Walsh transforms. The computation is important for understanding the performance of genetic algorithms (GAs) because most GAs depend on the sampling of schema fitness in populations of modest size, and the variance of schema fitness is a primary source of noise that can prevent proper evaluation of building blocks, thereby causing convergence to other-than-global optima. The paper also applies these calculations to the sizing of GA populations and to the adjustment of the schema theorem to account for fitness variance; the extension of the variance computation to nonuniform populations is also considered. Taken together these results may be viewed as a step along the road to rigorous convergence proofs for recombinative genetic algorithms.
