Page 39 - 49A Field Guide to Genetic Programming

3.3 Step 3: Fitness Function 25

- 2
x=-1

+ 1 / -1

- 3 - -2 - 3 - -3

3 0 x 1 3 0 x 2

Figure 3.1: Example interpretation of a syntax tree (the terminal x is a
variable and has a value of -1). The number to the right of each internal
node represents the result of evaluating the subtree root at that node.

procedure: eval( expr )
1: if expr is a list then
2: proc = expr(1) {Non-terminal: extract root}
3: if proc is a function then
4: value = proc( eval(expr(2)), eval(expr(3)), ... ) {Function: evaluate
arguments}
5: else
6: value = proc( expr(2), expr(3), ...) {Macro: don’t evaluate argu-
ments}
7: end if
8: else
9: if expr is a variable or expr is a constant then
10: value = expr {Terminal variable or constant: just read the value}
11: else
12: value = expr() {Terminal 0-arity function: execute}
13: end if
14: end if
15: return value
Notes: expr is an expression in prefix notation, expr(1) represents the prim-
itive at the root of the expression, expr(2) represents the first argument of
that primitive, expr(3) represents the second argument, etc.

Algorithm 3.1: Interpreter for genetic programming