On the Mean of the Second Largest Eigenvalueon the Convergence Rate of Genetic Algorithms

Genetic algorithms are sometimes disparagingly denoted as just a fancier form of a plain, stupidheuristic. One of the main reasons for this kind of critique is that users believed a GA could notguarantee global convergence in a certain amount of time.Because the proof of global convergence of GAs using elitism has been performed elsewhere (11),in this work we want to extend previous work by J. Suzuki (13) and focus on the identication of thedeterminants that inuence the convergence rate of genetic algorithms. The convergence rate of geneticalgorithms is addressed using Markov chain analysis. Therefore, we could describe an elitist GA usingmutation, recombination and selection as a discrete stochastic process. Evaluating the eigenvalues of thetransition matrix of the Markov chain we can prove that the convergence rate of a GA is determined bythe second largest eigenvalue of the transition matrix. The proof is rst performed for diagonalizabletransition matrices and then transferred to matrices in Jordan normal form.[...]