Page 65 - 49A Field Guide to Genetic Programming

6.2 Constraining Structures 51

Koza and his colleagues have used these architecture altering operations
quite widely in their genetic design work, where they evolve GP trees that
encode a collection of developmental operations that, when interpreted, gen-
erate a complex structure like a circuit or an optical system (see, for example,
Section 12.3, page 118).
The idea of architecture altering operations was extended to the ex-
tremely general Genetic Programming Problem Solver (GPPS), which is
described in detail in (Koza et al., 1999, part 4). This is an open ended
system which combines a small set of basic vector-based primitives with the
architecture altering operations in a way that can, in theory, solve a wide
range of problems with almost no input required from the user other than
the fitness function. The problem is that this open-ended system needs a
very carefully constructed fitness function to guide it to a viable solution, an
enormous amount of computational effort, or both. As a result it is currently
an idea of more conceptual than practical value.

6.2 Constraining Structures

As discussed in Section 3.2.1, most GP systems require type consistency
where all subtrees return data of the same type. This ensures that the out-
put of any subtree can be used as one of the inputs to any node. The basic
subtree crossover operator shuffles tree components entirely randomly. Uni-
versal type compatibility ensures that crossover cannot lead to incompatible
connections between nodes. This is also required to stop mutation from
producing illegal programs.
An implicit assumption underlying this approach is that all combinations
of structures are equally likely to be useful. In many cases, however, we know
in advance that there are constraints on the structure of the solution, or we
have strong suspicions about the likely form solutions will take. In this
section, we will look at several different systems that use tools such as types
and grammars to bias or constrain search with the primary aim of increasing
the chance of finding a suitable program.
A problem domain might be naturally represented with multiple types.
This suggests that the functions used by GP and their arguments will not
necessarily be all of the same type. This can often be addressed through
creative definitions of functions and implicit type conversion. For example,
the Odin system (Holmes and Barclay, 1996) defines operations on inappro-
priate types to return a new fail object. These are handled by introducing
a binary fatbar that returns its first argument unless it is fail, in which case
it returns its second argument.
This sort of approach may not always be desirable. For example, if a
key goal is to evolve solutions that can be easily understood or analysed,
then one might prefer a GP system that is constrained structurally or via