Vm e S' : (1) q,(m) > 0
(2) q1 = 1
(3) P=y .
Since the stationary distribution is by definition a left eigenvector of the state transition
matrix (Definition A10), it follows from Eq. 4.15 and 4.16 that the asymptotic state prob-
ability distribution of the time-homogeneous two-operator algorithm is completely deter-
mined by the objective function and the algorithm parameters. It is independent of the
starting state, mo.
4.3.3 A Three-Operator Algorithm (Reproduction. Mutation and Crossover)
The three-operator simple genetic algorithm corresponds to the case
Vk:Qk = (pm(k), pc(k)) with both pm(k) and p,(k) nonzero. Results analogous to Eq.
4.14-4.21 for the two-operator case are obtainable by defining a new function which is
similar in character to the Hamming distance function employed in Section 4.3.2 for the
two-operator case. This subsection completes that generalization. The result only reflects
the crossover operation implicitly, however it permits some very significant conclusions
concerning bounding values of the three operator conditional probabilities.
The new function, I(i,j, k, s), is defined over an ordered quadruple (i,j, k, s) where
i,j,k e S and where s e {0, 1, -,L} is a bit-string location. The states i,j e S represent
respectively the first and second parent strings selected at a particular crossover opportu-
nity and k e S represents a possible descendent string. The bit-string location s is the
location randomly selected by the crossover operator, and normally it is uniformly
distributed over its range. Thus, I is defined on S x S x S x {0, 1,2, .. L} and it takes on
values selected from {0, 1 depending upon whether the indicated crossover operation is
or is not consistent. That is, I assumes the value one if the bit-string k is produced by
crossing the bit-strings i and j at the site s, and zero otherwise.