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
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
g1 = 001110011
g3 = 000001011
Child1 = 001111011
Child2 = 000000011
Crossover 2 between g4 and g3
g4 = 001101010
g3 = 000001011
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.
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.
included in the zip file is an exe which demonstrates the
fundamentals of various search and optimisation techniques.
Also included in the zip file is an exe which demonstrates the fundamentals of various search and optimisation techniques.