Student World

Možná jste již někdy slyšeli výraz genetické programovaní, ale co se vlastně za tímto názvem skrývá — jde opravdu o geny zapřažené vedle elektronů a nebo nás zase počítačoví vědci mystifikují? Vlastně obojí je pravda, samozřejmě o žádnou kyselinu, kterou byste museli nalévat do počítače nejde, ale přesto mají genetické algoritmy s vývojem života velice mnoho společného.
Oblast genetických algoritmů (GA) je zařazována do evolučních výpočetních technik, kde mimo genetické algoritmy tvoří velkou část neuronové sítě. Všechny tyto techniky a jim podobné patří do oboru umělé inteligence.
Jak již název napovídá, genetické algoritmy jsou inspirovány myšlenkami převzatými z biologie a souvisejících věd. Genetický algoritmus může být použit k řešení problému tak, že použije vyjádření problému ve formě chromozomu a snaží se "vypěstovat" optimální řešení za pomoci vyvíjející se populace. Existují problémy, které se dají řešit pomocí genetických algoritmů velmi dobře. Stejně tak je ovšem plno jiných problémů, které je vhodnější řešit jinými způsoby. Genetický algoritmus může však dát řešení i v případech, kde ostatní metody selhaly. Asi nejčastější oblastí aplikací GA je optimalizace a strojové učení. GA byly použity pro řešení problémů z technických oborů, chemie, ekonomie a dalších. Je namístě říci, že GA nejsou zamýšleny jako pomůcka pro simulaci přírody, přestože byly použity pro modelování přírodních pochodů (např. pro studie otázek z genetiky nebo pro modelování ekosystému).

Problémy pro genetický algoritmus
Co to tedy genetický algoritmus je? Před tím, než ho podrobněji popíši, musím se zmínit o problémech, které mohou být pomocí GA řešeny. Problém můžeme specifikovat takto: vyber z nějakých přípustných řešení to nejlepší. Takto to zní velmi jednoduše, ovšem pokud si uvědomíme, že u praktických problémů může být počet přípustných řešení velmi velký, stává se situace složitější. Tento počet bývá tak velký, že ani při použití toho nejrychlejšího počítače nestihneme všechna přípustná řešení vygenerovat během našeho života, natož z nich vybrat to nejlepší.
Ilustrujme si vše na příkladě známého problému obchodního cestujícího: obchodní cestující má navštívit několik měst, ale nechce se mu strávit na cestách moc času. Přesněji tedy musí navštívit všechna města, vrátit se domů (tj. do města, ze kterého vyjel) a přitom urazit co nejkratší vzdálenost. Problém je zde tedy nalezení takové posloupnosti měst, kde cesta mezi nimi bude nejkratší možná. Pokud máme nějakou posloupnost, můžeme velmi rychle určit celkovou délku trasy (umět určit rychle tzv. cenu řešení je velmi důležité, jak uvidíme níže). Zaručeně nejlepší řešení umíme nalézt pouze tak, že probereme všechny možnosti (posloupnosti) a z nich vybereme tu nejlepší. Ohodnocení řešení (vzdálenost) umíme spočítat rychle. Problém je pouze v počtu řešení. Počet všech permutací n měst je n!=1*2*3*.*n. Pro 5 měst dostáváme 120 možností, což je počítačem snadno zvládnutelné. Již pro 20 měst však dostáváme 2432902008176640000, což by počítač ohodnocující miliardu permutací za vteřinu počítal přes 77 let. I jen malým zvýšením tohoto počtu se dostáváme za hranice času předpokládané existence vesmíru.
Musíme se tedy spokojit s tím, že optimální řešení nenalezneme. Člověk však je schopen nalézt dobré řešení v mnohem kratším čase. Není sice zaručené, že je to řešení optimální, ale pro praktické účely může být dostačující. A proč by něco takového nemohl umět i počítač? Ukážeme si, že nalézt poměrně rychle dobré (ale suboptimální) řešení pomocí počítače je možné např. pomocí genetických algoritmů.
Pro použití genetických algoritmů (ale i jiných optimalizačních metod) musíme v první řadě být schopni vygenerovat nějaká přípustná řešení daného problému, tj. řešení, která neporušují dané omezující podmínky. Na kvalitu těchto řešení nejsou kladeny žádné požadavky. Dále musíme být schopni umět ke každému řešení určit jeho ohodnocení, podle kterého můžeme všechna řešení uspořádat a tak nalézt to nejlepší. Optimalizace pak probíhá tak, že nějak prohledáváme prostor všech řešení s tím, že chceme najít to nejlepší. Jednotlivé optimalizační metody se liší v podstatě pouze tím, jak chytře tento prostor řešení prohledávají.

Trocha biologie
Genetický algoritmus používá pro reprezentaci řešení speciální tvar inspirovaný biologickými chromozomy a pro generování nových řešení křížení a mutaci. Před detailním popisem genetického algoritmu proto připomenu několik známých poznatků ze souvisejících oblastí. V každé buňce živého organismu je sada chromozomů skládajících se z DNA. Chromozomy tvoří model celého organismu a skládají se z genů (bloků DNA). Velmi zjednodušeně se dá říci, že každý gen reprezentuje nějakou vlastnost nebo rys, např. barvu očí. Možné stavy genu se nazývají alely, tj. například barva očí může být modrá, hnědá atd. Každý gen má svou pevnou pozici v chromozomu. Celý genetický materiál organismu se nazývá genom. Konkrétní "nastavení" genů v genomu se nazývá genotyp. Genotyp určuje tzv. fenotyp, což je vnější charakteristika organismu (fyzická i mentální — barva očí i inteligence).
Během reprodukce organismů dochází ke křížení (rekombinaci), při kterém se vybírají geny převzaté od rodičů a jejich kombinací se vytvoří genotyp potomka. Při nebo po reprodukci může dojít k mutaci — náhodné změně nepatrné části genotypu. Úspěšnost organismu (fitness — jeho ohodnocení) se v biologii udává jako pravděpodobnost, že organismus přežije do své reprodukce, nebo jako počet jeho potomků. Evoluční teorie pak říká, že pouze některé organismy přežijí a budou se reprodukovat, přičemž s větší pravděpodobností se to podaří těm lepším.

Genetický algoritmus
Vše výše uvedené používá genetický algoritmus. Přípustné řešení problému, který GA řeší, je reprezentováno pomocí genomu, tj. nějakého souboru genů. Konkrétní stav souboru genů je genotyp a reprezentuje tak fenotyp, což je konkrétní řešení. Na základě fenotypu se tedy určí ohodnocení řešení a tak vlastně i ohodnocení genotypu. Křížení a mutace však probíhá pouze na úrovni genotypu. Genetický algoritmus si udržuje populaci řešení ve formě genotypů (chromozomů), které kříží a mutuje s tím, že preferuje genotypy s vyšším ohodnocením, a tak se snaží "vypěstovat" dobré řešení. Na začátku svého běhu vytvoří náhodnou populaci (první generaci) a uvedeným způsobem vytváří nové potomky (další generace) dokud není splněna nějaká ukončující podmínka (např. počet generací, čas, nelepšící se nejlepší fitness apod.).

Genetický algoritmus lze tedy popsat zhruba takto:

1.[Start] Vygeneruj náhodnou populaci chromozomů
2.[Výpočet fitness] Ohodnoť každý chromozom x, tj. vyhodnoť fitness funkci f(x)
3.[Test konce] Jestliže je splněna ukončovací podmínka, ukonči běh algoritmu a vrať nejlepší nalezené řešení
4.[Nová populace] Vytvoř novou populaci opakováním následujících kroků
1.[Selekce] Vyber náhodně 2 rodiče z populace dle jejich ohodnocení (čím vyšší f(x), tím vyšší šance k výběru)
2.[Křížení] S danou pravděpodobností křížení proveď křížení pro vytvoření potomka (potomků) — pokud nedojde ke křížení, potomek je přesnou kopií rodiče
3.[Mutace] S danou pravděpodobností mutace proveď mutaci každého genu potomka
4.[Vložení] Vlož vytvořeného potomka (potomky) do nové populace
5.[Nahrazení] Nahraď starou populaci novou populací (nová generace)
6.[Opakování] Opakuj od bodu 2

Hlavní síla genetického algoritmu je v jeho paralelismu, tzn. že prohledává více bodů prostoru řešení najednou (celou populací). Z toho vyplývá hlavně jeho odolnost proti uváznutí v nějakém lokálním extrému (představme si, že hledáme nejvyšší bod v horách — pokud se budeme dívat pouze na jedno místo blízko kolem sebe, stejně jako velká část jiných optimalizačních metod, a pouze podle toho se budeme rozhodovat o další cestě, může se nám stát, že najdeme pouze lokální vrchol (extrém) a z něj se již tímto postupem nehneme). Genetický algoritmus je tak schopen pracovat bez zvláštních požadavků na prohledávaný prostor (např. jeho spojitost) a umí na rozdíl od jiných metod nalézt dobré řešení i když je prohledávaný prostor velmi "divoký". Další významnou odlišností od ostatních optimalizačních metod je oddělení genotypu a tvorby nových řešení (postupu v prostoru řešení) od fenotypu a ohodnocení vhodnosti řešení.

Příklad — maximum funkce
Ukažme si práci genetického algoritmu a reprezentaci chromozomů na klasickém příkladu hledání maxima funkce. Tento problém je sice v základní podobě spíše akademický, ale slouží jako základ pro úpravu na praktické úlohy. Je však velmi jednoduchý a ilustrativní. Mějme nějakou funkci. Máme najít její maximum na intervalu 0..255. Znamená to tedy hledat v daném intervalu takové x, kde bude f(x) nejvyšší — funkce f(x) tedy vyjadřuje fitness funkci. Fenotyp zde bude vyjadřovat konkrétní hodnotu x. Genotyp bude vyjádřen chromozomem, který má 8 genů nabývajících hodnot 0 nebo 1 — bude se jednat o binární vyjádření čísla x.

Křížení bude probíhat výběrem genů z rodičů a jejich kopií do chromozomu potomka. Výběr může probíhat tímto způsobem: Zvolíme náhodně nějaký bod mezi geny v chromozomu. Všechny geny potomka až do tohoto bodu budou převzaty z prvního rodiče, zbytek genů bude převzatý z druhého rodiče. Tento způsob, ilustrovaný v tabulce 2, se nazývá jednobodové křížení. Jak již bylo uvedeno, křížení probíhá při vytváření nové generace s určitou pravděpodobností, tzn. je předem daná pravděpodobnost křížení, která určuje, kolik potomků bude vytvořeno křížením (ostatní potomci budou přesnými kopiemi rodičů). Mutace probíhá tak, že každý gen (bit) je s danou pravděpodobností mutace zinvertován.
Tato pravidla křížení a mutace a dané pravděpodobnosti křížení a mutace určují do jisté míry úspěšnost genetického algoritmu. Závisí ovšem také na konkrétním řešeném problému. Uvedené možnosti křížení a mutace nejsou samozřejmě jediné. Navíc i reprezentace řešení, tedy tvar chromozomu, může vypadat různě, např. lze použít řetězec reálných čísel nebo znaků. Velmi zajímavá reprezentace je použita u tzv. genetického programování, kde chromozom představuje program a genetickým algoritmem lze vypěstovat program řešící zadaný problém. Binární reprezentace je však nejznámější, nejjednodušší a také nejprobádanější. Zatím pouze pro tuto reprezentaci existuje rozšířenější matematická teorie, která se snaží vysvětlit chování genetického algoritmu — tzv. teorie schémat. Tato teorie vysvětluje, že genetický algoritmus se snaží hledat řešení pomocí schémat, jakýchsi stavebních bloků.

Výběr rodičů
Nyní již umíme vytvořit potomky, zbývá nám pouze vybírat rodiče. Jak již bylo řečeno, rodiče se vybírají dle jejich ohodnocení, podle hodnoty fitness funkce. Je totiž pravděpodobné, že lepší rodiče (s vyšším ohodnocením) budou mít lepší potomky. Nelze však omezit výběr pouze na ty nejlepší. Pokud by se tak stalo, mohla by celá populace uváznout v lokálním extrému bez možnosti dalšího zlepšování. Jinými slovy — zdegenerovala by. Hodnota fitness funkce tedy udává pouze výši pravděpodobnosti vybrání chromozomu. Používaný způsob výběru se dá přirovnat k ruletě. Představme si, že máme ruletové kolo rozdělené na různě velké části, přičemž každá část odpovídá jednomu chromozomu v populaci. Velikost každé části odpovídá velikosti ohodnocení tohoto chromozomu. Roztočíme ruletu a vhodíme kuličku. Po zastavení rulety vidíme, ve které části se kulička zastavila, a dle toho určíme, jaký chromozom máme vybrat. Tímto způsobem preferujeme lepší chromozómy, ale nevylučujeme ani ty nejhorší. Uvedený způsob lze různě modifikovat, např. lze vhodně upravit velikosti částí ruletového kola.
K jakémukoliv způsobu selekce by měla být doplněna strategie, která zajistí přežití alespoň jednoho nejlepšího jedince do další generace, abychom neztratili nejlepší dosud nalezené řešení (pokud toto řešení neuchováváme jinak). Tato strategie se nazývá elitismus a spočívá jednoduše v tom, že se nejlepší jedinec (nebo několik málo nejlepších jedinců) přesně zkopíruje do nové populace.

Aplikace a shrnutí
Genetické algoritmy byly úspěšně použity v několika praktických aplikacích. Asi nejpoužívanější jsou pro optimalizační úlohy (např. plánování, navrhování obvodů VLSI), a pro strojové učení (klasifikace, predikce, učení neuronových sítí). Byly použity pro "automatické programování" (např. vývoj buněčných automatů, genetické programování). Mimo technické obory jsou genetické algoritmy používány např. v chemii (určování struktury složitých molekul), v ekonomii (predikce, hledání parametrů ekonomických modelů), v biologii a medicíně (modelování imunitního systému, modelování ekologického systému) a v sociologii (modelování sociálního systému).
Uvedený popis genetických algoritmů není ani zdaleka vyčerpávající. Více informací lze nalézt např. na Internetu. Existuje i několik stránek s Java applety, kde si lze pohrát s genetickým algoritmem řešícím nějakou jednoduchou úlohu, například http://cs.felk.cvut.cz/~xobitko/ga/index.html — na této stránce lze nalézt spolu s dalšími informacemi i odkazy na další stránky.

autor Marek Obitko