Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Tournament selection
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Selection method in genetic algorithms}} '''Tournament selection''' is a method of selecting an individual from a population of individuals in a [[evolutionary algorithm]].<ref>{{cite journal |last1=ZHANG |first1=Byoung-Tak |last2=KIM |first2=Jung-Jib |title=Comparison of Selection Methods for Evolutionary Optimization |journal=Evolutionary Optimization |date=2000 |url=https://citeseerx.ist.psu.edu/document?doi=d356a3e21bb51d0a1258d661066e99fa8fe0ed05}}</ref><ref name=miller-goldberg>{{cite journal|last1=Miller|first1=Brad|last2=Goldberg|first2=David|title=Genetic Algorithms, Tournament Selection, and the Effects of Noise|journal=Complex Systems|date=1995|volume=9|pages=193β212|s2cid=6491320|url=https://pdfs.semanticscholar.org/df6e/e94e2cf14c38e9cff4d2446a50db0aedd4ca.pdf|archive-url=https://web.archive.org/web/20190831154511/https://pdfs.semanticscholar.org/df6e/e94e2cf14c38e9cff4d2446a50db0aedd4ca.pdf|url-status=dead|archive-date=2019-08-31}}</ref> Tournament selection involves running several "tournaments" among a few individuals (or "[[chromosome (genetic algorithm)|chromosome]]s") chosen at random from the population. The winner of each tournament (the one with the best fitness) is selected for [[Crossover (genetic algorithm)|crossover]]. ''[[Selection pressure]]'' is then a probabilistic measure of a chromosome's likelihood of participation in the tournament based on the participant selection pool size, is easily adjusted by changing the tournament size. The reason is that if the tournament size is larger, weak individuals have a smaller chance to be selected, because, if a weak individual is selected to be in a tournament, there is a higher probability that a stronger individual is also in that tournament. == Pseudo Code == 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 the 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 == Variants == 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. There are two variants of the selection: ''with'' and ''without'' replacement. The variant without replacement guarantees that when selecting ''N'' individuals from a population of ''N'' elements, each individual participates in exactly ''k'' tournaments. An algorithm is proposed in.<ref>{{cite journal|first1=David E.|last1=Goldberg|first2=Bradley|last2=Korb|first3=Kalyanmoy|last3=Deb|title=Messy Genetic Algorithms: Motivation, Analysis, and First Results|journal=Complex Systems|date=1989|volume=3|issue=5|pages=493β530|url=https://wpmedia.wolfram.com/uploads/sites/13/2018/02/03-5-5.pdf}}</ref> Note that depending on the number of elements selected, selection ''without'' replacement does ''not'' guarantee that no individual is selected more than once. It just guarantees that each individual has an equal chance of participating in the same number of tournaments. == Advantages == In comparison with the (stochastic) [[fitness proportionate selection]] method, tournament selection is often implemented in practice due to its lack of stochastic noise.<ref>{{cite journal|last1=Blickle|first1=Tobias|last2=Thiele|first2=Lothar|title=A Comparison of Selection Schemes Used in Evolutionary Algorithms|journal=Evolutionary Computation|date=December 1996|volume=4|issue=4|pages=361β394|doi=10.1162/evco.1996.4.4.361|citeseerx=10.1.1.15.9584|s2cid=42718510}}</ref> 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.<ref name=miller-goldberg /> Tournament selection has also been shown to be independent of the scaling of the genetic algorithm [[fitness function]] (or '[[Loss function|objective function]]') in some classifier systems.<ref>{{cite book |editor-last1=CantΓΊ-Paz |editor-first1=Erick |title=Genetic and Evolutionary Computation -- GECCO 2003 : Genetic and Evolutionary Computation Conference Chicago, IL, USA, July 12-16, 2003 Proceedings, Part II |date=2003 |publisher=Springer-Verlag Berlin Heidelberg |location=Berlin, Heidelberg |isbn=978-3-540-45110-5}}</ref><ref>{{cite journal|last1=Goldberg|first1=David|last2=Deb|first2=Kalyanmoy|title=A comparative analysis of selection schemes used in genetic algorithms|journal=Foundations of Genetic Algorithms|date=1991|volume=1|pages=69β93|doi=10.1016/b978-0-08-050684-5.50008-2|isbn=9780080506845|s2cid=938257|url=https://pdfs.semanticscholar.org/feee/c4229f71c6ed155e2f2b732464dbc8c5b93c.pdf|archive-url=https://web.archive.org/web/20180717131907/https://pdfs.semanticscholar.org/feee/c4229f71c6ed155e2f2b732464dbc8c5b93c.pdf|url-status=dead|archive-date=2018-07-17}}</ref> ==References== {{reflist}} [[Category:Selection (evolutionary algorithm)]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Reflist
(
edit
)
Template:Short description
(
edit
)