Biologické algoritmy (1) - Evoluční algoritmy

Vitalij Chalupník 4. 4. 2012

Biologicky inspirované algoritmy vyznačující se vysokou robustností, jsou obecně schopny řešit celou řadu problémů. Nejvíce se tyto algoritmy uplatňují v oblasti optimalizace, klasifikace a rozhodování. V prvním dílu seriálu se naučíme princip evolučních algoritmů, v dalším dílu je zkusíme naprogramovat v Javě.

Evoluční algoritmy patří mezi globálně optimalizační algoritmy. Cílem je prohledat prostor a najít optimální řešení – tedy takové řešení, které maximalizuje nebo minimalizuje známou funkci. Je-li prostor možných řešení omezený a malý, lze jednotlivá řešení vyhodnotit hrubou silou a vybrat z nich to nejlepší.

Ovšem ve většině případů velikost prostoru možných řešení roste velmi rychle s velikostí problému. U takových problémů prohledávat celý prostor řešení je nemožné a tudíž je i nemožné najít optimální řešení v krátkém čase. Evoluční algoritmy tento problém řeší.

Kdy jsou evoluční algoritmy vhodné?

Tímto způsobem je vhodné řešit obecně obtížné problémy, u kterých je velký prostor řešení. Dále je tímto způsobem možné řešit obtížně formulovatelné problémy. Např. víme, jak by měl vypadat výstup, ale nevíme, jakým způsobem takový výstup dostat. Příkladem může být např. návrh elektronických schémat. Víme, jaký požadujeme od schématu výstup, ale nevíme, jak zapojit součástky, abychom tento výstup dostali.

Možností, jaké součástky a jak je ve schématu zapojit, je neomezeně mnoho. Evoluční algoritmy dokážou prohledat různé možnosti a najít nejvhodnější zapojení. Tímto způsobem se např. podařilo nalézt patentovaná schémata a v mnoha případech dokonce i schémata s lepšími vlastnostmi než patentované. Evoluční algoritmy jsou schopné také najít více optimálních řešení, jsou schopny najít celočíselná řešení i reálná.

Nevýhody evolučních algoritmů

U obtížných problémů jsou tyto algoritmy schopny najít pouze přibližná řešení. I když složitost roste pouze lineárně s velikosti populace a počtem generací, výpočet nemusí být rychlý vzhledem k tomu, že vyhodnotit řešení bývá časově náročné.

Základní principy

Každé možné řešení je reprezentováno jedincem v populaci. Populace je tedy množina jedinců – množina různých řešení. Postupem času se populace vyvíjí. Špatní jedinci vymírají, objevují se lepší jedinci, kteří je nahrazují. Počkáme-li dostatečně dlouho, populace bude tvořena dobrými jedinci, kteří reprezentují správná řešení problému.

Aby byla evoluce funkční, jsou nezbytné tři věci. Za prvé je nezbytné umět ze dvou existujících řešení vytvořit nové „zprůměrované“, této operaci se říká křížení. Za druhé je nezbytné umět vytvořené řešení náhodně pozměnit, této operaci se říká mutace. A za třetí je nezbytné pro vybraného jedince vybrat vhodného jedince ke křížení, této operaci se říká selekce nebo přirozený výběr.

Nyní se podívejme na graf níže. Na vodorovné ose je rozdílnost jedinců (jejich genetický kód). Rozdílní jedinci jsou od sebe dále. Na svislé ose je jejich kvalita. Každý jedinec tak má jednoznačně přiřazenou svoji kvalitu. V grafu je také vyznačeno nejlepší možné řešení, jedná se o globální maximum celého prostoru. Jedinec R1 si vybere jedince R2, se kterým se chce zkřížit. Jejich zkřížením by měl vzniknout „zprůměrovaný“ jedinec mezi nimi C. Ten však nahodile zmutuje (posune se některým směrem) a vznikne tak v populaci nový potomek D se svojí kvalitou. Míra mutace je základním parametrem evolučních algoritmů, což si dále ukážeme.

V následující generaci se proces opakuje. Dejme tomu, že jedinec D se chce zkřížit s jedincem R2. Zkřížením by vznikl jedinec E, náhodnou mutací se však toto řešení posune a vznikne nový jedinec v populaci F se svojí kvalitou. Zapojíme-li do tohoto procesu selekci, aby si jedinci vybírali ke křížení kvalitnější partnery, bude celá populace konvergovat k optimálnímu řešení. Špatní jedinci budou mít nižší pravděpodobnost, že si najdou partnera ke křížení a předají své geny.

V přírodě se za kvalitu považuje schopnost přežít. Jedinci si vybírají ke křížení takové partnery, kteří mají vyšší šanci přežít. Vlivem změny životního prostředí se uvedená křivka znázorňující kvalitu deformuje. Náhlá změna životního prostředí tak může vést k tomu, že kvalitní populace se v novém prostředí stane nekvalitní a vyhyne, anebo se populace, která již dosáhla maxima a dlouhou dobu se příliš nevyvíjela, náhle přesune k novému optimálnímu maximu. Nové druhy proto vznikají často při náhlých změnách životního prostředí. Kvalitu jedinců obvykle označujeme pojmem fitness.

Rychlost konvergence a parametry evoluce

Cílem je v rychlém čase dosáhnout optimálního řešení. Přitom však může docházet ke dvěma nežádoucím jevům. Za prvé populace může uvíznout v lokálním maximu – nikoliv globálním. Tato situace je znázorněna na obrázku níže. Všichni jedinci v populaci jsou si geneticky velmi blízcí a pokrývají pouze rozsah odpovídající lokálnímu maximu. Dostat se z této pasti a nalézt globální maximum bude velmi obtížné, protože vlivem křížení mohou vznikat pouze „zprůměrovaní“ jedinci mezi svými rodiči.

Jedinou cestou jak se dostat z této pasti je vysoká mutace, která populaci rozšíří, přidá nové geny a posune nové potomky mimo tuto past. K tomuto nežádoucímu jevu dochází, nastavíme-li míru mutace příliš nízkou. V přírodě se tento problém řeší tak, že při křížení geneticky blízkých jedinců je zvýšena pravděpodobnost mutace. Jsou-li rodiče vzájemně příbuzní, míra mutace potomků je vyšší. Je nezbytné zajistit v populaci heterogenitu, protože vývoje lze dosáhnout pouze v heterogenní populaci!

Druhým problémem je nahodilé nebo uniformní rozmístění populace. Najít optimální řešení bude opět velmi obtížné, je totiž málo pravděpodobné, že vznikne dobrý jedinec. Tato situace je znázorněna na obrázku níže. K tomuto jevu dochází, pokud je mutace příliš vysoká.

Optimální situace je znázorněna na dalším obrázku. Hustota populace směrem k maximu roste, vzdálenějších jedinců je méně. Pravděpodobnost, že nastane v genu mutace obvykle volíme mezi 2 – 4 %.

Nyní se podívejme na jiný graf, který znázorňuje typický vývoj populace v čase. Na vodorovné ose je čas, na svislé ose je kvalita jedinců. Každý bod v grafu znázorňuje jedince. Populaci v konkrétním čase získáme svislým řezem v grafu. Na začátku jsou v populaci nekvalitní jedinci. Postupem času se populace vyvíjí. V okamžiku, když se objeví nový kvalitnější jedinec, zbytek populace k němu zkonverguje. Populace se často vyvíjí skokově. Pokud po delší dobu nedochází ke zlepšení populace, signalizuje to, že populace uvízla v lokálním extrému.

Reprezentace řešení

Volba jak řešení reprezentovat často závisí na samotném problému. Pro některé problémy je vhodné řešení reprezentovat jako binární řetězec, u jiných problémů jako pole reálných hodnot, jako textové řetězce či celé grafy. Této reprezentaci jedinců se říká genotyp.

V příštím díle

V příštím díle si vyzkoušíme naprogramovat evoluční algoritmus v Javě a zkusíme pomocí něj vyřešit jednoduchý problém.

Našli jste v článku chybu?
Měšec.cz: Kurzy platebních karet: vyplatí se platit? (TEST)

Kurzy platebních karet: vyplatí se platit? (TEST)

DigiZone.cz: Skylink o půlnoci vypnul 12 525

Skylink o půlnoci vypnul 12 525

DigiZone.cz: Discovery Channel HD jen tak nebude

Discovery Channel HD jen tak nebude

Vitalia.cz: Pepsi Cola mění sirup za cukr

Pepsi Cola mění sirup za cukr

120na80.cz: Tipy pro odvodnění organismu

Tipy pro odvodnění organismu

Lupa.cz: Největší torrentový web KickassTorrents padl

Největší torrentový web KickassTorrents padl

Měšec.cz: Test: Výběry z bankomatů v cizině a kurzy

Test: Výběry z bankomatů v cizině a kurzy

Podnikatel.cz: Italské těstoviny nebyly k mání, tak je začal vyrábět

Italské těstoviny nebyly k mání, tak je začal vyrábět

Lupa.cz: Vodafone umí volání přes Wi-Fi. Z ciziny jako v ČR

Vodafone umí volání přes Wi-Fi. Z ciziny jako v ČR

Měšec.cz: Investice do drahých kovů - znáte základní chyby?

Investice do drahých kovů - znáte základní chyby?

Podnikatel.cz: Musí mít e-shopař sklad a provozovnu?

Musí mít e-shopař sklad a provozovnu?

Podnikatel.cz: Fotogalerie: Jesenka už má skoro 50 let

Fotogalerie: Jesenka už má skoro 50 let

Podnikatel.cz: 3 velké průšvihy obchodních řetězců

3 velké průšvihy obchodních řetězců

Podnikatel.cz: Přiznal prodej padělků. Pokuta ho nemine

Přiznal prodej padělků. Pokuta ho nemine

Vitalia.cz: Sobotní masakr žrádla, chlastu a zábavy

Sobotní masakr žrádla, chlastu a zábavy

Měšec.cz: Co s reklamací, když e-shop krachuje?

Co s reklamací, když e-shop krachuje?

Lupa.cz: V Praze se otevřel první podnik s virtuální realitou

V Praze se otevřel první podnik s virtuální realitou

DigiZone.cz: Kauza technik: oficiální vyjádření Novy

Kauza technik: oficiální vyjádření Novy

Měšec.cz: Se stavebkem k soudu už (většinou) nemusíte

Se stavebkem k soudu už (většinou) nemusíte

Podnikatel.cz: Polská vejce na českém pultu Albertu

Polská vejce na českém pultu Albertu