Genetic Algorithms

From Algorithmist
Revision as of 13:56, 28 November 2009 by 69.47.124.80 (Talk)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Genetic Algorithms are a search technique inspired by the natural process of genetic evolution. The solution space is modelled by chromosomes, or potential solutions. A population of a finite size is defined as a group of chromosomes. The population is initialized with random chromosomes to a given problem. Each chromosome is measure to see which is more correct, called fitness, and then goes through one of two transformations.

Similar to natural processes, these solutions "breed" in what is called a cross-over. Cross-overs take part of a chromosome and swap it with part of another chromosome in a given population. These creates a new potential solution which can be measured against it's parents and fellow children in the next round. The least fit chromosomes die out of the population.

To introduce diversity into the population, and avoid local minima and maxima, mutations are used. During the cross-over operation there is a given probability that a chromosome will mutate by introducing new data into the potential solution that may or may not have already been present in the population.

[edit] Pitfalls

The population size, method for selecting cross-overs, as well as the percentage chosen for mutations are all sources for error in an implementation. A small population for a large solution space may not find the correct answer; depending on the problem, selecting the fittest chromosomes for cross-over may create more fit children; and too frequent mutations will degrade the algorithm to an exhaustive search while to few with reduce it's accuracy.

A huge potential for error comes from a lack of diversity in a population. This issue is directly related to population size and mutation probabilities.


[edit] Examples

  1. http://www.lukejduncan.com/2009/11/genetic-algorithms---closest-pair-revisted.php
  2. http://www.generation5.org/content/2003/gahelloworld.asp
Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox