LINEAR-ANALYSIS OF GENETIC ALGORITHMS

We represent simple and fitness-scaled genetic algorithms by Markov ch ains on probability distributions over the set of all possible populat ions of a fixed finite size. Analysis of this formulation yields new i nsight into the geometric properties of the three phase mutation, cros sover, and fitness selection of a genetic algorithm by representing th em as stochastic matrices acting on the state space. This indicates ne w methods using mutation and crossover as the proposal scheme for simu lated annealing. We show by explicit estimates that for small mutation rates a genetic algorithm asymptotically spends most of its time in u niform populations regardless of crossover rate. The simple genetic al gorithm converges in the following sense: there exists a fully positiv e limit probability distribution over populations. This distribution i s independent of the choice of initial population. We establish strong ergodicity of the underlying inhomogeneous Markov chain for genetic a lgorithms that use any of a large class of fitness scaling methods inc luding linear fitness scaling, sigma-truncation, and power law scaling . Our analysis even allows for variation in mutation and crossover rat es according to a pre-determined schedule, where the mutation rate sta ys bounded away from zero. We show that the limit probability distribu tion of such a process is fully positive at all populations of uniform fitness. Consequently, genetic algorithms that use the above fitness scalings do not converge to a population containing only optimal membe rs. This answers a question of G. Rudolph (IEEE Trans. on Neural Netwo rks 5 (1994) 96-101). For a large set of fitness scaling methods, the limit distribution depends on the pre-order induced by the fitness fun ction f, i.e. c greater than or equal to c' double left right arrow f( c)greater than or equal to f(c') on possible creatures c and c', and n ot on the particular values assumed by the fitness function. (C) 1998- Elsevier Science B.V. All rights reserved.