Page 26 - 49A Field Guide to Genetic Programming

12 2 Tree-based GP

t=1 t=2 t=3 t=4
+ + + +

∗ ∗ ∗

x x y
t=5 t=6 t=7
+ + +

∗ / ∗ / ∗ /

x y x y 1 x y 1 0

Figure 2.3: Creation of a full tree having maximum depth 2 using the full
initialisation method (t = time).

will describe two of the simplest (and earliest) methods (the full and grow
methods), and a widely used combination of the two known as Ramped half-
and-half.
In both the full and grow methods, the initial individuals are generated
so that they do not exceed a user specified maximum depth. The depth of
a node is the number of edges that need to be traversed to reach the node
starting from the tree’s root node (which is assumed to be at depth 0). The
depth of a tree is the depth of its deepest leaf (e.g., the tree in Figure 2.1 has
a depth of 3). In the full method (so named because it generates full trees,
i.e. all leaves are at the same depth) nodes are taken at random from the
function set until the maximum tree depth is reached. (Beyond that depth,
only terminals can be chosen.) Figure 2.3 shows a series of snapshots of the
construction of a full tree of depth 2. The children of the * and / nodes
must be leaves or otherwise the tree would be too deep. Thus, at both steps
t = 3, t = 4, t = 6 and t = 7 a terminal must be chosen (x, y, 1 and 0,
respectively).
Although, the full method generates trees where all the leaves are at
the same depth, this does not necessarily mean that all initial trees will
have an identical number of nodes (often referred to as the size of a tree)
or the same shape. This only happens, in fact, when all the functions in
the primitive set have an equal arity. Nonetheless, even when mixed-arity
primitive sets are used, the range of program sizes and shapes produced by
the full method may be rather limited. The grow method, on the contrary,
allows for the creation of trees of more varied sizes and shapes. Nodes are
selected from the whole primitive set (i.e., functions and terminals) until
the depth limit is reached. Once the depth limit is reached only terminals