Page 35 - 49A Field Guide to Genetic Programming

3.2 Step 2: Function Set 21

Table 3.1: Examples of primitives in GP function and terminal sets.
Function Set
Kind of Primitive Example(s)
Arithmetic +, *, /
Mathematical sin, cos, exp
Boolean AND, OR, NOT
Conditional IF-THEN-ELSE
Looping FOR, REPEAT
. .
. .
. .
Terminal Set
Kind of Primitive Example(s)
Variables x, y
Constant values 3, 0.45
0-arity functions rand, go left

3.2.1 Closure
For GP to work effectively, most function sets are required to have an impor-
tant property known as closure (Koza, 1992), which can in turn be broken
down into the properties of type consistency and evaluation safety.
Type consistency is required because subtree crossover (as described in
Section 2.4) can mix and join nodes arbitrarily. As a result it is necessary
that any subtree can be used in any of the argument positions for every func-
tion in the function set, because it is always possible that subtree crossover
will generate that combination. It is thus common to require that all the
functions be type consistent, i.e., they all return values of the same type,
and that each of their arguments also have this type. For example +, -, *,
and / can can be defined so that they each take two integer arguments and
return an integer. Sometimes type consistency can be weakened somewhat
by providing an automatic conversion mechanism between types. We can,
for example, convert numbers to Booleans by treating all negative values as
false, and non-negative values as true. However, conversion mechanisms can
introduce unexpected biases into the search process, so they should be used
with care.
The type consistency requirement can seem quite limiting but often sim-
ple restructuring of the functions can resolve apparent problems. For exam-
ple, an if function is often defined as taking three arguments: the test, the
value to return if the test evaluates to true and the value to return if the
test evaluates to false. The first of these three arguments is clearly Boolean,
which would suggest that if can’t be used with numeric functions like +.