Page 46 - 49A Field Guide to Genetic Programming

32 4 Example Genetic Programming Run

(a) (b) (c) (d)

- + + *

+ 0 1 * 2 0 x -

x 1 x x -1 -2
x+1 x +1 2 x
2

Figure 4.1: Initial population of four randomly created individuals of gen-
eration 0.

4.2.2 Fitness Evaluation
Randomly created computer programs will typically be very poor at solving
any problem. However, even in a population of randomly created programs,
some programs are better than others. The four random individuals from
generation 0 in Figure 4.1 produce outputs that deviate by different amounts
2
from the target function x +x+1. Figure 4.2 compares the plots of each of
2
the four individuals in Figure 4.1 and the target quadratic function x +x+1.
The sum of absolute errors for the straight line x+1 (the first individual) is
2
7.7 (Figure 4.2a). The sum of absolute errors for the parabola x +1 (the
second individual) is 11.0 (Figure 4.2b). The sums of the absolute errors for
the remaining two individuals are 17.98 (Figure 4.2c) and 28.7 (Figure 4.2d).
As can be seen in Figure 4.2, the straight line x+1 (Figure 4.2a) is closer
2
to the parabola x +x+1 in the range from –1 to +1 than any of three other
programs in the population. This straight line is, of course, not equivalent to
2
the parabola x + x + 1; it is not even a quadratic function. It is merely the
best candidate that happened to emerge from the blind (and very limited)
random search of generation 0.
In the valley of the blind,
the one-eyed man is king.

4.2.3 Selection, Crossover and Mutation

After the fitness of each individual in the population is found, GP then
probabilistically selects the fitter programs from the population to act as
the parents of the next generation. The genetic operations are applied to
the selected individuals to create offspring programs. The important point
is that our selection process is not greedy. Individuals that are known to be
inferior still have some chance of being selected. The best individual in the
population is not guaranteed to be selected and the worst individual in the