disrupting high order high performance schemata. The extent of population divergence
introduced by the crossover operator is determined in part by the degree of schema diver-
sity present in the current population. In particular, when the population becomes uni-
form, the crossover operator is nullified, because assembling substrings extracted from
identical strings produces identical progeny.
The mutation operator also provides a disruptive mechanism which resists the con-
verging influence of the reproduction operator. Since any schema can be produced by
mutation with nonzero probability, the permanent extinction of any of the 3L possible
distinct schemata is precluded.
These ideas are captured in the following inequality, which is referred to in the liter-
ature as the Fundamental Theorem of Genetic Algorithms. It relates the number of copies
of a particular schema in the current generation to the expected number of copies of the
same schema in the succeeding generation. This inequality is derived in [Gold89a] from
relatively simple probability notions. The development is not repeated here.
E{ m(H,k+l) ) 2 m(H,k) x x Eq. 3.2
R
8(H)
[1 p x --- p x o(H)]
(L 1)
where m(H, k) = number of occurrences of schema H in the population at
generation k,
E{} = expected value operator,
R(H) = average objective function value (> 0) of all strings in
the current population which are realizations of H,
R = the average objective function value of the current pop-
ulation.