Úvod a cíle

Turnajová selekce byla navržena Wetzelem [25] a stala je jednou z nejoblíbenějšího a efektivního selekčního schématu ze selekčních přístupů. Vlastnosti tohoto přístupu jsou známé a byly mnohokrát analyzovány mnohými vědci např. Blickle a Thiele, Miller a Goldberg, Lee atd. [6]

Podstatou přístupu je výběr jedinců z populace , mezi nimiž se uspořádá turnaj. Vítězové zápasu se stanou jedinci selektované populace k páření .

Experimenty ukazují, že turnajová selekce spojená se samostatným uchováváním dosud nejlepšího řešení dává nejpříznivější výsledky. V reálných aplikacích GA se turnajová selekce používá téměř výhradně.

Poznamenejme, že pro takto upravené genetické algoritmy již neexistuje žádný aparát, který by vysvětlovat jejich chování. Přesto fungují velmi uspokojivě. Všimněme si rovněž, že všechny selekční mechanismy vycházejí jen z porovnávání kvality jedinců a že nevyžadují žádné doplňkové vlastnosti optimalizované účelové funkce, jako např. její diferencovatelnost. Jediným požadavkem je možnost vyčíslení kvality individua spolu s vytvořením rozumného selekčního tlaku. To tedy vylučuje použití GA na třídy funkcí, kterou jsou skoro všude konstantní. [8]

Jako příklad uvažujme turnajovou selekci (se substitucí) dvou jedinců k=2. Pro každý jednotlivý zápas jsou soupeři vybíráni náhodně (podle rovnoměrného rozdělení) a vítězové budou umístěni do populace pro páření . Za předpokladu, že bude obsahovat tolik stejných jedinců jako počáteční populace, každý jedinec se v průměru zúčastní dvou zápasů. Nejlepší kandidát řešení z populace vyhraje všechny zápasy a bude vybrán do , a tudíž bude průměrně obsahovat jeho dvě kopie (algoritmus se substitucí). Medián (hodnota, jež dělí řadu podle velikosti seřazených výsledků na dvě stejně početné poloviny) jedince v populaci je lepší než 50 % vyzývatelů, ale také zároveň prohrál oproti 50 %. Proto tento jedinec bude zhruba průměrně jedenkrát vybrán do . Oproti tomu, nejhorší jedinec v populaci prohraje všechny zápasy s jinými jedinci a může vyhrát pouze tehdy, pokud bude bojovat sám se sebou, což se stane s pravděpodobností . Není tudíž schopen se průměrně účastnit reprodukce protože .

TournamentSelect_r - v algoritmu (viz ) je popsán proces turnajové selekce se substitucí. Nejprve je vytvořena prázdná množina jedinců, do které budou postupně umístěni vybraní jedinci (řádek 2). Jedinci jsou setříděni na základě svých fitness hodnot (řádek 3). Do populace pro páření bude vybráno tolik jedinců, kolik je hodnota (řádek 4). Náhodně vybraný jedinec - značí ho index ve skupině (řádek 5), bude zápasit s dalšími (řádek 6) náhodně vybranými jedinci - značí je též index ve skupině (řádek 7) v k-1 párových zápasech. Zápas vyhraje a bude vybrán do populace k páření ten jedinec (řádek 8), který má nejlepší hodnotu fitness ze všech vybraných jedinců v k-1 soutěžních kolech (v případě minimalizace - menší hodnotu fitness - viz řádek 7). Jako výsledek tohoto algoritmu je navrácena populace obsahující jedince k páření (řádek 10). V algoritmu může jedinec soupeřit sám proti sobě - své kopii. Tato situace je svým způsobem v realitě neproveditelná, ale uvědomme si, že takoví jedinci mají stejnou hodnotu fitness a v takovém případě vyhraje první jedinec a ne jeho kopie, protože díky párovému porovnání v algoritmu (řádek 7) je vybrán první, svým způsobem pravý, jedinec.

TournamentSelect_w1   - turnajová selekce - bez substituce (viz ) je, v podstatě taková varianta algoritmu, kde každý vítěz zápasu, se už nemusí účastnit dalších zápasů - je odstraněn z vstupní populace (řádek 9) - listiny, kde jsou zapsáni všichni jedinci, kteří se mohou zápasit.

TournamentSelect_w2 - turnajová selekce - bez substituce (viz ) - podstata tohoto algoritmu je totožná s předchozím algoritmem, s tím rozdílem, že všichni jedinci - jejich indexy - jsou vybíráni do jednoho celkového kola - jednoho seznamu (řádek 10), ve kterém už se nesmí nacházet (řádek 9). Z tohoto seznamu je vybrán hlavní vítěz s nejmenší hodnotou fitness (řádek 12). Tento postup je opakován tolikrát, kolik má být vybráno jedinců k páření (řádek 4).