Putting It All Together
Now that we have learnt the basic theory behind the GA, lets put it all
together. Imagine a simple scenario of 3 “wheels” on the
combination lock each with 8 possible positions from 0 to 7. This
would give us the problem space:
Stage 1 – generate 4 random guesses – g1, g2, g3, g4
g1 = 1,6,3 = 001110011
g2 = 6,5,1 = 110101001
g3 = 0,4,3 = 000001011
g4 = 1,5,2 = 001101010
Stage 2 – evaluate how good they are – their fitness
In a basic introduction such as this, it is not necessary to go into great
deal with the evaluation stage, aka – the fitness function, however it
is necessary to understand that this function will provide each guess
with a “score” depending on how good they are.
Stage 3 – pick the parents
There
are many ways to choose which guesses become parents, perhaps the
easiest to imagine is to create a pie chart which represents each
guesses share of the total points. First add up the points of each guess – g1 score = 2.12, g2 score = 1.61, g3 score = 4, g4 score = 3.26
Total score = 10.99
g1 – total share of pie = 20%
g2 – total share of pie = 15%
g3 – total share of pie = 36%
g4 – total share of pie = 29%
Then pick a random point on the pie and whichever guess you are pointing at becomes a parent, this is repeated 4 times.
Random parents = g1, g3, g4, g3
Stage 4 – breed the parents
Crossover 1 between g1 and g3
Before –
g1 = 001110011
g3 = 000001011
After –
Child1 = 001111011
Child2 = 000000011
Crossover 2 between g4 and g3
Before -
g4 = 001101010
g3 = 000001011
After –
Child3 = 001101011
Child4 = 000001010
The children now become the next generation:
g1 = c1 = 001111011
g2 = c2 = 000000011
g3 = c3 = 001101011
g4 = c4 = 000001010
Stage 5 - Random mutation is applied to a random 1% of the population:
g1 = 001111011
g2 = 010000011
g3 = 001101011
g4 = 000001010
Return to stage 2 – This process is repeated a predefined number of times. In
a simple example like this the solution will not take long to converge
upon (the solutions will all become the same) so a relatively low
number of generations are necessary.
Downloads
Feel
free to download the samples.zip file which contains the C++ source
code for a simple Genetic Algorithm as well as the source code for a
Real-Coded GA, which is fundamentaly the same except the
population consists of real numbers instead of binary digits.
Also
included in the zip file is an exe which demonstrates the
fundamentals of various search and optimisation techniques.