3.2.3 Mutation
The mutation operator is applied to each member of the successor generation
created by the reproduction and crossover operators. It simply consists of randomly per-
turbing each descendent string with some (usually very small) perturbation probability,
p,. The operator exerts a diverging influence on the search algorithm, and it provides a
means by which the search can, with some nonzero probability, always arrive at any point
in the solution space. That is, no part of the "gene pool" is ever permanently extinguished
if the mutation operator is implemented. Clearly, it is analogous to mutation in biological
reproduction. Note also that if p, > 0, the mutation operator precludes the algorithm from
ever producing a permanently uniform population (i.e. it precludes algorithm conver-
gence).
3.3 Building Blocks, Schemata and the Fundamental Theorem
The underlying premise of the genetic algorithm operators is that good solutions to
an optimization problem over a bit-string solution space are composed of locally good
substrings, and that assembling combinations of such locally good substrings is an effec-
tive way to search the space for globally good solutions. In the genetic algorithm litera-
ture, this is referred to as the building block hypothesis. For a problem to be amenable to
genetic algorithm solution, this hypothesis should apply. In the genetics parlance, this
hypothesis is stated as a requirement that the problem exhibit "...some but not too much
epistasis" [Davi87]. The next subsection introduces an idea which helps to place this
hypothesis on a more analytical basis, but the results are still incomplete.
3.3.1 Schema Defined
Let the solution space under consideration be the set of binary strings of length L,
(i.e. S = {0, I}L). Then, a schema (plural schemata), designated H, is a subset of S having
the property that every member of H matches at some specified set of defining bit loca-
tions. Thus, if L= 5, then the schema H might be the set of length 5 bit-strings which
match the string (1,0,1,0,0) at the bit locations indicated by H = {s:s= (1,*,*,,0,*)}, in