Evoluční výpočetní techniky
Selekce přímo úměrná fitness (Fitness Proportionate Selection)

| Úvod a cíle |

Selekční mechanismus imituje proces přirozeného výběru, kde má silnější jedinec větší šanci být vybrán. Potom lze očekávat, že potomstvo kvalitních jedinců se bude vyznačovat ještě lepšími vlastnostmi a tedy i vyšším ohodnocením. [9]

Takové chování lze pojmenovat jako selekční tlak - zvýraznění nadprůměrných jedinců a potlačení podprůměrných jedinců.

Pokud bychom použili základní algoritmus, který by využíval selekci pomocí ruletového kola - pravděpodobnost výběru je přímo úměrná ohodnocení jedince (čím lepší fitness, tím větší pravděpodobnost výběru jedince do další populace) a potlačily bychom změnové operace (křížení, mutace), zjistili bychom při pohledu na statistické parametry populace (průměrná hodnota, rozptyl kvality jedinců v posloupnosti populací) po proběhnutí několika populací, že: [8]

1. Vlivem náhodné komponenty v selekci statistické hodnoty při vývoji kolísají.
2. Rozptyl populací postupně klesá - populace se homogenizují a po čase jsou tvořeny kopiemi téhož jedince.
3. Konvergence parametrů populací není rovnoměrná v tom smyslu, že např. očekávaný nárůst střední hodnoty (vylepšování průměrné kvality populace) může být dočasně narušen.

Na straně druhé tedy selekční kritérium musí být zvoleno i tak, aby v populaci vybraných jedinců byla zachována dostatečná rozmanitost. Jestliže toto kritérium bude favorizovat jen nejsilnější jedince, může se snadno stát, že jedinci s relativně vyšším ohodnocením velice rychle převládnou v celé populaci. Dramaticky se tím sníží rozmanitost v populaci, možnosti pro další evoluci budou silně omezené a populace může předčasně konvergovat k suboptimálnímu řešení. Je-li naopak řešení příliš volné, evoluční proces bude postupovat jen velmi pomalu a algoritmus bude často pracovat po mnoho generačních cyklů, aniž by bylo možné zaznamenávat jakýkoliv pokrok. [9]

U standardních genetických algoritmů (SGA) je úkolem selekce upřednostňovat kvalitnější jedince před horšími. Základním selekčním principem je náhodný výběr takový, že pravděpodobnost přežití každého jedince je úměrná jeho kvalitě. To je také důvod, proč je zaveden předpoklad nezápornosti účelové funkce: [8]

kde:

• … Pravděpodobnost výběru -tého jedince do dalšího kola algoritmu.

• … Funkce, která poskytuje jako výstup hodnotu fitness jedince.

• c … Koeficient - určován tak, aby součet pravděpodobností přes celou populaci byl roven jedné.

Existují mnohé varianty přístupů, které využívají pravděpodobnostní rozdělení, např. zbytkový stochastický výběr (Stochastic Remainder Sampling), universální stochastická selekce (Stochastic Universal Selection) atd. Nejznámější metodou je metoda Monte Carlo - ruletový mechanizmus, ruletové kolo (Roulette Wheel Selection). [6]

Selekce založená na ruletovém mechanismu je popsána v dalším studijním článku.