Information Technology Reference
In-Depth Information
consequently, all the new individuals created by inversion are syntactically
correct programs.
In gene expression programming, the inversion operator randomly chooses
the chromosome, the gene within the chromosome to be modified, and the
start and termination points of the sequence to be inverted. Typically, a small
inversion rate
p
i
of 0.1 is used as this operator is seldom used as the only
source of genetic variation.
The workings of inversion can be analyzed in the evolutionary history
shown in Figure 3.15. For this analysis, a much higher inversion rate of 1.0
was used as only inversion was used to create genetic diversity. Again, the
problem we are trying to solve is the majority function and the chromosomes
encode in this case two sub-ETs linked by OR. Note that chromosome 6 of
generation 19 has maximum fitness and therefore encodes a perfect solution
to the majority function problem.
The comparison of the sequence of this perfect solution with the sequences
of all its ancestors shows that it is a direct descendant of chromosome 0 of
generation 18. Also worth pointing out is that not only the perfect solution
but also all the individuals of generations 18 and 19 are descendants of one
of the worst individuals of the initial population, chromosome 3; by chang-
ing this chromosome again and again during reproduction, a perfect solution
to the problem at hand was created by generation 19.
The last event of inversion that led to the creation of this perfect solution
is shown in Figure 3.16. As you can see, a small sequence of four elements
“AaAb” was inverted in gene 2, creating a new sub-ET that is not only con-
siderably different from its mother but is also slightly better (a fitness of 8 as
opposed to 7). This new individual is in fact better than all its ancestors and
encodes a perfect solution to the problem at hand.
Note that inversion has not only the power of making small or medium
changes (such as the one that led to the creation of this perfect solution) in
expression trees but has also the power of causing huge macromutations. For
instance, chromosome 7 of generation 19 has a terminal at the start position
of gene 1 as a result of a small inversion that occurred during reproduction
(Figure 3.17). In this case, the daughter sub-ET turned out a total of 11 nodes
smaller than its mother, remaining equally fit in the process. Again we can
see that macromutations are not always bad: they are in fact essential to
drive evolution into other, very distant peaks.
You have certainly noticed that the examples I have chosen in order to
illustrate the mechanisms and effects of the modification operators have
