A Markov chain analysis on simple genetic algorithms

Publisher Website
Google Scholar
Abstract
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-l individuals through a generation change, Our 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 mu. In this way, we show the probability that the population includes the individual with the highest fitness value is lower-bounded by 1 - O(\lambda*\(n)), \lambda*\ < 1, where n is the number of the generation changes and lambda* is a specified eigenvalue of the transition matrix, Furthermore, the choice of mu so as to minimize \lambda*\ is discussed.

This publication has 6 references indexed in Scilit: