IX. Selekce

Úvod

Jak už víte ze schématu GA, chromozomy se z populace vybírají jako rodiče pro křížení. Otázkou je, jak tyto chromozomy vybírat. Podle Darwinovy teorie evoluce by měli přežívat nejzpůsobilejší jedinci a vytvářet nové potomky. Existuje mnoho způsobů, jak vybrat nejlepší chromozomy, např. ruletová selekce, Boltzmannova selekce, turnajová selekce, selekce podle pořadí, selekce se stálou populací a další.

Některé z nich budou popsány v této kapitole.

Ruletová selekce

Rodiče se vybírají podle své kvality. Čím lepší chromozomy jsou, tím větší je jejich šance na výběr. Představte si ruletu, na níž jsou umístěny všechny chromozomy populace, přičemž každý zabírá výsek úměrně své kvalitě, jak ukazuje následující obrázek.

graph

Pak se na ruletu hodí kulička a ta vybere chromozom. Chromozomy s vyšší kvalitou budou vybírány častěji.

To lze simulovat následujícím algoritmem.

  1. [Sum] Spočítej součet všech hodnot účelové funkce chromozomů v populaci - součet S.
  2. [Select] Vygeneruj náhodné číslo z intervalu (0,S) - r.
  3. [Loop] Procházej populaci a průběžně přičítej hodnoty účelové funkce od 0 - součet s. Jakmile se součet s stane větším než r, zastav a vrať chromozom na této pozici.

Samozřejmě, krok 1 se provádí jen jednou pro každou populaci.

Selekce podle pořadí

Předchozí metoda může způsobovat problémy, když se hodnoty účelové funkce příliš liší. Pokud například nejlepší chromozom zabírá 90 % rulety, ostatní chromozomy budou mít jen malou šanci na výběr.

Selekce podle pořadí nejprve populaci seřadí a potom každý chromozom dostane hodnotu účelové funkce podle tohoto pořadí. Nejhorší chromozom dostane hodnotu 1, druhý nejhorší dostane 2 atd., zatímco nejlepší chromozom dostane hodnotu N (počet chromozomů v populaci).

Na následujících obrázcích můžete vidět, jak se situace změní, když je kvalita nahrazena pořadím.

graph

Situace před seřazením podle pořadí (graf hodnot účelové funkce)

graph

Situace po seřazení podle pořadí (graf pořadových čísel)

Po tomto kroku má šanci být vybrán každý chromozom. Tato metoda ale může vést k pomalejší konvergenci, protože nejlepší chromozomy už se od ostatních tolik neliší.

Selekce se stálou populací

Nejde o konkrétní metodu výběru rodičů. Hlavní myšlenkou tohoto přístupu je, že velká část populace by měla přežít do další generace.

GA pak pracuje takto: v každé generaci se vybere několik dobrých chromozomů (s vysokou kvalitou) k vytvoření nových potomků. Potom jsou odstraněny některé špatné chromozomy (s nízkou kvalitou) a noví potomci jsou umístěni na jejich místa. Zbytek populace přežije do nové generace.

Elitismus

Myšlenka elitismu byla uvedena už dříve. Při vytváření nové populace křížením a mutací existuje značná pravděpodobnost, že ztratíme nejlepší chromozom.

Elitismus je metoda, při níž se nejprve zkopíruje nejlepší chromozom (nebo několik nejlepších chromozomů) do nové populace. Zbytek se potom vytváří obvyklým způsobem. Elitismus může výrazně zlepšit výkon GA, protože zabraňuje ztrátě nejlepšího nalezeného řešení.