control parameter values, F, signals algorithm termination, and n can be allowed to
depend on {fmik provided the algorithm termination requirement is satisfied.
4.3 State Behavior of the Simple Genetic Algorithm
In each of the next three subsections, the state transition mechanism (and its effect
on the nature of the solution sequence) which results from employing a specified combi-
nation of the genetic algorithm operators to the Markov chain model is examined. The
first case consists of a one-operator algorithm which employs only the reproduction
operator. The second is a two-operator algorithm which employs reproduction and muta-
tion. Finally a three-operator algorithm which includes crossover with reproduction and
mutation is examined.
Although it is most natural to describe the genetic operators in the order reproduc-
tion/crossover/mutation, the course adopted in Section 3.2, the following development
proceeds most instructively if mutation is included with reproduction in the two-operator
algorithm and crossover is deferred to the three-operator case. This is due to the fact that
the mutation operator provides the essential state space modification required to make the
Markov chains of the time-homogeneous two and three-operator algorithms irreducible
(Definitions A7 and A8, Theorem Al), and consequently causes them to have unique sta-
tionary distributions (Theorem A3). The one-operator algorithm (proportional reproduc-
tion only) does not satisfy the irreducibility requirement for existence of a unique
stationary distribution. (Neither does the algorithm variant which employs reproduction
and crossover without mutation). A unique stationary distribution means that the asymp-
totic state occupancy probability of the time-homogeneous two and three-operator algo-
rithms is completely determined by the algorithm parameters and objective function. It is
independent of the starting state (initial population). Asymptotic independence of the
starting state is a necessary (but not sufficient) condition on the zero mutation probability
limit of the stationary distribution of the time-homogeneous algorithm for the inhomoge-
neous algorithm counterpart to avoid asymptoticallyy) local minima entrapment.