Markov Chain Models of Genetic Algorithms

Accepted by GECCO 99, 
Genetic and Evolutionary Computation Conference,
Orlando, Florida,  July 13-17, 1999.

Markov Chain Models of Genetic Algorithms

Alden H. Wright 
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
wright@cs.umt.edu
(406) 243-4790

   And

Yong Zhao
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
yzhao@cs.umt.edu
(406) 243-2883

ABSTRACT:
Nix and Vose modeled the simple genetic 
algorithm as a Markov chain, where the Markov chain states are 
populations.  Vose has extended this model to a "Random Heuristic 
Search" model of genetic (and other) algorithms where each individual 
of the next generation is selected from a probability distribution 
over individuals in the search space.  Many genetic algorithms do 
not fit this framework. The first part of this paper shows how 
to use Markov chains to model to a wider class of genetic algorithms, 
including steady state algorithms and algorithms that use a $(\mu + 
\lambda)$ selection strategy.  

Hill-climbing and strict hill-climbing evolutionary algorithms are 
defined,  and an asymptotic convergence rate is shown for a class 
of strict hill-climbing algorithms.  A strict hill-climbing no-mutation 
genetic algorithm is given that is guaranteed to converge to the 
optimum individual for separable fitness functions, and an expected 
time to convergence is proved.