Page 27 - 49A Field Guide to Genetic Programming
P. 27
2.2 Initialising the Population 13
t=1 t=2 t=3
+ + +
x x −
t=4 t=5
+ +
x − x −
2 2 y
Figure 2.4: Creation of a five node tree using the grow initialisation method
with a maximum depth of 2 (t = time). A terminal is chosen at t = 2,
causing the left branch of the root to be closed at that point even though
the maximum depth had not been reached.
may be chosen (just as in the full method). Figure 2.4 illustrates this
process for the construction of a tree with depth limit 2. Here the first
argument of the + root node happens to be a terminal. This closes off that
branch preventing it from growing any more before it reached the depth
limit. The other argument is a function (-), but its arguments are forced
to be terminals to ensure that the resulting tree does not exceed the depth
limit. Pseudocode for a recursive implementation of both the full and grow
methods is given in Algorithm 2.1.
Because neither the grow or full method provide a very wide array of
sizes or shapes on their own, Koza (1992) proposed a combination called
ramped half-and-half. Half the initial population is constructed using full
and half is constructed using grow. This is done using a range of depth limits
(hence the term “ramped”) to help ensure that we generate trees having a
variety of sizes and shapes.
While these methods are easy to implement and use, they often make it
difficult to control the statistical distributions of important properties such
as the sizes and shapes of the generated trees. For example, the sizes and
shapes of the trees generated via the grow method are highly sensitive to the
sizes of the function and terminal sets. If, for example, one has significantly
more terminals than functions, the grow method will almost always generate
very short trees regardless of the depth limit. Similarly, if the number of
functions is considerably greater than the number of terminals, then the
grow method will behave quite similarly to the full method. The arities
of the functions in the primitive set also influence the size and shape of the