56
P.A. Whigharn . G.ß. Fogel
Paren! 1 chromosome
Paren! 2 chromosome
• • 1
0010000
Chlld 1 chromosome
Chlld 2 chromosome
Child chromosome
0000
00 0
MII!~!Art r.hllrt r.hromo~omA
Figure 4.2. Crossover using tree structures (GP).
The details of the variation operators depend largely on the structure used to
represent the individuals of the population. The choice of an appropriate
representation is a key ingredient in the development of an evolutionary
algorithm, however current theory (Wolpert and Macready 1997) suggests that no
one representation or set of variation operators is most useful over all fitness
functions. Therefore, the user is required to tailor the representation and variation
operator to the problem at hand.
Figure 4.1 shows typical variation operators (crossover and point mutation) for
individuals represented as bit strings. The site(s) for crossover is commonly
selected at random and the parent material is recombined to create two new
offspring. Mutation is normally applied with a certain probability to each site of
the bit string, typically transforming the value from a 0 to 1, or vice versa. Figure
4.2 shows crossover using a tree structure as the individual representation (such as
found in Genetic programming (GP». Commonly, two random crossover sites are
selected from the parents, and the subtrees below this site are swapped to create
two new children. Mutation of a tree structure involves randomly selecting an
internal node, deleting the subtree below this node and randomly creating a new
subtree. The size of the new subtree is limited to some maximum depth of tree to
limit the individual size. This can also be considered as a means of limiting the
specialization of the tree representation: a smaller tree typically represents a more
P.A. Whigharn . G.ß. Fogel
Paren! 1 chromosome
Paren! 2 chromosome
• • 1
0010000
Chlld 1 chromosome
Chlld 2 chromosome
Child chromosome
0000
00 0
MII!~!Art r.hllrt r.hromo~omA
Figure 4.2. Crossover using tree structures (GP).
The details of the variation operators depend largely on the structure used to
represent the individuals of the population. The choice of an appropriate
representation is a key ingredient in the development of an evolutionary
algorithm, however current theory (Wolpert and Macready 1997) suggests that no
one representation or set of variation operators is most useful over all fitness
functions. Therefore, the user is required to tailor the representation and variation
operator to the problem at hand.
Figure 4.1 shows typical variation operators (crossover and point mutation) for
individuals represented as bit strings. The site(s) for crossover is commonly
selected at random and the parent material is recombined to create two new
offspring. Mutation is normally applied with a certain probability to each site of
the bit string, typically transforming the value from a 0 to 1, or vice versa. Figure
4.2 shows crossover using a tree structure as the individual representation (such as
found in Genetic programming (GP». Commonly, two random crossover sites are
selected from the parents, and the subtrees below this site are swapped to create
two new children. Mutation of a tree structure involves randomly selecting an
internal node, deleting the subtree below this node and randomly creating a new
subtree. The size of the new subtree is limited to some maximum depth of tree to
limit the individual size. This can also be considered as a means of limiting the
specialization of the tree representation: a smaller tree typically represents a more