Selekce

Operátor selekce je vlastně realizací Darwinovy teorie přirozeného výběru. Modeluje princip přežití nejlepšího jedince. Vybírá z populace “lepší” jedince, kteří se pak účastní rekombinace (tvorby potomků). Nejedná se ale o jednoduché vybrání N nejlepších jedinců z populace – selekce musí zaručit i to, že se rekombinace může zúčastnit i nejhorší z jedinců v populaci. To je zaručeno pravděpodobnostními mechanismy výběru jedinců – ke každému chromozomu je na základě jeho kvality (kterou získáme ohodnocovací funkcí) určitým způsobem přiřazena pravděpodobnost jeho přežití. Způsob výpočtu pravděpodobnosti přežití jedince je závislý na použité selekční metodě.

  • Ruletová selekce (Roulette-wheel selection)
    Pravděpodobnost přežití jedince je přímo úměrná jeho kvalitě. Rozhodnutí, zda jedinec přežije a objeví se i v další generaci, se dá představit jako náhodný pokus, ve kterém točíme ruletovým kolem (odtud i název metody) a vybíráme vždy toho jedince, na něhož padne kulička. Přitom platí, že čím je jedinec kvalitnější, tím více ruletových políček zabírá.
    Toto selekční schéma s sebou ale nese i řadu problémů: má potíže se škálováním, zvládá pouze maximalizační problémy, způsobuje velké vzorkovací chyby a pro správnou funkci vyžaduje relativně velké populace. Pro nápravu těchto vlastností byla vyvinuta další selekční schémata.
  • Pořadová selekce (Rank selection)
    Pravděpodobnost přežití jedince nesouvisí přímo s jeho kvalitou, ale s jeho umístěním v posloupnosti, kde jsou chromozomy seřazeny podle své kvality. Předpokládejme například, že máme populaci o dvou chromozomech A a B, které byly ohodnoceny f(A)=1 a f(B)=99. Ruletová selekce jim přiřadí pravděpodobnosti přežití p(A)=0.01 a p(B)=0.99. Pořadová selekce je nejprve uspořádá podle velikosti poř(A)=1, poř(B)=2 a nad tímto pořadím už probíhá ruletová selekce. Výsledkem je tedy p(A)=0.33 a p(B)=0.66. Takovýto postup odstraňuje problémy se škálováním (omezuje předčasnou konvergenci), odstraňuje problémy se vzorkováním u malých populací a zvládá maximalizační i minimalizační problémy.
  • Zbytkový stochastický výběr (Reminder stochastic sampling)
    Jedná se o další modifikaci ruletové selekce. Pro všechny jedince v populaci se vypočítá pravděpodobnost jejich přežití. Na základě této pravděpodobnosti se spočítá počet kopií každého jedince v nové populaci: n(i)=p(i)*PopSize (počet kopií i-tého jedince je pravděpodobnost jeho přežití násobená velikostí populace). Tento počet je ale obecně reálné číslo – každý jedinec se zkopíruje pouze tolikrát, kolik udává celá část n(i). Zbytek, tj. součet desetinných částí všech n(i), udává počet ještě neobsazených míst v nové generaci. Na rozdělení těchto míst se už aplikuje klasická ruletová selekce. I tato metoda napravuje vliv malé populace.
  • Turnajová selekce (Tournament selection)
    Tato metoda již není úpravou ruletové selekce, využívá jiného principu. Pro obsazení každého jedince v nové generaci se PopSize-krát uspořádá turnaj. Ze staré generace se náhodně vybírají n-tice chromozomů a do nové generace se vkládají vždy nejlepší jedinci z těchto n-tic. Volbou n se dá také ovlivňovat selekční tlak (čím větší n, tím větší selekční tlak). V krajním případě, kdy n = PopSize, by byla nová generace tvořena ze samých nejlepších jedinců generace (předčasná konvergence).
  • Elitismus
    Elitismus sám o sobě vlastně není selekčním schématem. Je to jen jakási volba, kterou se dají rozšířit ostatní selekční mechanismy. Pokud se jakékoli selekční schéma označí za elitistické, znamená to, že n nejlepších jedinců je v každé generaci bezprostředně zkopírováno do generace následující. Výhodou této volby je, že se nemusí zvlášť udržovat dosud nejlepší nalezené řešení (BSF – best-so-far), protože nemůže během vývoje vlivem náhodných jevů odumřít.