Page 68 - 49A Field Guide to Genetic Programming

54 6 Modular, Grammatical and Developmental Tree-based GP

tree

E * sin ( E * t )

var ( E op E )

y var + var

x z

Figure 6.2: Example individual (a derivation tree) that might be evolved
in Whigham’s grammar-based GP system (Whigham, 1996) if the grammar
in Equation (6.3) was used. Rectangles represent non-terminal symbols of
the grammar.

In this sort of system, the grammar is typically used to ensure the initial
population is made up of legal “grammatical” programs. The grammar is
also used to guide the operations of the genetic operators. Thus we need to
keep track not only of the program itself, but also the syntax rules used to
derive it.
What actually is evolved in a grammar-based GP system depends on the
particular system. Whigham (1996), for example, evolved derivation trees,
which effectively are a hierarchical representation of which rewrite rules must
be applied, and in which order, to obtain a particular program. Figure 6.2
shows an example of a derivation tree representing a grammatical program
with respect to the grammar in Equation (6.3). In this system, crossover is
restricted to only swapping subtrees deriving from a common non-terminal
symbol in the grammar. So, for example, a subtree rooted by an E node
could be replaced by another also rooted by an E, while an E-rooted subtree
could not be replaced by an op-rooted one.
The actual program represented by a derivation tree can be obtained by
reading out the leaves of the tree one by one from left to right. For the
derivation tree in Figure 6.2, for example, this produces the program
y × sin((x + z) × t).
However, for efficiency reasons, in an actual implementation it is not con-
venient to extract the program represented by a derivation tree is this way.