Equation 3.2 is an inequality because it does not consider the accretion of the
schema H contributed by crossover and mutation. It only accounts for the disruptive
effects of these operators. A more thorough treatment can be found on pp 9-13 of
[Gref87], but the result is too cumbersome to be of much analytical value.
Qualitatively, Eq. 3.2 suggests that low order schemata occurring in the current
population contribute to succeeding generations in direct proportion to the product of
their number in the current generation and their average performance relative to the other
schemata competing for dominance of the same set of defining locations. Crossover and
mutation tend to disrupt this converging influence, and the disruptive effect of crossover
is directly proportional to the defining length of the schema in question.
In view of Eq. 3.2, the building block hypothesis might be restated as a characteris-
tic of genetic algorithm amenable optimization problems. A GA amenable problem is one
for which a near optimum solution can be achieved, with a relatively small expenditure of
search effort, by assembling high performance, low order schemata into novel combina-
tions. If the objective function is such that (nonlinear) contributions from combinations of
bits spanning widely separate bit locations are appreciable (i.e. if the objective function
depends heavily on large defining length schemata), then the problem is not likely to be
suitable for solution by genetic algorithm. On the other hand, if the objective function
depends predominantly on short defining length schemata, then sorting through promis-
ing combinations of realizations of those schemata is likely to isolate good (though not
necessarily optimal) solutions. Accomplishing the required sorting efficiently is the task
for which genetic algorithms are well suited.
3.4 An Assessment of the Genetic Algorithm Theoretical Foundation
The existing theoretical foundation for analysis of genetic algorithms includes the
fundamental theorem of genetic algorithms (Eq. 3.2) originally enunciated by Holland
[Holl75] and extended by Bridges and Goldberg [BrGo87], the Walsh function approach
to computing schema fitness averages contributed by Bethke [Beth80] and