Tournament selection
|
|
Tournament selection is one of many methods of selection in genetic algorithms which runs a "tournament" among a few individuals and selects the winner (the one with the best fitness) for crossover.
Selection pressure can be easily adjusted by changing the tournament size. If the tournament size is higher, weak individuals have a smaller chance to be selected.
Tournament selection 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*(p*(1-p)) and so on...
Deterministic tournament selection selects the best individual in any tournament which is the same as p=1. 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.
Tournament selection has several benefits: it is efficient to code, works on parallel architectures and allows the selection pressure to be easily adjusted.
External link
"Genetic Algorithms, Tournament Selection, and the Effects of Noise" (http://www.assuredigit.com/tech_doc/more/Goldberg_GA_tournament_seletion_and_the_effects_of_noise.pdf) by Brad L. Miller and David E. Goldberg (PDF link).