The workings of a Genetic Algorithm

Genetic algorithms are a way of solving problems by mimicking processes that mother nature uses. They use the same combination of selection, recombination and mutation to evolve a solution to a problem. Solutions are encoded on chromosomes. The chromosomes are altered using methods which are loosely based on the theories of Evolution first suggested by Charles Darwin.

A genetic algorithm works like this: A population is created with chromosomes created randomly. The chromosomes in the population are then evaluated to rate their fitness. Two chromosomes are then selected, the higher the fitness of the chromosome, the higher chance it has of being selected to "reproduce". These two chromosomes then crossover to create a new chromosome. This process continues until a suitable solution has been found or a certain number of generations have passed, depending on the need of the programmer.

Outline of the Basic Genetic Algorithm
1. [Start] Generate random population of n chromosomes (suitable solutions for the problem)
2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population
3. [New population] Create a new population by repeating following steps until the new population is complete
- [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected)
- [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents.
- [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome).
- [Accepting] Place new offspring in a new population
4. [Replace] Use new generated population for a further run of algorithm
5. [Test] If the end condition is satisfied, stop, and return the best solution in current population
6. [Loop] Go to step 2