Information Technology Reference
In-Depth Information
This new way of representing the parse tree has a number of advantages from
an evolutionary perspective. First, it introduces positional independence. The
position of a component in the array need not have any direct bearing on the
position of the component in the parse tree. This is of benefit to recombination
because position is not conserved where different programs are of different
shapes and sizes—which, most of the time, is the case for GP. Consequently,
the position of a component in a child program will most likely not be its position
in the parent program. In tree-based GP, where context is given by position,
this is a problem. In enzyme GP, where context is independent of position, it is
not a problem.
Second, the linear encoding has a homogenous structure. In a typical parse
tree about half of the nodes are leaf nodes. Consequently, during subtree
crossover, a large proportion of randomly chosen crossover points will occur at
or near the leaf nodes. This, in turn, means that a disproportionately high number
of small subtrees will be targeted during crossover. In practice the selection of
crossover points is biased so that more are chosen nearer the root of the tree.
However, this bias has to be carefully chosen to avoid biasing the shapes and
sizes of solutions explored during evolution. In enzyme GP, by comparison,
there is no need to bias crossover because it will automatically sample subtrees
of all sizes. Furthermore, enzyme GP does not have to target complete subtrees
during recombination. It can, in principle, target any collection of components.
In some cases, components will be connected, such as subtrees, in other cases
they will not. Consequently, crossover can carry out a wide range of behaviors.
However, it is possible that during evolution linkage will develop between
neighboring genes, meaning that crossover is more likely to target connected
groups of components. The more evolved the solutions, therefore, the more
focused the behaviors of crossover could become.
Third, not all the components described within a genome need be expressed
in the developed program. One example of the utility of this is TR crossover,
which allows components to be added to a genome without replacing exist-
ing components. If the new components do not naturally interact with the
existing components, then they will not be used in the program. This is less
disruptive than forcing components to be replaced, which is the only option
with subtree crossover. Redundant components, more generally, can form a
source of backtracking and neutral evolution. Backtracking can be enabled
by saved copies of components that are no longer used in developed pro-
grams. These, and unused copies of current components, are subject to mu-
tation. Because they do not contribute to the phenotype, these mutations are
neutral and have no fitness penalty. Nevertheless, these mutations may be ben-
eficial and result in improvements to existing components. This might lead
to the development of gene families comparable to those found in biological
genomes.
