Úvod a cíle

Selekce (Selection) je operace užívaná k výběru skupiny jedinců (Mating Pool) pro reprodukci ze seznamu jedinců (splňují podmínku přípustnosti řešení) - populace . [I3]

Selekce takových potenciální rodičů (Parents) určených k páření ( ), tj. k reprodukci potomků (dětí - Children), může probíhat deterministicky, nebo náhodně - záleží na řešeném problému, tj. jaká budou zvolena kritéria selekce, např. hodnota fitness.

V zásadě existují dvě třídy algoritmů selekce: [6]

1. Bez substituce (Without Replacement)
2. Se substitucí (With Replacement)

ad 1. - Selekce bez substituce - každý jedinec ze seznamu kandidátů řešení se může účastnit reprodukce maximálně jednou, tj. výsledný seznam jedinců pro reprodukci obsahuje každého jedince pouze jedenkrát - není umožněna duplicita prvků. Tato třída algoritmů bude značena dolním indexem .

kde:

•       … Požadovaná velikost populace jedinců vybraných k reprodukci - .

•       … Populace určená k reprodukci.

•       … Seznam jedinců (splňujících podmínku přípustnosti řešení) ze kterých se vybírá populace .

V některých případech u selekce bez substituce existují jistá omezeni na .

ad 2. - Selekce se substitucí - skupina jedinců určených k reprodukci může obsahovat stejného jedince několikrát. To je hlavním důvodem, proč je populace jedinců určených k páření reprezentována jako seznam a ne jako množina (množina - nemůže obsahovat stejného jedince dvakrát). Tato třída algoritmů bude značena dolním indexem . Oproti předchozí variantě je varianta selekčních algoritmů se substitucí využívána více. Jedná se zejména o případ, kdy počet jedinců vybraných k reprodukci je větší než počet jedinců vstupního seznamu jedinců v , tj. .

Selekční algoritmy mají velký vliv na výkonnost evolučních algoritmů.

Selekce může pracovat přímo s jedinci použitím komparační funkce nebo se vztahuje k již provedenému ohodnocení jedinců hodnoty fitness.

Pro minimalizaci hodnot fitness funkce dvou jedinců tedy platí algoritmus komparační funkce (viz ).

Pro maximalizaci hodnot fitness funkce dvou jedinců tedy platí:

Další možnou klasifikací selekčního algoritmu je notace - značí počet rodičů a - počet zplozených potomků.

Obecně lze říci, že selekci lze např. implementovat jako: [I4]

1. Funkce fitness ohodnotí každého jedince pomocí hodnot fitness, které jsou dále normalizovány, tj. hodnota fitness každého jedince je vydělena součtem všech hodnot fitness v populaci (suma všech takto získaných hodnot fitness jedinců je rovna jedné).
2. Populace je setříděna sestupně podle hodnot fitness.
3. Jsou vypočteny akumulované normalizované hodnoty fitness (hodnota fitness jedince je připočtena k hodnotám fitness všech předchozích jedinců, kde poslední akumulovaná hodnota fitness je rovna jedné).
4. Náhodné číslo v rozmezí od 0 do jedné.
5. Vybraný jedinec je prvním jedincem, jehož akumulovaná normalizovaná hodnota je větší než náhodné číslo.

V návaznosti na předchozí členění se ve studijních článcích zaměříme na vybrané základní metody selekce a to:

• Selekce přímo úměrná fitness.
• Ruletová selekce.
• Turnajová selekce.