Evoluční výpočetní techniky
Populace v evolučních algoritmech

| Úvod a cíle |

Jedním z klíčových faktorů, které od sebe odlišují různé EVT je proces výběru nové populace ze staré.

Na dalším obrázku je patrný princip náhrady generace - populace u EVT (viz ).

Mezigenerace označuje množinu tvořenou jak jedinci, kteří byli předmětem změnových operací, tak i jedinci vytvořenými změnami.

Náhrada generací představuje postup (vývojovou strategii), jak z této smíšené množiny „rodičů“ a „potomků“ vybrat množinu, kterou budeme považovat v dalším vývoji za novou populaci. V této náhradě je zpravidla zajištěn konstantní rozsah populací. V EVT se zpravidla hovoří o těchto typech vývojových strategií:

1. Generační (General Evolution) - jde o úplnou náhradu jedné populace populací následující představující analogii životního cyklu jednoletých rostlin. [8] Strategii lze také vyjádřit jako tzv. ne-elitářskou (Non-Elitist), tzn., nepreferuje určité jedince - popsáno v následujícím algoritmu (viz ).
2. Postupná (Steady State Evolution) - změny podstupuje jen malá část populace a rodiče koexistují se svými potomky (model vývoje déle žijících živočich či víceletých rostlin). [8] Tato strategie podporuje zachování lepších jedinců i v následujících populacích tzv. elitářství (Elitist) - zachovávají se archivy jedinců s dobrou hodnotou fitness popsanou v následujícím algoritmu (viz ).
3. Ustálená populace - po každém křížení potomek (potomci) nahradí nejslabšího (dva nejslabší jedince). [21]
4. Přechodové formy - přechodové formy mezi generační a ustálenou populací. [21]

U strategie elitářství (Elitism), která zajišťuje, že alespoň jedna kopie nejlepšího jedince s dobrou hodnotou fitness (tato hodnota je většinou závislá na hodnotě účelové funkce, ale to samozřejmě závisí na použité strategii přidělování hodnoty fitness jedinci) současné generace přejde do nové generace. Použití takového přístupu je zejména vhodné, pokud losujeme v populaci jedinců, které mají téměř shodné hodnoty fitness. Znamená to, že pravděpodobnost vylosování nejlepšího jedince do nové generace bude rovna , kde m bude velikost populace. Je patrné, že čím větší bude velikost populace, tím menší je pravděpodobnost vylosování nejlepšího jedince ze skupiny. Zabráníme tím ztrátě nejlepšího jedince ze skupiny.

Evoluční algoritmy využívají různých variací předchozích uvedených vývojových strategií.

Popišme si nyní zjednodušeně jednotlivé bloky zachycené v algoritmech (viz , ):

CreatePop - tvorba počáteční náhodné populace.

TerminationCriterion - formulace zastavovacího pravidla (kritéria ukončení) pro ukončení celého cyklu (algoritmu).

UpdateOptimalSet - kontrola, zda nový jedinec bude zařazen do množiny optim. Pokud se tak stane, může to vést k tomu, že jiný jedinec z množiny optim bude muset být vyřazen.

PruneOptimalSet - pokud je množina optim příliš velká (teoreticky může obsahovat nekonečně mnoho prvků), musí dojít k jejímu ořezání na specifikovanou velikost. Existují různé techniky ořezávání, např. seskupovací algoritmy. Účelem takových technik by mělo být také zachování různorodosti jedinců.

AssignFitness - většina z evolučních algoritmů přiřazuje hodnotu fitness (skalár) každému jedinci podle hodnoty účelové funkce vzhledem k dalším jedincům v populaci nebo množině optim. Tento přiřazovací proces je prostředkem k zachování různorodosti.

Select - selekční algoritmus pomáhá vybírat takové jedince z populace (množiny optim), kteří se budou reprodukovat. Jedná se zde zejména o exploataci (zužitkování) - snahu zlepšovat dosavadní známé řešení pomocí malých změn, které vedou k novým podobným zlepšeným jedincům. Touto cestou lze také dosáhnout lepší výkonnosti.

ReproducePop - nová populace je generována z jedinců uvnitř populace určené k páření za pomoci mutace a/nebo rekombinace.

Dalším logicky navazujícím tématem týkající se populací v evolučních algoritmech je reprodukce, která je obecně popsána v dalším studijním článku.