## 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.