Page 66 - 49A Field Guide to Genetic Programming

52 6 Modular, Grammatical and Developmental Tree-based GP

a type system, since these often generate results that are more comprehen-
sible (Haynes, Wainwright, Sen, and Schoenefeld, 1995), (Langdon, 1998,
page 126). Similarly, if there is domain knowledge that strongly suggests a
particular syntactic constraint on the solution, then ignoring that constraint
may make it much harder to find a solution.
We will focus here on three different approaches to constraining the syn-
tax of the evolved expression trees in GP: simple structure enforcement
(Section 6.2.1), strongly typed GP (Section 6.2.2) and grammar-based con-
straints (Section 6.2.3). Finally, we consider the advantages and disadvan-
tages of syntactic and type constraints and their biases (Section 6.2.4).

6.2.1 Enforcing Particular Structures

If a particular structure is believed or known to be important then one
can modify the GP system to require that all individuals have that struc-
ture (Koza, 1992). For example, if a problem is believed to have (or require)
a periodic solution, one might want to consider constraining the search to
solutions of the form a × sin(b × t). By allowing a and b to evolve freely
but keeping the rest of the structure fixed, one could restrict GP to evolving
expressions that are periodic. Syntax restrictions can also be used to make
GP follow sensible engineering practices. For example, we might want to
ensure that loop control variables appear in the correct parts of for loops
and nowhere else (Langdon, 1998, page 126).
Enforcing a user specified structure on the evolved solutions can be imple-
mented in a number of ways. One could ensure that all the initial individuals
have the structure of interest (for example, generating random subtrees for
a and b while fixing the rest) and then constrain crossover and mutation
so that they do not alter any of the fixed regions of a tree. An alternative
approach would be to evolve the various (sub)components separately. One
could evolve pairs of trees (a, b) (like ADFs). Alternatively, one could have
two separate populations, one of which is used to evolve candidates for a
while the other is evolving candidates for b.
A form of constraint-directed search in GP was also proposed in (Tsang
and Jin, 2006; Tsang and Li, 2002) to help GP to focus on more promising
areas of the space.

6.2.2 Strongly Typed GP

Since constraints are often driven by or expressed using a type system, a
natural approach is to incorporate types and their constraints into the GP
system (Montana, 1995). In strongly typed GP, every terminal has a type,
and every function has types for each of its arguments and a type for its
return value. The process that generates the initial, random expressions,