Information Technology Reference
In-Depth Information
a less fit solution. However, the chance of finding a higher fitness solution can
be increased by only making small changes to existing solutions.
In practical terms, this requires that operators generate new solutions (child
solutions) that are similar to the existing solutions (parent solutions) they are
derived from. For mutation, a small change to the information held within
a representation should, in general, lead to a small change in the solution it
represents. For crossover, which derives new solutions from more than one
existing solution, the issues are more complicated. However, there is still a
requirement for each child solution to bear reasonable similarity to one of its
parents. A further requirement is that the recombination be meaningful, or to
use a simple metaphor, a child should not consist of two heads and no body.
Genetic Programming
Artificial evolution can be applied to any structure that can be represented within
a computer. This includes computer programs. Genetic programming (GP) [6,
15, 16, 17] is an approach in evolutionary computation that evolves programs
and other executable structures. The original GP algorithm was designed by
Koza [16], and many aspects of it, including the representation, remain standard
in modern GP.
In Koza's GP, programs are represented by their parse tree. A parse tree
captures the execution ordering of a program and shows the hierarchical rela-
tionships between components of the program. Functions occur at internal tree
nodes and terminals occur at leaf nodes. For a hierarchical language such as
LISP, the parse tree is the program. However, GP typically uses simple un-typed
languages that can be fully described by a function set and a terminal set. Since
there are no types, any function can receive the output of any other function or
terminal as input. Consequently, any parse tree will be syntactically correct.
The initial population is filled with random parse trees of various shapes
and sizes, each consisting of randomly chosen functions and terminals. The
standard variational operators are mutation and crossover. There are two kinds
of mutation. Point mutation replaces a single terminal with a single terminal
or a single nonterminal with a single nonterminal. Subtree mutation replaces a
subtree with a new randomly generated subtree. Crossover, which is depicted
in Figure 3.1, creates child parse trees by swapping a pair of subtrees between
two parent parse trees.
The Representation Problem of GP
Recall that evolvability places certain demands on recombination. First, new
solutions should be similar to at least one of the solutions they were derived
from. Second, recombination should be meaningful. In the example recombi-
nation shown in Figure 3.1, neither of these demands has been met, despite the
fact that the parent solutions are quite similar to one another.
