Overview of Genetic Algorithms
A genetic algorithm searches a (potentially) vast
solution space for an optimal (or near optimal) solution
to the problem at hand.
- Solutions are encoded as strings over a finite alphabet
(often 0 and 1).
- A fitness function (or objective function)
is used to evaluate each string (solution).
- Bits and pieces of the fittest strings (solutions)
are used to generate new strings (solutions).
Each time step (or generation) of the algorithm produces
a population of possible solutions based on the population
from the previous time step (or generation).
- Natural selection:
strings with a good fitness value survive from one generation
to the next with high probability; strings with a poor fitness
value perish with high probability.
- Reproduction: two strings chosen via natural selection
mate (via crossover, which picks a position within the strings
at random and exchanges the upper halves of the two strings)
to produce new strings.
- Mutation: strings can undergo spontaneous changes
(with small probability)
to produce new strings in a different part of the solution space.
- Randomly initialize the population of solutions
Use a population sufficiently large to be representative of
the search space as a whole.
- Evaluate the fitness of each individual
That is, evaluate the fitness function for each solution in the
population to see if the termination criteria for optimality are met.
- While termination condition does not hold
- Replicate individuals based on their fitness
Use a weighted roulette wheel to reproduce strings in the
next generation in proportion to their fitness.
- Transform the individuals in the population
- Randomly pick two parents from the population
- Crossover the parents (pick a random point in the
strings and exchange their top parts) to produce offspring
- Mutate each offspring (randomly decide whether to
flip each bit in the string) optionally flip each bit)
- Evaluate the fitness of each new individual
Selection using a Roulette Wheel
Select an individual for the next generation
in proportion to its contribution to the total
fitness of the population
/* Assumes fitness values in global array fitness */
/* Returns a single selected individual */
int select (real sum_of_fitness_values)
index = 0;
sum = 0.0;
/* Random number between 0 and fitness total */
r = drand48() * sum_of_fitness_values;
sum = sum + fitness[index];
while (index < SIZE-1) and (sum < r);
A GA can be expected to produce good solutions, but might never
find a perfect solution.
When is a good solution 'good enough'?
When should a GA terminate?
- after a prespecified number of generations.
- when an individual solution reaches a prespecified level of fitness.
- when the variation of individuals from one generation to the next
reaches a prespecified level of stability.