The key limitation of simulated annealing is that the convergence behavior is
asymptotic. Thus global optimality is obtained only after an infinite number of algorithm
iterations. The rate of convergence to optimality is determined by a nonnegative algo-
rithm control parameter whose ideal value is zero and which must observe a lower bound
in order to assure coherent algorithm behavior. The best available known bound for the
parameter, the annealing schedule bound, is of the form K/log(k) where k is the iteration
index and K is a parameter independent of k [GeGe84, MiRo85].
Another combinatorial optimization stochastic search technique reported in the lit-
erature is the genetic algorithm [Davi87, Gold83, Gold89a, Gref85, Gref87]. It emulates
the evolution of biological systems by employing a set of stochastic operators (e.g.
reproduction, crossover and mutation) to transform a population of candidate solutions to
the underlying optimization problem into a new (descendent) population. It has some fea-
tures which suggest that it may provide significantly improved convergence behavior
over simulated annealing on certain types of optimization problems. However, the nature
of the genetic operators and their influence on algorithm behavior is only understood in
general terms. No complete theoretical model of the algorithm exists in the literature. The
fundamental goal of the work reported here is to provide a theoretical framework for ana-
lyzing the algorithm based upon the asymptotic probability distribution of the solution
sequences which it produces. The work reported herein includes significant progress on
the key intermediate steps to achieving that goal.
1.2 Organization
The remaining sections of this paper are organized as follows. Sections 2 and 3 are
background reviews of the simulated annealing and genetic algorithm literature respec-
tively. Section 2 places considerable emphasis on the methodology employed to yield the
asymptotic convergence results which are the theoretical foundation of the simulated
annealing algorithm. That methodology appeals heavily to the theory of inhomogeneous
(nonstationary) Markov chains and their asymptotic state probability distributions. The