The product of that effort is a very general nonstationary Markov chain model for varia-
nts of the algorithm incorporating combinations of the three fundamental genetic algo-
rithm operators. The model is tailored to resemble the model employed in the analysis of
the simulated annealing algorithm convergence behavior, with the mutation probability
algorithm parameter playing a role analogous to absolute temperature in simulated
annealing.
Additionally, some salient features of the model state behavior are pointed out in
Section 4. In particular, the one-operator (reproduction only) simple genetic algorithm is
shown to possess exactly 2L absorbing states, one for each possible uniform population,
while the two-operator (reproduction/mutation) and three-operator (reproduction/muta-
tion/crossover) variants possess a unique stationary distribution. The expected value of
the absorption time for the one-operator algorithm is finite and an upper bound is pro-
vided by Eq. 4.8. The probability distribution of the final solution state produced by the
one-operator simple genetic algorithm depends upon the initial state, mo.
The inclusion of the mutation operator is shown in Section 4 to provide a significant
additional dimension to the state behavior of the time-homogeneous (stationary) two and
three-operator variants of the algorithm, the existence of a unique stationary distribution.
The significance of the unique stationary distribution is that the asymptotic state behavior
is independent of the starting state. It is completely determined by the objective function
and the algorithm parameters.
In Section 5, the genetic algorithm model is employed to generate some computer
simulation results. Specifically, a combinatorial interpretation of the model state space is
explored numerically in Section 5.2 and the limiting stationary distribution of the three
operator algorithm is approximated for a variety of algorithm parameter sets in Section
5.5. A very significant feature of the limiting stationary distribution is suggested by the
Section 5.5 results and later verified theoretically (in Section 7). It is that the limiting two
and three-operator algorithm stationary distribution behavior necessary for extrapolating