Genetic Algorithms and the Variance of Fitness.

Abstract

this paper, we consider one important source of stochastic variation, the variance of a schema's fitness or what we call collateral noise. Specifically, a method for calculating fitness variance from a function's Walsh transform is derived and applied to a number of problems in GA analysis. In the remainder, Walsh functions and their application to the calculation of schema average fitness are reviewed; a formula for the calculation of schema fitness variance is derived using Walsh transforms. The variance computation is then applied to two important problems in genetic algorithm theory: population sizing and the calculation of rigorous probabilistic convergence bounds. Extending the technique to the analysis of nonuniform populations is also discussed. Re iew of als - c ema Anal sis