SECTION 8
A MONOTONIC MUTATION PROBABILITY ERGODICITY BOUND
8.1 Overview
The annealing schedule bounds for the simulated annealing algorithm, which are
reviewed in Section 2.4.2, are derived by requiring that the nonstationary Markov chain
which represents the algorithm be strongly ergodic (Definition A13) and then deducing a
monotonic lower bound on the algorithm control parameter. The methodology consists of
demonstrating that the time-homogeneous Markov chain corresponding to every positive
algorithm control parameter value possesses a stationary distribution, that the sequence of
stationary distributions corresponding to any sequence of positive control parameter val-
ues converges to a limiting distribution if the control parameter sequence converges to
zero, and then employing Definitions A 1l-A13 and Theorems A5-A7 to deduce a
sufficient condition (the annealing schedule lower bound) to guarantee that the nonsta-
tionary algorithm achieves the limiting distribution (i.e. strong ergodicity).
The model development in Section 4 demonstrates that for all mutation probability
values in the range 0 < p < 1, the Markov chain representing either the two or three-
operator time-homogeneous simple genetic algorithm possesses a stationary distribution.
Section 7 demonstrates that the stationary distribution approaches a limit as the mutation
probability parameter approaches zero. This section proposes and then verifies a mono-
tone decreasing lower bound on the mutation probability sequence of the nonstationary
genetic algorithm Markov chain which is sufficient to ensure strong ergodicity.