SECTION 4
A MARKOV CHAIN MODEL OF THE SIMPLE GENETIC ALGORITHM
4.1 Overview
From the discussion of the simple genetic algorithm operators in Section 3.2, it is
clear that the sequence of populations generated by the algorithm when executing on a
specified combinatorial optimization problem is a stochastic process (with finite state
space), and further that the conditional dependence of each population in the sequence on
its predecessors is completely described by its dependence upon the immediate predeces-
sor population. Thus, the sequence is a Markov chain (Definition Al). In this section, a
nonstationary Markov chain model of the simple genetic algorithm is developed for one,
two and three-operator variants of the algorithm. The model is tailored to resemble that
offered in Section 2.4.1 for simulated annealing. The one-operator genetic algorithm
model implements proportional reproduction only, while the two-operator variant
employs reproduction in combination with mutation. The three-operator algorithm imple-
ments reproduction, mutation and crossover. This model hierarchy is employed because it
provides some degree of insight into the effect that each operator has on the nature of the
state space of the resulting Markov chain.
Describing and analyzing the operation of the simple genetic algorithm is facilitated
by assuming that the underlying optimization problem is defined over a bit-string solution
space. This assumption is not essential and sacrifices very little generality. It is implem-
ented throughout the following sections.
4.2 The Markov Chain Model
Let a combinatorial optimization problem be characterized by the pair (S,R) where
S={0,1 )L and R is a strictly positive real valued reward function, and assume, with no