SECTION 10
CONCLUSIONS AND FUTURE DIRECTION
10.1 Summary
This dissertation reports an effort to establish an analytical framework for the sim-
ple genetic algorithm, based upon the asymptotic probability distribution of the generated
solution sequences. The mechanism employed herein is extrapolation of the extensive
existing theoretical foundation of the simulated annealing algorithm onto the genetic
algorithm. That foundation is based upon the asymptotic behavior of a nonstationary
Markov chain simulated annealing algorithm model. The simulated annealing literature is
reviewed in Section 2, with particular emphasis on the methodology employed to develop
the key theoretical results. Those results include a demonstration that provided a lower
bound of the form K/log(k) on the algorithm parameter corresponding to absolute temper-
ature is observed, the asymptotic probability distribution over the algorithm state space is
zero for all states corresponding to sub-optimal solutions. Thus, the simulated annealing
algorithm obtains asymptoticallyy) a globally optimal solution.
The genetic algorithm literature is reviewed in Section 3. The significant conclusion
of that section is that while certain important theoretical results exist, notably the so
called schema theorem and some work on a problem construct referred to as the minimal
deceptive problem, no genetic algorithm model or accompanying convergence theory
comparable in scope to that of simulated annealing exists in the literature. The fundamen-
tal purpose of the work described herein is to provide such an analytical framework by
extrapolating the known simulated annealing theory onto the genetic algorithm.
An essential first step toward that goal is development of a nonstationary Markov
chain algorithm model for the genetic algorithm. That task is accomplished in Section 4.