Markov chain models of genetic algorithms
Alden H. Wright, Yong Rui Zhao · 1999
Nix and Vose [Nix and Vose, 1992] 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 (¯ + ) 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. Nix and Vose [Nix and ...