On Convergence Rate of a Class of Genetic Algorithms

Studying convergence rate of a genetic algorithm is a very important but a nontrivial task. The more accurate estimation of convergence rate for genetic algorithms can be used to design the more efficient control parameters of algorithms, and to point out the correct direction to improve the algorithms. Moreover, one good measure of convergence rate can be used to judge the efficiency of different algorithms. The existing results about the convergence rate for genetic algorithms can be classified into two types. One type is based on Doeblin condition in which some parameters should be estimated. The other type needs to estimate the eigenvalues of the state transition matrix. However, these parameters are difficult to estimate. In this paper, we first formulate a model for a class of genetic algorithms, and then analyze the convergence rate of such an algorithm in a different way. It shows that their convergence rate is linear based on property of Markov chain.