GENETIC ALGORITHMS TUTORIAL|
This is a tutorial which guides you through the process of making a genetic algorithm (GA) program. To make and run the program, you'll need to use a C compiler on your computer.
A GA tries to simulate the process of evolution that happens on Earth. First you create a bunch of organisms who each have a unique set of genes (usually chosen randomly). They are the first generation. Then you evaluate and rank the fitness of each of the organizms according to some criteria (e.g. which creature gets the fattest after two years). Then you chose some of the more fit organisms and let them reproduce with each other to produce the second generation. One the first generation has reproduced, all the members of the first generation "die". Then you evaluate the second generation and the cycle repeats.
The GA keeps producing new generations until a perfect organism has been created or we get to, say, the 1000th generation and decide to stop. A run is the process of doing all the generations.
The program can be seen as a small hierarchy of functions which are all in one file:
Here is the code for main():
finalGeneration = DoOneRun();
printf("The final generation was: %d\n",
We include stdio.h so we can use the printf() function to print how many generations it took to get a perfect organism.
Our first real task is to allocate memory to store the organisms in. The only information we need to store about each organism is its genetics (i.e. its set of genes). We'll start with 100 organisms who each have 20 genes. We'll store each organism's genes as an array of char variables (not a "string" per se). Here is the code for AllocateMemory():
#define NUMBER_ORGANISMS 100
#define NUMBER_GENES 20
char **currentGeneration, **nextGeneration; // globals
(char**)malloc(sizeof(char*) * NUMBER_ORGANISMS);
(char**)malloc(sizeof(char*) * NUMBER_ORGANISMS);
(char*)malloc(sizeof(char) * NUMBER_GENES);
(int*)malloc(sizeof(int) * NUMBER_ORGANISMS);
Notice that currentGeneration and nextGeneration are two global pointers which we'll use so we can manipulate the organism data in our various functions. modelOrganism is what we'll use as the "perfect" organism. Later on, we'll be comparing our regular organisms with the model to see how perfect they are. Conceptually though, the model organism isn't a real organism the way the others are. I hope the rest of the code isn't too dense to understand, I'll be skipping over most of the coding-specific issues for brevity.
First we initialize the organisms, then we use a simple loop to go from one generation to the next until a perfect generation is found. A perfect generation is one that has at least one organism which has the exact same genes as the model organism. When we get to a perfect generation, we return the generation number.
#define FALSE 0
#define TRUE 1
int generations = 1;
int perfectGeneration = FALSE;
perfectGeneration = EvaluateOrganisms();
if( perfectGeneration==TRUE ) return generations;
You'll notice I've written the code in a very simple way so it is easier to learn. Latter on, I'll give a more concise and efficient version of the program.
Before we start each run, we need to randomize the genes of the normal organisms and the model. Notice that we don't need to do anything to the nextGeneration data structure since it is only a temporary holding area we use when we're producing the following generation.
Each gene can be one of four alleles: C, G, A, or T. But for simplicity, we'll represent their values as 0, 1, 2, and 3, respectively.
#define ALLELES 4
// initialize the normal organisms
The evaluation stage has two purposes. Primarily, we have to determine the fitness of all the organisms so that later on, in ProduceNextGeneration(), we'll know which were the better organisms and therefore which should reproduce more often. Our secondary purpose is to decide if we've got a perfect generation, one with at least one organism that has the same genetics as the model.
Each organism's fitness is simply the number of its genes that match the model (they have to be in the right position too). So, if the organism we're considering is AAAAAACAAAAAAAAAAAAA and the model is CCCCCCCCCCCCCCCCCCCC, then the organism gets a fitness of 1. The one point comes from both the model and the organism having a 'C' as their seventh gene.
We introduce another global variable totalOfFitnesses here. It is simply the sum of each organisms fitness. Ignore it for now, we'll use it later on in SelectOneMember(). Here's the code:
#define MAXIMUM_FITNESS NUMBER_GENES
totalOfFitnesses = 0;
Once we've figured out the fitness of all the organisms in our current generation, we can select the best organisms and reproduce them. We'll temporarily store each organism of the new generation, the children, in the nextGeneration data structure. After we've created all the children, we copy them into the currentGeneration data structure and the reproduction phase is complete.
Now a little more detail on how the children are created. For each child, we first use SelectOneMember() twice to get the two parents. Then we randomly select a crossover point and start copying over the parents genes to the child. The genes to the left of the crossover point are copied over from parent one, while the genes right of the crossover point come from parent two.
Each time we copy over a gene, there is a chance it will mutate into a random gene.
#define MUTATION_RATE 0.001
// fill the nextGeneration data structure with the
How you select organisms for reproduction will determine how effective your GA is. The simplest method is roulette wheel sampling, which we'll use here. Metaphorically, each organism is "assigned" a slice of the roulette wheel. The size of the slice each organism gets is proportional to its fitness. Then, we "spin" the wheel and whichever slice we land on, that organism gets selected.
How we'll implement this is best shown with a visual example. Imagine we have only five organisms with fitnesses of 3, 2, 0, 5, and 2. So the totalOfFitnesses is 12. I'll abbreviate organismsFitnesses below to oF. We "line up" the organisms from left to right as follows:
Notice oF didn't get any slots since its fitness was 0. Anyway, the process is, first we pick a random number from 1 to 12. Then we start adding up organisms from left to right until our running total is as big as that number. Suppose we randomly chose 9. Then we'd start by adding oF to runningTotal to get 3, which isn't as big as than 9 so we keep going. Next we add oF so runningTotal is 5. After adding oF the total is still 5. Finally, when we add oF, and runningTotal becomes 10, which is as big as 9, so we select oF.
Here's how we implement it:
runningTotal = 0;
randomSelectPoint = rand() % (totalOfFitnesses + 1);
for(organism=0; organism= randomSelectPoint) return organism;
The Complete Code
Now that we've seen all the functions, here is the complete program. Here's an insanely dense version.
February 24, 1999