An Introduction to Genetic Algorithms

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.