Page 24 - 49A Field Guide to Genetic Programming

10 2 Tree-based GP

together with certain other features of their structure, form the architecture
of the program. This is discussed in more detail in Section 6.1.
It is common in the GP literature to represent expressions in a prefix no-
tation similar to that used in Lisp or Scheme. For example, max(x+x,x+3*y)
becomes (max (+ x x) (+ x (* 3 y))). This notation often makes it eas-
ier to see the relationship between (sub)expressions and their corresponding
(sub)trees. Therefore, in the following, we will use trees and their corre-
sponding prefix-notation expressions interchangeably.
How one implements GP trees will obviously depend a great deal on
the programming languages and libraries being used. Languages that pro-
vide automatic garbage collection and dynamic lists as fundamental data
types make it easier to implement expression trees and the necessary GP
operations. Most traditional languages used in AI research (e.g., Lisp and
Prolog), many recent languages (e.g., Ruby and Python), and the languages
1
associated with several scientific programming tools (e.g., MATLAB and
2
Mathematica ) have these facilities. In other languages, one may have to
implement lists/trees or use libraries that provide such data structures.
In high performance environments, the tree-based representation of pro-
grams may be too inefficient since it requires the storage and management
of numerous pointers. In some cases, it may be desirable to use GP primi-
tives which accept a variable number of arguments (a quantity we will call
arity). An example is the sequencing instruction progn, which accepts any
number of arguments, executes them one at a time and then returns the

max

+ +

x x x ∗

3 y

Figure 2.1: GP syntax tree representing max(x+x,x+3*y).

1
MATLAB is a registered trademark of The MathWorks, Inc
2 Mathematica is a registered trademark of Wolfram Research, Inc.