The Linear Geometry of Genetic Operators with Applications to the Analysis of Genetic Drift and Genetic Algorithms Using Tournament Selection

We extend the results of the authors in [., (1998) 101-134] on the convergence of genetic algorithms with proportional fitness-scaled selection to genetic algorithms with various types of tournament fitness selection often used in practical applications. Our analysis allows for a general notion of fitness selection which includes types of fitness selection mechanisms where the fitness of the individual depends upon the population it lives in (such as frequency-dependent fitness selection). We also include a short analysis of the effect of genetic drift which has applications to the study of genetic algorithms with selection and crossover but without mutation. Genetic algorithms are represented by Markov chains on probability distributions over the set of all possible populations of a fixed finite size. Linear analysis of the stochastic matrices representing the three phases mutation, crossover, and fitness selection of a genetic algorithm — using, ., computation of spectra and Hilbert space techniques — yields new insight into the geometric properties of these phases. We show by explicit estimates, that for small mutation rates a genetic algorithm asymptotically spends most of its time in uniform populations regardless of the crossover rate. We show ergodicity of genetic algorithms using scaled multiple-bit mutation, and a wide range of fitness selection mechanisms which includes scaled proportional fitness selection, tournament fitness selection, and fitness selection mechanisms where the fitness of the individual depends upon the population it lives in. Our analysis permits varying mutation and crossover rates according to a pre-determined schedule, where the mutation rate stays bounded away from zero. If proportional fitness selection, tournament fitness selection or rank selection is used, then the limit probability distribution of such a process is fully positive at all populations of uniform fitness regardless of the fitness selection method and its possible scaling