Information Technology Reference
In-Depth Information
AND
AND
Parent solutions
T1
OR
OR
T1
OR
T1
T1
T2
T2
T3
AND
AND
Child solutions
OR
OR
T2
T1
T1
T1
OR
T1
T3
T2
Figure 3.1
Subtree crossover. Crossover points are chosen randomly in two parent
solutions, and the subtrees below the crossover points are swapped to produce child
solutions.
Subtree crossover is a natural recombination operator for parse trees and
can be useful to evolution. However, subtree crossover does have significant
limitations [3, 31]. In one sense, the behaviors that subtree crossover can carry
out are too constrained. This is because subtree crossover may only work with
full subtrees. A group of components that do not form a complete subtree can
only be exchanged if the entire subtree within which they reside is exchanged.
This means that an incomplete subtree that does not have a fully ground set of
leaf nodes may not be transferred, although this operation would be particularly
useful for incomplete subtrees near the root of the parse tree. In this situation
swapping the entire subtree with another would almost inevitably make the
program dysfunctional. Figure 3.2 shows what an incomplete subtree crossover
could look like.
In another sense, the behaviors that subtree crossover does carry out are too
unconstrained. This is because subtrees are exchanged nondeterministically.
When a functional subtree is replaced by a subtree that does not carry out a
similar function, this will most likely cause the program to stop working. Hence,
most nondeterministic subtree crossovers will produce inviable recombinants.
Relatively few crossovers will have a positive, or at least neutral, effect [30].
Consequently, most of the behaviors carried out by subtree crossover are not
useful most of the time.
One solution to these problems is to modify crossover to allow a greater range
of behaviors while disallowing disruptive behaviors [20]. Such an operator
