Page 67 - 49A Field Guide to Genetic Programming

6.2 Constraining Structures 53

and all the genetic operators are implemented so as to ensure that they do
not violate the type system’s constraints.
Returning to the if example from Section 3.2.1 (page 21), we might have
an application with both numeric and Boolean terminals (e.g., get speed
and is food ahead). We might then have an if function that takes three
arguments: a test (Boolean), the value to return if the test is true, and
the value to return if the test is false. Assuming that the second and third
values are numbers, then the output of the if is also going to be numeric.
If we choose the test argument as a crossover point in the first parent, then
the subtree (excised from the second parent) to insert must have a Boolean
output. That is, we must find either a function which returns a Boolean or
a Boolean terminal in the other parent tree to be the root of the subtree
which we will insert into the new child. Conversely if we choose either the
second or third argument as a crossover point in the first parent, then the
inserted subtree must be numeric. In all three cases, given that both parents
are type correct, restricting the second crossover point in this way ensures
the child will also be type correct.
This basic approach to types can be extended to more complex type sys-
tems including simple generics (Montana, 1995), multi-level type systems
(Haynes, Schoenefeld, and Wainwright, 1996), fully polymorphic types (Ols-
son, 1994), and polymorphic higher-order type systems (Yu, 2001).

6.2.3 Grammar-based Constraints
Another natural way to express constraints is via grammars, and these have
been used in GP in a variety of ways (Gruau, 1996; Hoai, McKay, and
Abbass, 2003; O’Neill and Ryan, 2003; Whigham, 1996; Wong and Leung,
1996). Many of these simply use a grammar as a means of expressing the
kinds of constraints discussed above in Section 6.2.1. For example, one could
enforce the structure for the period function using a grammar such as the
following:

tree ::= E × sin(E × t) (6.3)
E ::= var | (E op E)
op ::= + | − | × | ÷
var ::= x | y | z

Each line in this grammar is known as a rewrite rule or a production rule.
Elements that cannot be rewritten are known as the terminals of the gram-
1
mar while symbols that appear on the left-hand-side of a rule are known
as non-terminal symbols.

1 Not to be confused with the terminals in the primitive set of a GP system.