the simulated annealing asymptotic global optimality result does not follow. The limiting
distribution is nonzero for all states corresponding to uniform populations (one-operator
absorbing states), including those representing sub-optimal solutions. This complication
precludes an exact extrapolation of the simulated annealing convergence theory onto the
simple genetic algorithm. The Section 5 results do however reinforce the intuitive notion
that increasing the algorithm population size parameter biases the limiting distribution
towards the desired limiting behavior.
Section 6 employs the Perron-Frobenius Theorem (which is summarized in Appen-
dix B) to formulate the time-homogeneous two and three-operator algorithm unique sta-
tionary distribution existence argument into a system of equations whose solution is the
stationary distribution components. The solution is formulated in terms of Cramer's Rule,
and is not explicitly solved, however the Section 6 results provide a remarkable degree of
insight into the form of the solution and its behavior with respect to the algorithm param-
eters. Those results provide the foundation for the remaining sections.
The unique stationary distribution existence argument for the stationary two and
three-operator algorithm variants only applies when the mutation probability parameter is
strictly greater than zero. A one-operator (zero mutation probability) stationary distribu-
tion exists but as demonstrated in Section 4.3.1 it is not unique. A very important require-
ment for extrapolation of the simulated annealing convergence theory onto the simple
genetic algorithm is existence of a zero mutation probability limit for the stationary
distribution. Section 7 is devoted to resolving that question affirmatively. It is based upon
the results developed in Section 6 and it also verifies the Section 5.5 observation concern-
ing the nonzero limit for all states corresponding to uniform populations.
A very significant theoretical contribution of this work is developed in Section 8. It
is a monotonic mutation probability bound sufficient to guarantee strong ergodicity of the
nonstationary two and three-operator simple genetic algorithm Markov chains. The
parameter bound is analogous to the simulated annealing temperature schedule bound.