3.0 Genetické algoritmy

Články na webu » Seminární práce » 3.0 Genetické algoritmy

GENETICKÉ ALGORITMY

ÚVODEM

Genetický algoritmus je díky svému věku (vznikl na začátku šedesátých let) poměrně netradiční, moderní a v určitém ohledu „revoluční“ typ algoritmu, který se úspěšně používá k řešení optimalizačních problémů. Vychází ze známé Darwinovy teorie o vývoji druhu.
Od počátku procházel poměrně rychlým vývojem a celou řadou optimalizací a v praktických aplikacích byla potvrzena smysluplnost použití tohoto typu algoritmu.

V problémech, které se popisuje tento text (především kinetická analýza) je i přes jeho – dle mého názoru – vhodné vlastnosti prakticky nevyužíván.

POPIS ALGORITMU

Jak už bylo zmíněno výše, genetický algoritmus funguje na bázi předávání genetické informace mezi jednotlivými generacemi, kdy dle Darwina mají vyšší pravděpodobnost na předání informace silnější (lepší) jedinci. Ač se to možná nezdá, právě tento postup se dá velmi výhodně použít pro optimalizační problémy, kdy dochází k hledání nejlepšího možného řešení (samozřejmě s určitou přesností).

Na počátku řešení problému je vybrána náhodná populace jedinců z oblasti hledání řešení, která může být prakticky neomezeně rozsáhlá. Každý jedinec bude mít své základní informace uložené ve své genetické informaci určené jednoduchým binárním řetězcem o předem dané délce (počtu znaků). Cíl algoritmu je tedy měnit tuto genetickou informaci tak, aby byl průměrný jedinec v další generaci lepší než ten v té předchozí.

K určení, zda je jedinec kvalitní, je použita funkce, která díky předem daným parametrům určí kvalitu jedince. Například při hledání maxima funkce může být kvalita určena absolutní hodnotou prohledávané funkce – tedy čím vyšší hodnota, tím kvalitnější řetězec. Nyní máme tedy základní populaci a máme i funkci, která bude určovat kvalitu jednotlivých jedinců v populaci.

Vývoj populace (tvorba druhé a další generace) probíhá za pomoci reprodukce, mutace a křížení jedinců předchozí generace. Při reprodukci je vytvořen základ další generace – dochází ke kopírování starých řetězců do nové generace, a to tak, že s vyšší kvalitou řetězce stoupá jeho šance na to být v další generaci. Nejsnazší cestou jak toho dosáhnout je vážená ruleta, kdy je pravděpodobnost, že padne vybraný jedinec odpovídající jeho kvalitě. Tento výběr je možné doplnit nějakou formou zvýhodnění silných jedinců. Reprodukce nám umožní do další generace přenést jen silné jedince, přesněji řečeno v následující generaci bude větší množství lepších jedinců. To ale samo o sobě nestačí.

Pro prohledání celého definičního oboru je třeba získat i zcela nebo částečně nové jedince. Jednou z možností je křížení současných jedinců, tedy výměna informací mezi řetězci. Z nově vylosované populace se náhodně vyberou dva řetězce a jejich kód se změní tak, že si mezi sebou přepíšou část jejich genetické informace. Jejich „potomci“ budou tedy zcela noví jedinci. Tento krok mnohdy přinese do populace zcela nekvalitní jedince, kteří však nemají šanci v dalším kole rulety. Občas ale přinese jedince s vysokou kvalitou, která se v populaci ještě nevyskytovala. Závěrem je třeba říci, že křížení neprobíhá u všech jedinců, pouze u určitého procenta. V nové generaci tak máme určité procento silných jedinců původní generace a zbytek jsou noví jedinci vzniklý křížením silných jedinců.

Posledním krokem je mutace, která prakticky nezasáhne větší část vznikající generace, nicméně hraje velmi důležitou roli. Stejně jako u křížení dochází k mutaci jen s určitou, avšak výrazně nižší, pravděpodobností. Zároveň je mutací ovlivněna podstatně menší část genetické informace (v našem případě mnohdy jen jeden bit – tedy jedna jednička nebo nula). Ač se může zdát, že tato změna je prakticky bezvýznamná, je esenciální pro nalezení velmi kvalitních jedinců, u kterých je poté vysoká pravděpodobnost, že se dostanou do další generace a o několik generací dál značně zlepší průměrnou kvalitu celé generace.

ZÁVĚREM

V předchozí kapitole byl popsán jeden přepis mezi generacemi. Pro získání kvalitní populace to samozřejmě nestačí, je třeba nechat proběhnout vývoj po několik stovek (tisíc) generací. Z pohledu výpočetního času je tato činnost podstatně méně náročná na výkon než jiné způsoby hledání řešení. Spolehlivě umožní minimálně určení oblasti, ve které se nachází hledané řešení a s velkou pravděpodobností bude v populaci na konci vývoje i jedinec (statisticky významná skupina jedinců), který s danou přesností odpovídá hledanému řešení.

K oblasti genetických algoritmů se v této práci vrátíme ještě při kinetické analýze, kdy se pokusím navrhnout a otestovat jednoduchý algoritmus pro kinetickou analýzu termoanalytických dat využívající genetickou analýzu. Tato testovací aplikace bude především zdrojem informací a zkušeností pro následnou kinetickou analýzu dějů skládajících se z dvou (a více) podprocesů, při kterých jsou běžné metody kinetické analýzy obtížně použitelné nebo vyžadují velké množství výpočetního času.