Page 38 - 49A Field Guide to Genetic Programming

24 3 Getting Ready to Run Genetic Programming

3.3 Step 3: Fitness Function

The first two preparatory steps define the primitive set for GP, and therefore
indirectly define the search space GP will explore. This includes all the
programs that can be constructed by composing the primitives in all possible
ways. However, at this stage, we still do not know which elements or regions
of this search space are good. I.e., which regions of the search space include
programs that solve, or approximately solve, the problem. This is the task
of the fitness measure, which is our primary (and often sole) mechanism
for giving a high-level statement of the problem’s requirements to the GP
system. For example, suppose the goal is to get GP to synthesise an amplifier
automatically. Then the fitness function is the mechanism which tells GP
to synthesise a circuit that amplifies an incoming signal. (As opposed to
evolving a circuit that suppresses the low frequencies of an incoming signal,
or computes its square root, etc. etc.)
Fitness can be measured in many ways. For example, in terms of: the
amount of error between its output and the desired output; the amount
of time (fuel, money, etc.) required to bring a system to a desired target
state; the accuracy of the program in recognising patterns or classifying
objects; the payoff that a game-playing program produces; the compliance
of a structure with user-specified design criteria.
There is something unusual about the fitness functions used in GP that
differentiates them from those used in most other evolutionary algorithms.
Because the structures being evolved in GP are computer programs, fitness
evaluation normally requires executing all the programs in the population,
typically multiple times. While one can compile the GP programs that make
up the population, the overhead of building a compiler is usually substantial,
so it is much more common to use an interpreter to evaluate the evolved
programs.
Interpreting a program tree means executing the nodes in the tree in
an order that guarantees that nodes are not executed before the value of
their arguments (if any) is known. This is usually done by traversing the
tree recursively starting from the root node, and postponing the evaluation
of each node until the values of its children (arguments) are known. Other
orders, such as going from the leaves to the root, are possible. If none
of the primitives have side effects, the two orders are equivalent. 3 This
depth-first recursive process is illustrated in Figure 3.1. Algorithm 3.1 gives
a pseudocode implementation of the interpretation procedure. The code
assumes that programs are represented as prefix-notation expressions and
that such expressions can be treated as lists of components.

3 Functional operations like addition don’t depend on the order in which their argu-
ments are evaluated. The order of side-effecting operations such as moving or turning a
robot, however, is obviously crucial.