Турнирна селекция

Турнирна селекция (на английски: tournament selection) е една от разновидностите на генетичния оператор селекция, посредством който определен брой индивиди от дадено поколение на генетичен алгоритъм биват избирани да продължат в следващото поколение.[1] Турнирната селекция включва провеждането на няколко „турнира“ помежду индивидите („хромозомите“, кандидат-решенията на оптимизационната задача), избрани на случаен принцип от популацията. Победителят от всеки от турнирите, т.е. индивидът с най-висока стойност на фитнес функцията, се избира за кръстосване.

Размерът на турнира може да се регулира, като по-големият размер означава, че индивидите с по-ниски фитнес функции имат по-малък шанс да бъдат избрани да продължат към следващото поколение.

Методът на турнирната селекция може да се опише в псевдокод по следния начин:

избират се k (размер на турнира) индивиди от популацията на случаен принцип
най-добрият индивид (измежду индивидите) в турнира се избира с вероятност p
вторият най-добър индивид в турнира се избира с вероятност p*(1-p)
третият най-добър индивид в турнира се избира с вероятност p*((1-p)^2)
и т.н.

Детереминистичната турнирна селекция при p = 1 избира най-добрия индивид във всеки турнир. Турнирна селекция при k = 1 е равнозначна на случайна селекция. Веднъж избран да продължи към следващото поколение, един индивид следва да бъде отстранен от популацията, за да не бъде избран повторно. В сравнение със стохастичната селекция на принципа на рулетката, турнирната селекция често се имплементира на практика заради липсата при нея на стохастичен шум.[2]

Турнирната селекция има няколко предимства пред други алтернативни техники на селекция, като селекцията на принципа на рулетката и селекцията с награди (reward-based selection):

  • лесна е за програмиране,
  • работи на паралелни архитектури
  • позволява лесно да се настройва размерът на турнира.[1]

Показано е, че в някои класификатори (classifier systems) турнирната селекция е независима от мащаба на фитнес функцията на генетичния алгоритъм.[3][4]

Източници

[редактиране | редактиране на кода]
  1. ↑ а б Miller, Brad и др. Genetic Algorithms, Tournament Selection, and the Effects of Noise // Complex Systems 9. 1995. с. 193 – 212. Посетен на 17 август 2015.
  2. ↑ Blickle, Tobias и др. A Comparison of Selection Schemes Used in Evolutionary Algorithms // Evolutionary Computation 4 (4). December 1996. DOI:10.1162/evco.1996.4.4.361. с. 361 – 394.
  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. 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, 2003. ISBN 978-3-540-45110-5.
  4. ↑ Goldberg, David и др. A comparative analysis of selection schemes used in genetic algorithms // Foundations of Genetic Algorithms. 1991. с. 69 – 93.
  Тази страница частично или изцяло представлява превод на страницата Tournament selection в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​