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.