Toward an extrapolation of the simulated annealing convergence theory onto the simple genetic algorithm
Thomas E. Davis · 2011
Simulated annealing and the genetic algorithm are stochastic relaxation search techniques suitable for application to a wide variety of combinatorial complexity nonconvex optimization problems. Each produces a sequence of candidate solutions (or populations of candidate solutions) to the underlying optimization problem, and the purpose of both algorithms is to generate sequences biased toward solutions which optimize the objective function. The appeal of simulated annealing is that it provides asymptotic convergence to a globally optimal solution. A substantial body of knowledge exists concerning the algorithm convergence behavior. It is based upon a nonstationary Markov chain algorithm model. No genetic algorithm model comparable in scope exists in the literature. This work constitutes an attempt to provide such a model and accompanying convergence theory by extrapolating the simulated annealing results onto the genetic algorithm. A prerequisite, developed herein, is a nonstationary Markov chain genetic algorithm model. The essence of the simulated annealing theory is demonstration of (1) existence of a unique asymptotic probability distribution (stationary distribution) for the stationary Markov chain corresponding to every strictly positive constant value of an algorithm control parameter (absolute temperature), (2) existence of a stationary distribution limit as the control parameter approaches zero, (3) the desired behavior of the stationary distribution limit (i.e. optimal solution with probability one) and (4) sufficient conditions on the algorithm control parameter to ensure that the nonstationary algorithm achieves (asymptotically) the limiting distribution. With the exception of (3), this work adapts that methodology to the genetic algorithm Markov chain model employing a genetic operator parameter (mutation probability) as the algorithm control parameter. The results include a mutation probability control parameter bound analogous to (and asymptotically superior to) the conventional simulated annealing parameter bounds, and a framework for representing the genetic algorithm stationary distribution components at all consistent fixed control parameter values, including zero. The genetic algorithm stationary distribution limit has nonzero components corresponding to all solutions. Thus, the simulated annealing global optimality convergence result does not extrapolate. However, both empirical and theoretical evidence is provided which suggests that the desired limiting behavior can be approached by suitably adjusting the algorithm parameters.