Page 45 - 49A Field Guide to Genetic Programming

4.2 Step-by-Step Sample Run 31

Table 4.1: Parameters for example genetic programming run
2
Objective: Find program whose output matches x + x + 1 over the
range −1 ≤ x ≤ +1.
Function set: +, −, % (protected division), and ×; all operating on floats
Terminal set: x, and constants chosen randomly between −5 and +5
Fitness: sum of absolute errors for x ∈ {−1.0, −0.9, . . . 0.9, 1.0}
Selection: fitness proportionate (roulette wheel) non elitist
Initial pop: ramped half-and-half (depth 1 to 2. 50% of terminals are
constants)
Parameters: population size 4, 50% subtree crossover, 25% reproduction,
25% subtree mutation, no tree size limits
Termination: Individual with fitness better than 0.1 found

the crossover operation will be used twice (each time generating one indi-
vidual), which corresponds to a crossover rate of 50%, while the mutation
and reproduction operations will each be used to generate one individual.
These are therefore applied with a rate of 25% each. For simplicity, the
architecture-altering operations are not used for this problem.
In the fifth and final step we need to specify a termination condition. A
reasonable termination criterion for this problem is that the run will continue
from generation to generation until the fitness (or error) of some individual
is less than 0.1. In this contrived example, our example run will (atypically)
yield an algebraically perfect solution with a fitness of zero after just one
generation.

4.2 Step-by-Step Sample Run

Now that we have performed the five preparatory steps, the run of GP can
be launched. The GP setup is summarised in Table 4.1.

4.2.1 Initialisation

GP starts by randomly creating a population of four individual computer
programs. The four programs are shown in Figure 4.1 in the form of trees.
The first randomly constructed program tree (Figure 4.1a) is equivalent
to the expression x+1. The second program (Figure 4.1b) adds the constant
2
terminal 1 to the result of multiplying x by x and is equivalent to x +1. The
third program (Figure 4.1c) adds the constant terminal 2 to the constant
terminal 0 and is equivalent to the constant value 2. The fourth program
(Figure 4.1d) is equivalent to x.