wiki:Documentation/Reference/Genetic Algorithm

(Standard) Genetic Algorithm

Genetic algorithms (GAs) were introduced in the early 70s by John Holland as what is now known as the canonical genetic algorithm using binary solution encoding, a fitness-proportional selection, single point crossover, and bit flip mutation. John Holland proved that in this configuration so-called building blocks evolve over time which in turn are assembled in individual solutions such that finally a reasonably good solution is achieved ( Holland 1975, Goldberg 1989). Over the years the GA community has expanded the application of genetic algorithms to other domains and introduced additional encoding schemes as well as crossover and mutation operators.

The genetic algorithm described here is based on what has been established as the standard genetic algorithm (SGA) (Dumitrescu et al. 2000) that applies crossover to all individuals, mutates them with a certain, and generally low, probability, and replaces the whole parent generation with the new children except for a small number of elite parent individuals that are allowed to survive.

Algorithm Parameters:

Parameter Description
Analyzer The operator used to analyze each generation.
Crossover The operator used to cross solutions.
Elites The numer of elite solutions which are kept in each generation.
MaximumGenerations The maximum number of generations which should be processed.
MutationProbability The probability that the mutation operator is applied on a solution.
Mutator The operator used to mutate solutions.
Population Size The size of the population of solutions.
Seed The random seed used to initialize the new pseudo random number generator.
Selector The operator used to select solutions for reproduction.
SetSeedRandomly True if the random seed should be set to a random value, otherwise false.

Is there a sample/tutorial?

Yes, actually. HeuristicLab comes with a pre-configured SGA that solves the "ch130" traveling salesman problem from the TSPLIB. Have a look at the description here.

References:

  • Dumitrescu, D., B. Lazzerini, L. C. Jain, and A. Dumitrescu. 2000. Evolutionary computation. The CRC Press International Series on Computational Intelligence. CRC Press.
  • Goldberg, D. E. 1989. Genetic algorithms in search, optimization and machine learning. Addison-Wesley.
  • Holland, J. H. 1975. Adaption in natural and artificial systems. University of Michigan Press.
Last modified 7 years ago Last modified on 02/17/11 10:27:31