Page 70 - 49A Field Guide to Genetic Programming

56 6 Modular, Grammatical and Developmental Tree-based GP

tree
→ h 39 mod 1 = 0, i.e., there is only one option i
E × sin(E × t)
→ h 7 mod 2 = 1, i.e., choose second option i
(E op E) × sin(E × t)
→ h 2 mod 2 = 0, i.e., take the first option i
(var op E) × sin(E × t)
→ h 83 mod 3 = 2, pick the third variable, i
(z op E) × sin(E × t)
→ h 66 mod 4 = 2, take the third operator i
(z × E) × sin(E × t)
. . .
(z × x) × sin(z × t)

Figure 6.3: Sample grammatical evolution derivation using the grammar in
Equation (6.3) and the integer sequence in Equation (6.4). The non-terminal
to be rewritten is underlined in each case.

of structures that can be constructed. While this is true, it can come at a
price.
An expressive type system typically requires more complex machinery to
support it. It often makes it more difficult to generate type-correct individ-
uals in the initial population or during mutation and it is more difficult to
find crossover points that do not violate the type system. In an extreme case
like, constructive type theory (Thompson, 1991), the type system is so pow-
erful that it can completely express the formal specification of the program.
Thus, any program/expression having this type is guaranteed to meet that
specification. In GP this would mean that all the members of the initial
population would need to be solutions to the problem, thus putting all the
problem solving burden on the initialisation phase and removing the need
for any evolution at all! Even without such extreme constraints, it has often
been found necessary to develop additional machinery in order to efficiently
generate an initial population that satisfies the constraints (Montana, 1995;
Ratle and Sebag, 2000; Schoenauer and Sebag, 2001; Yu, 2001).
As a rule, systems that focus on syntactic constraints (such as grammar-
based systems) require less machinery than those that focus on semantic
constraints (such as type systems), since it is typically easier to satisfy the
syntactic constraints in a mechanistic fashion. For example, grammar-based