The GA does not simply bounce around randomly, instead there must be some method behind the bouncing.
This can be described as a set of stages:
1. Have a few guesses – generate a number of random points somewhere in the grid
2. Find out how near they are to the answer
3. Alter them
4. Return to 2 – This loop is performed until an answer is found
It is stage three that is the brains behind the Genetic Algorithm, because, as the name “Genetic” suggests, the way in which the guesses are made has something to do with DNA or Evolution. The guesses are altered using methods which are loosely based on the theories of Evolution first suggested by Charles Darwin.
Before we can demonstrate the ways in which the guesses are generated it is necessary to introduce some terminology: the guesses are referred to as “Chromosomes” and the ways in which these chromosomes can change are referred to as mutation and crossover.
Getting Started
The chromosomes (guesses!) are represented as binary. In our combination example each chromosome has to store a guess for the first digit and a guess for the second digit – for instance a guess may be 9,2. In binary this would be:
1001, 0010
These two separate strings of binary are stuck together to form 1 long string of eight digits – 10010010.
In order to form new guesses we can simply alter individual binary digits (genes!) of the guess (chromosome!), for example, by changing the first digit from a 1 to a 0:
10010010 becomes 00010010
In this way we are able to jump around inside the grid to potentially any position. In order to determine how good the guesses are they must be split in half to produce the two parameters.
Comments