Fundamental Study Theory of genetic algorithms
Lothar M. Schmitt · 2001
(i) We investigate spectral andgeometric properties of the mutation-crossover operator in a genetic algorithm with general-size alphabet. By computing spectral estimates, we show how the crossover operator enhances the averaging procedure of the mutation operator in the random generator phase of the genetic algorithm. By mapping our model to the multi-set model often investigatedin the literature, we compute correspond ing spectral estimates for mutation-crossover in the multi-set model. (ii) Various types of unscaledor scaled5tness selection mechanisms are consid eredsuch as proportional 5tness selection, rank selection, andtournament 5tness selection. We allow 5tness selection mechanisms where the 5tness of an individual or creature depends upon the population it resides in. We investigate contracting properties of these 5tness selection mechanisms and combine them with the crossover operator to obtain a model for genetic drift. This has applications to the study of genetic algorithms with zero or extremely low mutation rate. (iii) We discuss a variety of convergent simulated-annealing-type algorithms with mutationcrossover as generator matrix. (iv) The theory includes proof of strong ergodicity for various types of scaled genetic algorithms using common 5tness selection methods. If the mutation rate converges to a positive value, andthe other operators of the genetic algorithm converge, then the limit probability d istribution over populations is fully positive at uniform populations whose members have not necessarily optimal 5tness. (v) In what follows, suppose the mutation rate converges to zero su6ciently slow to assure weak ergodicity of the inhomogeneous Markov chain describing the genetic algorithm, unbounded power-law scaling for the 5tness selection is used , mutation andcrossover commute, andthe 5tness function is injective which is a minor restriction in regardto function optimization. (va) If a certain integrable convergence condition is satis5ed such that the selection pressure increases fast, then there is essentially no other restriction on the crossover operation, andthe algorithm asymptotically behaves as the following take-the-best search algorithm: (1) mutate