Page Title

Genetic Algorithms

A genetic algorithm is an algorithm for solving problems using techniques you can observe in nature.

An example:

Let's say there's a species named crawlers. They are living in a bright desert without any problems. Then, because of a natural disaster, they are forced to live in caves, many of them die because they cannot find any food. One day, a crawler is born, which has a genetic change: It is able to see in the dark. Because of this it is able to mate with more female crawlers. The possibility to inherit that genetic "defect" to his descendants is higher than normal, because of the fact that this crawler is stronger and lives longer.

Now back to our algorithm:

This may be a typical chromosome:

1010010111000001

Those would be it's genes:

1010 --> 10
0101 --> 5
1100 --> 9
0001 --> 1

Steps

1. Create a population of a specific number of chromosomes.

2. Calculate the fitness of each chromosome.

3. Select two chromosomes, the chance to be selected is proportional to it's fitness(Look at roulette wheel selection).

4. Check if the selected ones should crossover, after that check if they should mutate.

5. Repeat the steps 2 - 4 til the goal is reached.

Fitness

The fitness of a chromosome decribes how good it is working for solving the problem.

Mutation

The mutation rate is the possibility that a bit changes the value:
1 -> 0; 0 -> 1

Crossover Rate

The crossover rate is the possibility that two chromosomes change their bits at a random index:

Given two chromosomes and the index 8:

10110101 11110001
01101100 11100101

After the crossover, our chromosomes look like this:

10110101 11100101
01101100 11110001

Roulette Wheel Selection

Every chromosome gets a piece of the wheel proportional to it's fitness, so the chance to be chosen is higher with a higher fitness.

Important

Because your Algorithm has to repeat many steps again and again, make sure it is very efficent, StackOverflowErrors can be thrown here easily

Over here you can find my source, easy to understand and not that long.

Genetic Algorithms - An explanation