Page 28 - 49A Field Guide to Genetic Programming

14 2 Tree-based GP

procedure: gen rnd expr(func set,term set,max d,method)

|term set|
1: if max d = 0 or method = grow and rand() <
|term set|+|func set|
then
2: expr = choose random element( term set )
3: else
4: func = choose random element( func set )
5: for i = 1 to arity(func) do
6: arg i = gen rnd expr( func set, term set, max d - 1, method );
7: end for
8: expr = (func, arg 1, arg 2, ...);
9: end if
10: return expr
Notes: func set is a function set, term set is a terminal set, max d is the
maximum allowed depth for expressions, method is either full or grow,
expr is the generated expression in prefix notation and rand() is a function
that returns random numbers uniformly distributed between 0 and 1.
Algorithm 2.1: Pseudocode for recursive program generation with the
full and grow methods.

3
trees produced by grow. Section 5.1 (page 40) describes other initialisation
mechanisms which address these issues.
The initial population need not be entirely random. If something is
known about likely properties of the desired solution, trees having these
properties can be used to seed the initial population. This, too, will be
described in Section 5.1.

2.3 Selection

As with most evolutionary algorithms, genetic operators in GP are applied
to individuals that are probabilistically selected based on fitness. That is,
better individuals are more likely to have more child programs than inferior
individuals. The most commonly employed method for selecting individuals
in GP is tournament selection, which is discussed below, followed by fitness-
proportionate selection, but any standard evolutionary algorithm selection
mechanism can be used.
In tournament selection a number of individuals are chosen at random

3
While these are particular problems for the grow method, they illustrate a general
issue where small (and often apparently inconsequential) changes such as the addition or
removal of a few functions from the function set can in fact have significant implications
for the GP system, and potentially introduce important but unintended biases.