Výběr turnaje - Tournament selection

Výběr turnaje je metoda výběru jednotlivce z populace jednotlivců v a genetický algoritmus.[1] Výběr turnajů zahrnuje provozování několika „turnajů“ mezi několika jednotlivci (nebo „chromozomy ") náhodně vybrán z populace. Je vybrán vítěz každého turnaje (ten s nejlepší kondicí) crossover. Selekční tlak, pravděpodobnostní měřítko pravděpodobnosti účasti chromozomu na turnaji na základě velikosti skupiny účastníků pro výběr, se snadno upravuje změnou velikosti turnaje, protože je-li velikost turnaje větší, mají slabí jedinci menší šanci na výběr , protože pokud je vybrán slabý jedinec, který se má zúčastnit turnaje, je větší pravděpodobnost, že se na tomto turnaji zúčastní i silnější jedinec.

Způsob výběru turnaje lze popsat v pseudokódu:

náhodně vyberte k (velikost turnaje) jednotlivce z populacevyberte nejlepšího jednotlivce z turnaje s pravděpodobností pvyberte druhého nejlepšího jedince s pravděpodobností p * (1-p) vyberte třetího nejlepšího jedince s pravděpodobností p * ((1-p) ^ 2) a tak dále

Deterministický výběr turnaje vybírá nejlepšího jednotlivce (když p = 1) na jakémkoli turnaji. Jednosměrný turnaj (k = 1) výběr je ekvivalentní náhodnému výběru. Existují dvě varianty výběru: s a bez výměna, nahrazení. Varianta bez náhrady to zaručuje při výběru N jednotlivci z populace N prvků se každý jedinec účastní přesně k turnaje. Algoritmus je navržen v [2]. Všimněte si, že v závislosti na počtu vybraných prvků výběr bez výměna ano ne zaručit, že žádný jednotlivec nebude vybrán více než jednou. Jen zaručuje, že každý jednotlivec má stejnou šanci zúčastnit se stejného počtu turnajů.

Ve srovnání s (stochastickou) fitness přiměřený výběr metoda, výběr turnaje je často implementován v praxi kvůli jeho nedostatku stochastického šumu.[3]

Výběr turnajů má oproti alternativním metodám výběru genetických algoritmů několik výhod (například fitness přiměřený výběr a výběr založený na odměnách ): je efektivní kódovat, pracuje na paralelních architekturách a umožňuje snadné nastavení výběrového tlaku.[1] Ukázalo se také, že výběr turnajů je nezávislý na škálování genetického algoritmu fitness funkce (nebo 'Objektivní funkce ') v některých klasifikačních systémech.[4][5]

Viz také

Reference

  1. ^ A b Miller, Brad; Goldberg, David (1995). „Genetické algoritmy, výběr turnajů a účinky hluku“ (PDF). Složité systémy. 9: 193–212. S2CID  6491320.
  2. ^ Goldberg, David E .; Korb, Bradley; Deb, Kalyanmoy (1989). „Chaotické genetické algoritmy: motivace, analýza a první výsledky“ (PDF). Složité systémy. 3 (5): 493–530.
  3. ^ Blickle, Tobias; Thiele, Lothar (prosinec 1996). "Porovnání schémat výběru použitých v evolučních algoritmech". Evoluční výpočet. 4 (4): 361–394. CiteSeerX  10.1.1.15.9584. doi:10.1162 / evco.1996.4.4.361. S2CID  42718510.
  4. ^ Miller, editace 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). Konference o genetických a evolučních výpočtech GECCO 2003 00 Konference o genetických a evolučních výpočtech v Chicagu, IL, USA, červenec 1216, 2003 Sborník, část II. Berlín: Springer-Verlag Berlin Heidelberg. ISBN  978-3-540-45110-5.CS1 maint: další text: seznam autorů (odkaz)
  5. ^ Goldberg, David; Deb, Kalyanmoy (1991). „Srovnávací analýza výběrových schémat používaných v genetických algoritmech“ (PDF). Základy genetických algoritmů. 1: 69–93. doi:10.1016 / b978-0-08-050684-5.50008-2. ISBN  9780080506845. S2CID  938257.