next up previous contents
Next: Algoritmus 5.1.1: Up: Genetické algoritmy Previous: Genetické algoritmy   Obsah


Genetický algoritmus

Za počátek historie genetických algoritmů jsou považována 70. léta tohoto století a práce Johna Hollanda. Genetický algoritmus je stochastická prohledávací metoda inspirovaná evolučními principy jako jsou přirozený výběr, křížení a mutace.

Jedná se o alternativní metodou k řešení problémů optimalizace. Tedy takových problémů, které lze převést na hledání maxima funkce v závislosti na jejích parametrech. V terminologii genetických algoritmů tuto funkci nazýváme účelovou funkcí.

Genetický algoritmus pak hledá v prostoru všech přípustných parametrů takové hodnoty parametrů, pro něž je hodnota účelové funkce maximální. Každé přípustné nastavení parametrů považujeme za potencionální řešení problému. Algoritmus pracuje vždy z množinou potencionálních řešení. Každé řešení je zakódováno do konečného řetězce znaků (bitů, čísel), který je označován jako jedinec. Množinu jedinců pak nazýváme populace.

Výpočet probíhá iterativně a je popsán algoritmem 5.1.1. V každé iteraci sestrojíme novou populaci, tzv. novou generaci, pomocí genetických operátorů - selekce, křížení a mutace.

Selekce slouží k výběru jedince do nové populace v závislosti na hodnotě účelové funkce. Modeluje darwinistický přirozený výběr tak, že vybírá jedince náhodně s pravděpodobností přímo úměrnou odpovídající hodnotě účelové funkce.

Operátor křížení vytváří dva nové jedince kombinací dvou vybraných jedinců. Nejpoužívanějším typem křížení je tzv. jednobodové křížení, které se realizuje tak, že řetězce představující jedince se na náhodném místě rozdělí a jejich části se vymění.

Operátor mutace vnáší do populace náhodné změny. Realizuje se obvykle tak, že náhodně zvolíme pozici ve vybraném jedinci a danou jednotku (bit, znak,číslo) náhodně změníme.

Výpočet probíhá tak dlouho, dokud se v populaci neobjeví jedinec s dostatečně velkou hodnotou účelové funkce.



Subsections
next up previous contents
Next: Algoritmus 5.1.1: Up: Genetické algoritmy Previous: Genetické algoritmy   Obsah
Petra Kudova
2001-04-19