Sample Trace of the Genetic Algorithm
(from Goldberg)
Step 1. Generate an initial population of random strings. Use weighted selection to
generate n individuals (in this case n=4) for the mating pool.
In this example, one copy each of individuals 1 and 4 and two copies of
individual 2 are selected for the mating pool.
Initial Expected Actual
Population x Value pselect count Count
String (randomly (unsigned f(x) f(i)/sum(f) f(i)/avg(f) (roulette
No. generated) integer) x^2 wheel)
-----------------------------------------------------------------------------
1 0 1 1 0 1 13 169 0.14 0.58 1
2 1 1 0 0 0 24 576 0.49 1.97 2
3 0 1 0 0 0 8 64 0.06 0.22 0
4 1 0 0 1 1 19 361 0.31 1.23 1
-----------------------------------------------------------------------------
Sum 1170 1.00 4.00 4.0
Average 293 0.25 1.00 1.0
Max 576 0.49 1.97 2.0
Step 2: Select two pairs of individuals randomly from the mating pool. For
each pair of individuals, select a crossover point and perform crossover
of the individuals to generate a new population.
This is the next generation of the population.
Depending on the probability of mutation, mutation of individual bits
may occur before or after the crossover.
(NOTE: FOR THIS TABLE THE INDEXES START ON 1)
Mating Pool after Mate Crossover Site
Reproduction (Randomly (Randomly New x f(x)
(Cross site shown) selected) selected) Population Value x^2
-----------------------------------------------------------------------------
0 1 1 0 | 1 2 4 0 1 1 0 0 12 144
1 1 0 0 | 0 1 4 1 1 0 0 1 25 625
1 1 | 0 0 0 4 2 1 1 0 1 1 27 729
1 0 | 0 1 1 3 2 1 0 0 0 0 16 256
-----------------------------------------------------------------------------
Sum 1754
Average 439
Max 729
Step 3: Select 4 individuals from the new population, using weighted selection, for
the new mating pool.
New f(x) pselect Expected Count Actual Count
Population f(i)/sum(f) f(i)/avg(f)
-------------`-----------------------------------------------------
0 1 1 0 0 144 .082 .33 0
1 1 0 0 1 625 .36 1.42 1
1 1 0 1 1 729 .42 1.66 2
1 0 0 0 0 256 .16 .58 1
The new mating pool consists of one each of individuals 2 and 4 and two of
individual 3:
Mating Pool after Mate Crossover Site
Reproduction (Randomly (Randomly New x f(x)
(Cross site shown) selected) selected) Population Value x^2
-----------------------------------------------------------------------------
1 1 0 | 0 1 3 3 1 1 0 1 1 27 729
1 | 1 0 1 1 4 1 1 0 0 0 0 16 256
1 1 0 | 1 1 1 3 1 1 0 0 1 25 625
1 | 0 0 0 0 2 1 1 1 0 1 1 27 729
-----------------------------------------------------------------------------
Sum 2339
Average 585
Max 729
Note that in the new population, the maximum individual has not changed, but
the average fitness value has increased to 585.
New f(x) pselect Expected Count Actual Count
Population f(i)/sum(f) f(i)/avg(f)
-------------`-----------------------------------------------------
1 1 0 1 1 729 .31 1.24 0
1 0 0 0 0 256 .11 .44 1
1 1 0 0 1 625 .27 1.07 1
1 1 0 1 1 729 .31 1.24 1
Here is a good example of where the algorithm may only select three new individuals
for the new mating pool. This algorithm needs to be adjusted to handle such a case.
The algorithm will have to select a duplicate of either individual 1, 3, or 4 so that
there will the mating pool will continue to have 4 individuals.
The individuals may reach a local maximum (a maximum individual that is not the true
max..31) without the proper mutation and crossover probability settings.
The ideal values for these mutation and crossover probabilities will depend upon the
problem.