A Markov chain analysis on simple genetic algorithms

This paper addresses a Markov chain analysis of genetic algorithms (GAs), in particular for a variety called a modified elitist strategy. The modified elitist strategy generates the current population of M individuals by reserving the individual with the highest fitness value from the previous generation and generating M-1 individuals through a generation change. The author´s analysis is based on a Markov chain: by assuming a simple GA in which the genetic operation in the generation changes is restricted to selection, crossover, and mutation, and by evaluating the eigenvalues of the transition matrix of the Markov chain, the convergence rate of the GAs is computed in terms of a mutation probability μ. In this way, the authors show the probability that the population includes the individual with the highest fitness value is lower-bounded by 1-O(|λ*|ⁿ), |λ*|<1, where n is the number of the generation changes and λ* is a specified eigenvalue of the transition matrix. Furthermore, the choice of μ so as to minimize |λ*| is discussed