Tournament selection

Tournament selection is a method of selecting an individual from a population of individuals in a genetic algorithm.[1] Tournament selection involves running several "tournaments" among a few individuals (or 'chromosomes') chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for crossover. Selection pressure is easily adjusted by changing the tournament size. If the tournament size is larger, weak individuals have a smaller chance to be selected.

The tournament selection method may be described in pseudo code:

choose k (the tournament size) individuals from the population at random
choose the best individual from pool/tournament with probability p
choose the second best individual with probability p*(1-p)
choose the third best individual with probability p*((1-p)^2)
and so on...

Deterministic tournament selection selects the best individual (when p = 1) in any tournament. A 1-way tournament (k = 1) selection is equivalent to random selection. The chosen individual can be removed from the population that the selection is made from if desired, otherwise individuals can be selected more than once for the next generation. In comparison with the (stochastic) fitness proportionate selection method, tournament selection is often implemented in practice due to its lack of stochastic noise.[2]

Tournament selection has several benefits over alternative selection methods for genetic algorithms (for example, fitness proportionate selection and reward-based selection): it is efficient to code, works on parallel architectures and allows the selection pressure to be easily adjusted.[1] Tournament selection has also been shown to be independent of the scaling of the genetic algorithm fitness function (or 'objective function') in some classifier systems.[3][4]

See also

References

  1. 1 2 Miller, Brad; Goldberg, David (1995). "Genetic Algorithms, Tournament Selection, and the Effects of Noise". Complex Systems. 9: 193–212.
  2. ↑ Blickle, Tobias; Thiele, Lothar (December 1996). "A Comparison of Selection Schemes Used in Evolutionary Algorithms". Evolutionary Computation. 4 (4): 361–394. doi:10.1162/evco.1996.4.4.361.
  3. ↑ Miller, edited by Erick Cant-Paz, James A. Foster, Kalyanmoy Deb, Lawrence David Davis, Rajkumar Roy, Una-May OReilly, Hans-Georg Beyer, Russell Standish, Graham Kendall, Stewart Wilson, Mark Harman, Joachim Wegener, Dipankar Dasgupta, Mitch A. Potter, Alan C. Schultz, Kathryn A. Dowsland, Natasha Jonoska, Julian (2003). Genetic and Evolutionary Computation GECCO 2003 00 Genetic and Evolutionary Computation Conference Chicago, IL, USA, July 1216, 2003 Proceedings, Part II. Berlin: Springer-Verlag Berlin Heidelberg. ISBN 978-3-540-45110-5.
  4. ↑ Goldberg, David; Deb, Kalyanmoy (1991). "A comparative analysis of selection schemes used in genetic algorithms". Foundations of Genetic Algorithms: 69–93.
This article is issued from Wikipedia - version of the 8/17/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.