Page 223 -

5.8 Genetic Algorithms 21 1

Consider the following example of a chromosome with 6 binary genes
belonging to two distinct schemas, H1 and H2:

When crossing g with another chromosome, there is only a small chance that
schema HZ will survive, unless the other chromosome has genes in the same fixed
positions before or after the crossing position. On the contrary, schema Hl will
always survive. As a matter of fact, a little thought shows that a schema survives 1-
point crossover if it falls outside its defining length d(H). As there are m-1 different
positions for I-point crossover the probability of survival is:

4~)
Ps =I--.
m-l
If crossover is applied with probability P, the probability of survival is:

Similar results are obtained for other types of crossover.
Concerning the effect of mutation, a schema is destroyed if mutation is applied
to any fixed position. If P,,, is the probability of mutation, the chance of a schema
surviving is:

Combining all these effects we have:

Neglecting a small cross-product term:

This formula justifies the statement of the Schema theorem that short, low-order
and above average fitness schemata will grow exponentially in subsequent
generations.
The problem with the Schema theorem is that it assumes that important
chromosomal information is already present initially, or will appear during