3 Representation of Solutions

The original formulations of genetic programming considered Lisp S-expressions as candidate solutions. The Lisp programming language is popular in artificial intelligence research as it was designed for symbolic processing, see [Shapiro, 1990] for a further discussion. S-expressions, or symbolic expressions, are the basic objects in Lisp and are naturally represented as syntax trees, where leaves represent terminals (variables or constants) and nodes represent functions. The arity of a node is the number of arguments it expects to receive. In genetic programming, to overcome typing issues related to passing arguments and function values to functions, it is standard to use a strongly-typed system [Montana, 1995] where variables and functions have the same type. Grammar-based genetic programming systems can use multiple types easily, but require a defined grammar and specialised operators, e.g. [Whigham, 1995,Ryan et al., 1998].

The evaluation of a syntax tree is performed as a depth-first walk of the tree. Before evaluating a node, each of its arguments must first be evaluated. Thus, one may think of the syntax tree evaluation algorithm as a recursive call on the root node of the tree, which in turn evaluates each of its children, typically from left to right. Function and terminal nodes return their values up the tree to their parent, where terminals can only return their value. In the domain of mathematical functions, the expression $((3 / (1+2)) + (-1))$ can be represented by an S-expression in prefix as:

$$(+ (/ (3 (+ (1 2) ) ) ) -1),$$

which can then be represented as a syntax tree as:

$$\Tree [.+ [./ 3 [.+ 1 2 ] ] -1 ] .$$

The representation of candidate solutions in genetic programming is not limited to single syntax trees. Auxiliary data structures such as memory arrays are also used [Spector and Luke, 1996], as are data structures containing several syntax trees to represent one solution [Luke, 1998]. The encapsulation of functions has been accomplished with automatically defined functions [Koza, 1994] or automatically defined macros [Spector, 1996]. More recent advances have seen ``architectural-altering'' operators, loops and recursion [Koza et al., 1999]. Additionally, when using functional languages such as ML in a genetic programming framework, iteration and recursion can become more natural [Olsson, 1995].