For the sake of simplicity, we are going to illustrate the mechanisms of mutation using the compact, linear representation of chromosomes used to describe the
structural organization of
chromosomes in the previous chapter. In this representation, each element (function or terminal) is represented by a single character so that each element can be easily identified by its position in the chromosome.
Mutation is by far the most efficient operator in Gene Expression Programming
(GEP). With mutation, populations of individuals adapt very efficiently, allowing the evolution of good solutions to virtually all problems. The default value for the
mutation rate in GeneXproTools 4.0 is 0.044, but a good rule of thumb consists of using a mutation rate equivalent to two one-point mutations per chromosome. Considering the length of GEP genomes, this mutation rate is much higher than the mutation rates found in nature, but thanks to the cloning of the best individual of each generation, we can have GEP populations undergoing high mutation rates and, nevertheless, evolving very efficiently.
In Gene Expression Programming, mutations can occur anywhere in the chromosome. But obviously the structural organization of chromosomes must remain intact, that is, in the
heads any symbol can change into another (function or terminal), whereas in the
tails terminals can only change into other terminals. This way, the
structural organization of chromosomes is preserved, and all the new individuals produced by mutation are structurally correct programs.
Consider the following chromosome composed of three genes, each with a head length of 7:
012345678901234012345678901234012345678901234
-cQd/-/aadddcca+*b**cQbcaacbda+c*/cdaabbdbcba
Suppose a mutation changed the “-” at position 5 in gene 1 to “b”;
the “d” at position 10 in gene 1 to “c”; the “*” at position 1 in gene 2 to “Q”; and the “c” at position 1 in gene 3 to “/”. In this case the following chromosome is obtained:
012345678901234012345678901234012345678901234
-cQd/b/aadcdcca+Qb**cQbcaacbda+/*/cdaabbdbcba
Note that if a function is mutated into a terminal or vice versa, or a function of one argument is mutated into a function of two arguments or vice versa, the
expression tree is usually modified drastically, growing or shrinking between the boundaries determined by the size of the gene. In summary, in
Gene Expression Programming
there are no constraints both in the kind of mutation and the number of mutations in a chromosome as, in all cases, the newly created individuals are syntactically correct programs.
|