Information Technology Reference
In-Depth Information
can change into another (function or terminal); and in the tails, terminals can
only change into terminals. This way, the structural organization of chromo-
somes is maintained and all the new individuals produced by mutation are
structurally correct programs.
It is worth emphasizing that GEP point mutation is totally unconstrained.
This means that, in the heads, functions can be replaced by other functions
without concern for the number of arguments each one takes; functions can
also be replaced by terminals and vice versa; and obviously terminals can
also be replaced by other terminals. Indeed, no restrictions whatsoever exist
and, therefore, mutation can be completely exploited to roam thoroughly the
fitness landscape.
The workings of mutation can be analyzed in the evolutionary history
shown in Figure 3.12. For this analysis, mutation was the only source of
genetic variation. The mutation rate was, as usual, equivalent to two one-
point mutations per chromosome, which, for these chromosomes of length
14, corresponds to a mutation rate
p
m
= 0.143. The populations shown in
Figure 3.12 were obtained in a run created to solve the already familiar ma-
jority function problem using the number of hits fitness function of section
3.2.3. Note that chromosome 1 of generation 6 encodes a perfect solution to
the majority function and, therefore, has maximum fitness.
By analyzing the sequence of this perfect solution, one can easily guess
that its most probable ancestors are chromosomes 0, 1, and 3 of generation 5.
In the first case, only one point mutation would have occurred during repro-
duction, whereas two point mutations would have been required in the last
two cases. Figure 3.13 compares the sub-ETs of one of these putative ances-
tors (chromosome 3) with the daughter sub-ETs, i.e., before and after muta-
tion. As you can see, in this case, two point mutations occurred during repro-
duction of chromosome 3: one changed the “N” at position 1 in gene 1 into
“a”; and another changed the “a” at position 3 in gene 2 into “b”. Note that
the first mutation changed significantly the sub-ET
1
, shortening the original
sub-ET in one node. Note also that, although the second mutation did not
change the shape of sub-ET
2
, the expression encoded in this new sub-ET is
no longer the same.
Let's now analyze more closely the populations shown in Figure 3.12. On
the one hand, we can see that several mutations have a neutral effect. For
instance, chromosome 7 of generation 6 is a descendant of chromosome 4 of
generation 5. These chromosomes differ only at positions 1 and 4 in gene 2. As
you can see in Figure 3.14, the expression of these chromosomes results in
