Section 5 digresses briefly from the theoretical development to produce and
examine some empirical work based upon the algorithm model. The presentation is not,
nor is it intended to be, a thorough empirical study. It is provided to help fix some of the
algorithm model state space and asymptotic probability distribution ideas which are cen-
tral to this work, and it anticipates some of the theoretical results which follow.
Section 6 resumes the theoretical development. Its result is an expression for the
components of the unique asymptotic probability distribution produced by the stationary
algorithm variants which implement the mutation operator with nonzero mutation proba-
bility (i.e. the stationary two and three-operator algorithm variants). The result is
expressed in terms of Cramer's Rule and thus its solution requires evaluation of
determinants. The determinants are the characteristic polynomials, evaluated at X= 1, of
matrices derived from the state transition matrix produced in Section 4 by zeroing one
row. A later section attacks the problem of explicitly solving the system, based upon the
highly symmetrical nature of the state transition matrix, but some very significant results
are obtainable from the product of Section 6 without explicit solution.
An essential step in establishing a connection between simulated annealing and the
genetic algorithm is demonstrating the existence of a stationary distribution limit for the
algorithm as the mutation probability approaches zero. Section 7 accomplishes that task
and also provides a foundation for deducing, in Section 8, a mutation probability bound
analogous to the annealing schedule bounds of the simulated annealing algorithm. The
results developed in Sections 7 and 8 apply to both the two and three-operator algorithm
variants.
A somewhat surprising result produced in Section 7 and anticipated by the empiri-
cal study reported in Section 5 is that the stationary distribution zero mutation probability
limit does not necessarily isolate globally optimal solutions. In fact, it provides nonzero
probability for all solutions of the underlying optimization problem and consequently the
extrapolation of the simulated annealing methodology is less than exact. However, both