Genetic algorithm

From Glossary

Jump to: navigation, search

Genetic algorithms (GAs) are a class of algorithms inspired by the mechanisms of genetics, which has been applied to global optimization (especially for combinatorial programs). It requires the specification of three operations (each is typically probabilistic) on objects, called "strings" (these could be real-valued vectors):

  1. Reproduction - combining strings in the population to create a new string (offspring);

    Example: Taking 1st character from 1st parent + rest of string from 2nd parent:

    LaTeX: 
[001001] + [111111] \rightarrow [011111]
  2. Mutation - spontaneous alteration of characters in a string;

    Example: Just the left-most string:

    LaTeX: 
[001001] \rightarrow [101001]

  3. Crossover - combining strings to exchange values, creating new strings in their place.

    Example: With crossover location at 2:

    LaTeX: 
[001001]  &  [111111] ===> [001111], [111001]
These can combine to form hybrid operators, and the reproduction and crossover operations can include competition within populations. Here is a generic GA (strategy):

0. Initialize population.

1. Select parents for reproduction and GA operators (viz., mutation and crossover).
2. Perform operations to generate intermediate population and evaluate their fitness values.
3. Select members of population to remain with new generation.

Repeat 1-3 until some stopping rule is reached.

The original GA (1973, by John Holland) used crossover and total population replacement. This means a population with 2N objects (called chromosomes) form N pairings of parents that produce 2N offsprings. The offsprings comprise the new generation, and they become the total population, replacing their parents. More generally, a population of size N produces an intermediate population of N+M, from which Ñ is kept to form the new population. One way to choose which Ñ survive is by those with the greatest fitness values – survival of the fittest.

Views
Personal tools