PARALELNÍ GENETICKÉ ALGORITMY PETR POŠÍK
DIPLOMOVÁ PRÁCE České vysoké učení technické Praha, 2001
Abstrakt Genetické algoritmy (GA) se osvědčily při řešení různých optimalizačních problémů v mnoha oblastech lidské činnosti. Dnes se často používají paralelní modely a paralelní implementace genetických algoritmů, protože při správném nastavení úspěšně redukují dobu potřebnou k nalezení řešení přijatelné kvality. Přestože jsou GA operačně jednoduché, analýza jejich činnosti je naopak značně složitá. Bohužel ještě nerozumíme dobře tomu, jaký efekt má různé nastavení parametrů paralelních GA (PGA) na kvalitu a efektivitu prohledávání stavového prostoru. Díky tomu neumíme navrhnout paralelní GA s takovými parametry, který by dosahoval řešení požadované kvality v co možná nejkratším čase. Cílem této diplomové práce je rozšířit naši znalost vlivu nastavení PGA na jejich činnost se zvláštním zaměřením na parametry migrace. Výzkumy se soustřeďují na vícekmenový model PGA (multi-deme PGA), protože je v praxi nejvíce používaný. Je zde prezentován nový operátor migrace, který by měl být lépe přizpůsoben pro použití v rozsáhlých sítích (např. na Internetu). Účinnost PGA využívajících tento nový operátor je otestována na známých referenčních úlohách a porovnána s účinností jiných migračních operátorů, případně i s jednoduchým GA.
ii
Abstract Genetic algorithms (GAs) have proved their efficiency in solving various optimisation problems in many domains of human activities. Nowadays, parallel models and parallel implementations of GAs (PGAs) are often used, because, if properly set, they succeed in reduction of time needed to find desirable solution. Despite of their operational simplicity, their analysis is very difficult. Unfortunately, we still do not exactly understand all the effects of various PGA parameter settings to the quality and efficiency of searching the state space. That’s the reason we are not able to design PGA with such parameters that would guarantee finding the desired solution in the shortest time possible. The goal of this thesis is to extend our knowledge of influence of the PGA settings to their evolution with special emphasis on parameters of migration. The research considers multi-deme model of PGA because at present it is most frequently used model. In this paper, new migration operator is presented. This operator should be more suitable for use in wide-area networks (e.g. on Internet). Efficiency of PGA using this new operator is verified on known reference problems and compared to efficiency of conventionally used migration operator and with simple GA respectively.
iii
Obsah 1
Úvod............................................................................................................................................ 1 1.1 Struktura textu......................................................................................................2
2
Jednoduché genetické algoritmy.............................................................................................. 3 2.1 Vlastnosti GA ......................................................................................................4 2.2 Účelová funkce (Objective function)...................................................................5 2.3 Princip činnosti GA .............................................................................................5 2.3.1 Inicializace..............................................................................................5 2.3.2 Selekce....................................................................................................6 2.3.3 Rekombinace ..........................................................................................7 2.3.4 Křížení ....................................................................................................7 2.3.5 Mutace ....................................................................................................8 2.4 Parametry GA ......................................................................................................8 2.4.1 Velikost populace ...................................................................................8 2.4.2 Elitismus .................................................................................................9 2.4.3 Velikost překrytí.....................................................................................9 2.4.4 Nahrazovací strategie .............................................................................9 2.5 Druhy GA ..........................................................................................................10 2.6 Práce s omezeními .............................................................................................11 2.6.1 Pokutové funkce ...................................................................................11 2.6.2 Dekodéry a opravné algoritmy .............................................................11 2.6.3 Problémově závislá reprezentace .........................................................11 2.7 Stavební bloky, schéma-teorém .........................................................................12 2.8 Shrnutí 13
3
Paralelní genetické algoritmy ................................................................................................. 14 3.1 Paralelní model vs. paralelní implementace ......................................................15 3.2 Možnosti paralelizace ........................................................................................15 3.2.1 Paralelizace globálního modelu............................................................15 3.2.2 Vícekmenové PGA (Multi-deme PGA) ...............................................16 3.2.3 Hybridní (hierarchické) PGA ...............................................................17 3.3 Problém nadměrného urychlení .........................................................................17 3.4 Shrnutí 17
4
Migrační strategie..................................................................................................................... 19 4.1 Migrační kritérium .............................................................................................19 4.1.1 Synchronní migrace..............................................................................20 4.1.2 Asynchronní migrace............................................................................20 4.1.2.1 Míra konvergence ....................................................................21 4.2 Komunikační topologie......................................................................................22 4.2.1 Statické topologie .................................................................................23 4.2.2 Dynamické topologie............................................................................23 4.2.3 Stupeň propojení – DOC ......................................................................24 4.3 Migrační koeficient............................................................................................24 4.4 Způsob přenosu migrantů ..................................................................................25 4.4.1 Migrace jedinců ....................................................................................25 4.4.2 Migrace schémat...................................................................................25
iv
4.4.3 Úprava ohodnocení migrujících jedinců ..............................................26 4.5 Cíl experimentů..................................................................................................26 5
Experimenty............................................................................................................................. 28 5.1 Testovací úlohy..................................................................................................28 5.1.1 Reálné funkce dvou proměnných .........................................................28 5.1.2 Klamné funkce......................................................................................31 5.1.3 Problém obchodního cestujícího (TSP)................................................32 5.2 Volba nastavení parametrů PGA .......................................................................33 5.2.1 Volba velikosti populace ......................................................................34 5.2.2 Volba ostatních parametrů....................................................................37 5.3 Migrace synchronní vs. asynchronní, hromadná vs. individuální .....................41 5.4 Statická vs. dynamická topologie ......................................................................49 5.5 Migrace jedinců vs. migrace schémat................................................................53 5.6 Migrace bez úpravy ohodnocení vs. migrace s úpravou ohodnocení ................53 5.7 Volba nové migrační strategie ...........................................................................58 5.8 Experimenty s referenčními funkcemi...............................................................58 5.8.1 Experimenty s funkcí 10xF2 ................................................................59 5.8.2 Experimenty s funkcí 10xF101 ............................................................61 5.8.3 Experimenty s funkcí 10xF103 ............................................................63 5.8.4 Experimenty s funkcí 50xDF3..............................................................64 5.8.5 Experimenty s funkcí 50xPDF .............................................................66 5.8.6 Experimenty s funkcí TSP30................................................................67 5.8.7 Experimenty s funkcí TSP50................................................................69 5.8.8 Diskuse výsledků experimentů.............................................................71
6
Závěr ......................................................................................................................................... 72
Přílohy Příloha A: Popis prostředí pro experimenty Příloha B: Zdrojový kód nadstavby knihovny GAlib pro PGA.
v
1 Úvod Umělá inteligence je vědní disciplína zabývající se všemi postupy a algoritmy, které vedou k napodobení projevů inteligentního chování člověka [Mařík1993]. Její součástí je tedy i řešení úloh, které jsou ve valné většině NP-obtížné či dokonce NP-úplné (obtížně řešitelné nebo neřešitelné v polynomiálním čase). Proces řešení takových úloh se dá často transformovat na prohledávání stavového prostoru, který představuje množinu všech potenciálních řešení dané úlohy a bývá často příliš velký. Úkolem umělé inteligence je hledání a zdokonalování takových metod prohledávání stavového prostoru, které by zaručily nalezení optimálního či alespoň suboptimálního řešení v přijatelném čase. Pro jednodušší úlohy se používají deterministické metody. Význačným představitelem této skupiny metod jsou metody gradientní, jejichž výhodou je, že vždy naleznou takové řešení, které je na jistém okolí nejlepší (naleznou extrém účelové funkce). Není ale zaručeno, že toto řešení je nejlepší v celém stavovém prostoru (hlavně u složitějších, multimodálních účelových funkcí). Nalezené řešení bývá často pouze suboptimálním řešením daného problému a gradientní algoritmus není schopen bez změny počátečních podmínek sám od sebe najít řešení jiné – lepší ve smyslu účelové funkce. Z toho důvodu bylo nutno vyvinout metody, ve kterých se jistým způsobem uplatňuje náhoda – metody, které nevynechávají žádnou oblast stavového prostoru a které jsou samy od sebe schopné „vymanit se ze spárů suboptimálního řešení“. Genetické algoritmy (GA) patří mezi právě takové metody. Řadí se sice mezi stochastické metody prohledávání stavového prostoru, ale využívají také vlastností deterministických metod. Z obou skupin se snaží převzít ty nejlepší vlastnosti – od stochastických metod stejnoměrné prohledání všech oblastí stavového prostoru („exploration“) a od deterministických metod zase zaměření úsilí prohledávání do slibných oblastí („exploitation“). Mezi těmito dvěma zřejmě protichůdnými požadavky pak GA ustavují kompromis pomocí svých parametrů. Jsou schopny nám poskytnout relativně kvalitní řešení v přijatelně krátkém čase (vzhledem k obtížnosti problému). Proto si plně zasluhují pozornost, která jim je v současnosti věnována po celém světě, i úsilí vědců porozumět jejich zákonitostem a jevům, které se v nich projevují.
1
Ve snaze po urychlení GA vznikly paralelní implementace genetických algoritmů. Některé z nich využívají takový model, v němž je populace rozdělena do několika subpopulací, mezi nimiž v určitých intervalech migrují jedinci. Migrace je zvláštní typ operátoru, jehož chování je v některých aspektech nečekané a není ještě zcela uspokojivě vysvětleno ([Cantú-Paz1999b]). Cílem této práce je rozšířit poznatky v oblasti paralelních modelů GA, zvláště pak osvětlit vliv různých parametrů migrační strategie na kvalitu řešení nalezeného pomocí PGA. S využitím těchto poznatků byl navržen nový operátor migrace, pomocí něhož PGA dosahuje výsledků srovnatelných nebo lepších, než dosahuje s využitím dosud používaných migračních operátorů. Nová migrační strategie je ale lépe přizpůsobena pro práci v dynamickém prostředí a pro vývoj subpopulací na geograficky značně vzdálených počítačích (např. v síti Internet).
1.1
Struktura textu
Tato diplomová práce je organizována následovně: kapitola 2 shrnuje poznatky o vlastnostech jednoduchých GA (SGA) nutné pro pochopení jejich činnosti; kapitola 3 obsahuje popis možností paralelizace GA, popis jednotlivých modelů paralelních GA a jejich srovnání; v kapitole 4 jsou identifikovány a popsány rysy migračních operátorů a navrženy nové vlastnosti migrační strategie, jejichž účinnost je ověřena experimentálně v kapitole 5. Kapitola 6 shrnuje dosažené výsledky a obsahuje doporučení oblastí pro další studium.
2
2 Jednoduché genetické algoritmy Genetické algoritmy se inspirovaly v přírodě a přírodních vědách. Snaží se napodobit evoluci takovým způsobem, jakým probíhá v přírodě. Jako teoretický podklad užívají Mendelovu teorii genetiky a Darwinovu teorii přirozeného výběru. Teorie přirozeného výběru hlásá, zjednodušeně řečeno, přežití silnějšího, tzn., že rychlejší, silnější a inteligentnější jedinci mají větší šanci na přežití v dynamickém a neustále se měnícím prostředí, než jedinci pomalejší, slabší a hloupější. Tito „horší“ jedinci ve svém prostředí přežívají spíše díky tomu, že mají štěstí, než díky svým vlastnostem. Proto se reprodukce (vytváření další generace) zúčastňují také, avšak v menší míře, než jedinci „lepší“. G. Mendel zase objevil mechanismus přenosu charakterových vlastností z rodiče na potomka. Později se ukázalo, že za jednotlivé vlastnosti jsou zodpovědné geny, které jsou uspořádány lineárně v chromozomech. V oblasti GA se proto také používají výrazové prostředky převzaté z těchto biologických disciplín. Mluvíme o jedincích (nebo o genotypech, chromozomech, strukturách či řetězcích) v populaci. (Pro potřeby GA se většinou dělá určité zjednodušení: každý biologický jedinec má obyčejně více druhů chromozomů – zde se předpokládají jedinci s jediným chromozomem, proto je možné oba pojmy „sjednotit“. Existují ale také implementace GA s diploidními jedinci – s jedinci se dvěma chromozomy.) Chromozomy jsou dále tvořeny lineárně uspořádanými1 geny (jinak také rysy, vlastnostmi či dekodéry). Stav genu reprezentujícího určitou vlastnost (např. barvu vlasů) může nabývat několika hodnot, kterým se říká alely. Každý chromozom reprezentuje jedno potenciální řešení problému. Význam a výklad formátu chromozomů – jeho fenotyp – je plně v rukou uživatele. Proces evoluce populace jedinců pak odpovídá prohledávání stavového prostoru.
Poznamenejme, že GA spadají do širší třídy metod - tzv. evolučních algoritmů (EA). Rozdíl se týká hlavně použitých datových struktur, jimiž už nemusí být lineární binární řetězce. Jedinci mohou být představováni libovolnou datovou strukturou – např. maticí, stromem apod. Je třeba k nim ale také doplnit vhodné operátory mutace a křížení – viz. dále.
1
3
2.1
Vlastnosti GA
GA jsou metody pro prohledávání stavového prostoru aplikovatelné na širokou škálu typů úloh (nejsou závislé na typu řešeného problému) [Michalewicz1995]. Nastavením jejich parametrů lze upravit rovnováhu mezi zaměřením na slibné oblasti a prohledáním co největší části stavového prostoru. Obou těchto vlastností GA používají ke svému prospěchu. Mnoho výzkumníků i praktiků z velice rozmanitých oborů lidské činnosti si oblíbilo GA. Jejich popularita pramení hlavně z následujících vlastností [Michalewicz1995]: •
GA jsou robustní v tom smyslu, že jsou aplikovatelné na velice rozmanité úlohy, přičemž je na nich potřeba provést pouze minimální úpravy
•
GA umí pracovat se všemi druhy stavových prostorů, včetně nehladkých, multimodálních a nespojitých
•
GA umí hledat řešení z hlediska více kritérií a není přitom nutné explicitně definovat společnou účelovou funkci
•
GA umí nalézt větší počet různých řešení blízkých optimálnímu
• GA se dají použít pro dynamické optimalizace Jak již bylo řečeno, GA patří do třídy stochastických algoritmů a přesto se velice liší od náhodných prohledávacích metod. Kombinují totiž elementy řízeného i stochastického prohledávání. Další důležitou vlastností GA je to, že pracují s celou populací potenciálních řešení – ostatní metody pracují vždy pouze s jedním bodem stavového prostoru, s jediným řešením. Tato populace podstupuje simulovanou evoluci: v každé generaci se „lepší“ jedinci množí, zatímco „horší“ odumírají. Rozlišení mezi „horší“ a „lepší“ provádí již výše zmíněná účelová (ohodnocovací) funkce, která zastupuje v GA roli životního prostředí jedinců. Hodnota účelové funkce pro daný chromozom pak vyjadřuje míru přizpůsobenosti jedince danému prostředí. K řešení určitého problému pomocí GA (nebo pomocí jakéhokoli jiného EA) je třeba splnit následující požadavky [Michalewicz1995]: 1) najít vhodnou reprezentaci potenciálních řešení problému (vhodně zvolit „formát“ chromozomu) 2) najít způsob, jak vytvořit počáteční populaci chromozomů tak, aby představovaly přípustná řešení 3) sestavit účelovou funkci, díky níž budeme schopni rozhodnout, který jedinec je „lepší“ a který „horší“ 4) zvolit nebo vytvořit vhodné genetické operátory, které ovlivňují tvorbu nových potomků 5) vhodně nastavit různé parametry používané v GA (velikost populace, pravděpodobnosti uplatnění genetických operátorů, apod.) V současnosti stále nejsou vyvinuty exaktní a přesné metody pro řešení výše uvedených 5 bodů, protože jsou značně závislé na konkrétním problému. Nastavení GA je proto velice ovlivněno zkušenostmi a odhadem uživatele, takže správná volba parametrů GA se stále ještě považuje spíše za umění [Michalewicz1995]. 4
2.2
Účelová funkce (Objective function)
Účelová (ohodnocovací) funkce je vlastně jediný element GA, který je zcela a beze zbytku v moci uživatele. Měla by jí být věnována maximální pozornost – je to totiž právě ona, která má největší vliv na celý proces evoluce, protože její extrém hledáme. Pomocí ní se určuje kvalita jedince (schopnost přežití v okolním prostředí) – ať už přímo, nebo nepřímo přes škálovací funkci. Pro hodnotu, kterou chromozomu účelová (a případně ještě škálovací) funkce přiřadí, se v anglické literatuře vžil název fitness value. Protože neexistuje český ekvivalent tohoto anglického výrazu, budu v této práci dále používat pro hodnoty účelové funkce výraz fitness.
2.3
Princip činnosti GA
Populace genetického algoritmu je tvořena jedinci – umělými chromozomy představujícími zakódovaná řešení problému, který si přejeme vyřešit. Každý jedinec je ohodnocen. Toto ohodnocení udává, jak dobré řešení problému jedinec představuje. Nejlepší řešení jsou vybírána a rekombinována s ostatními. Během simulované evoluce pak dobré vlastnosti jedinců přežívají a navzájem se mísí, čímž vytvářejí nové – a možná kvalitnější – jedince. Přirozený výběr zároveň eliminuje v populaci špatné vlastnosti. Běh všech jednoduchých GA se řídí podle následujícího předpisu (P(k) označuje populaci jedinců obhospodařovaných GA v k-té generaci): k=0 Inicializace P(k) Ohodnocení P(k) Opakuj k = k+1 Selekce P(k) z jedinců v P(k-1) Rekombinace P(k) Ohodnocení P(k) Dokud není splněna terminální podmínka Věnujme se jednotlivým krokům podrobněji.
2.3.1
Inicializace
Každý GA potřebuje znát způsob, jakým může na počátku běhu inicializovat populaci, tzn. jak může vygenerovat první sadu jedinců, od nichž se bude celý vývoj odvozovat. Často se používá náhodná inicializace, která však není vhodná např. při práci s omezeními, kdy není třeba populaci naplnit jen nějakými libovolnými jedinci, ale je vhodné vytvořit ji z jedinců přípustných. V určitých případech je proto nutné vytvořit vlastní způsob inicializace populace pro konkrétní řešený problém. Počáteční populace totiž musí obsahovat dostatek informací, ze kterých by GA mohl vyvinout kvalitní řešení, takže by měla rovnoměrně pokrývat celý stavový prostor.
5
2.3.2
Selekce
Jak už název napovídá, operátor selekce v GA představuje ekvivalent Darwinova přirozeného výběru. Modeluje princip přežití silnějších jedinců. Vybírá z populace „lepší“ jedince, kteří se pak účastní rekombinace (tvorby nové populace – viz. dále). Nejedná se ale o jednoduché vybrání N nejlepších jedinců z populace – pokud má selekce napodobovat skutečné biologické procesy, pak musí zaručit to, že se rekombinace může zúčastnit i nejhorší z jedinců v populaci. Toho se většinou dociluje pravděpodobnostními mechanismy výběru jedinců – ke každému chromozomu je na základě jeho fitness jistým způsobem přiřazena pravděpodobnost jeho přežití. Způsob výpočtu pravděpodobnosti přežití jedince je závislý na použité selekční metodě. Několik z nich je popsáno v následujících odstavcích. Výčet si neklade žádné nároky na úplnost, uvádím jen nejznámější a nejpoužívanější selekční schémata [Goldberg1989]. Ruletová selekce (Roulette-wheel selection) Pravděpodobnost přežití jedince je přímo úměrná jeho fitness. Rozhodnutí, zda jedinec přežije a objeví se i v další generaci, se dá představit jako náhodný pokus, ve kterém točíme ruletovým kolem (odtud i název metody) a vybíráme vždy toho jedince, na něhož padne kulička. Přitom platí, že čím má jedinec vyšší fitness, tím více ruletových políček zabírá. Toto selekční schéma s sebou ale nese i řadu problémů: má potíže se škálováním, zvládá pouze maximalizační problémy, způsobuje velké vzorkovací chyby a pro správnou funkci vyžaduje relativně velké populace. Pro nápravu těchto vlastností byla vyvinuta další selekční schémata. Pořadová selekce (Rank selection) Pravděpodobnost přežití jedince nesouvisí přímo s jeho kvalitou, ale s jeho umístěním v posloupnosti, kde jsou chromozomy seřazeny podle fitness. Předpokládejme například, že máme populaci o dvou chromozomech A a B, které mají fitness f ( A) = 1 a f (B ) = 99 . Ruletová selekce jim přiřadí pravděpodobnosti přežití p( A) = 0.01 a p(B ) = 0.99 . Pořadová selekce je nejprve uspořádá podle velikosti poř ( A) = 1 , poř (B ) = 2 a nad tímto pořadím proběhne ruletová selekce. Výsledkem je tedy p( A) = 0.33 a p(B ) = 0.67 . Takovýto postup odstraňuje problémy se škálováním (omezuje předčasnou konvergenci – přílišné omezení různorodosti populace), odstraňuje problémy se vzorkováním u malých populací a zvládá maximalizační i minimalizační problémy. Deterministický výběr (Deterministic sampling) Jde opět o modifikaci ruletové selekce. Výběr probíhá ve dvou fázích. V první fázi se pro všechny jedince v populaci vypočítá pravděpodobnost jejich přežití. Na základě této pravděpodobnosti se určí počet kopií každého jedince v nové populaci: n(i ) = p(i ) ⋅ PopSize (počet kopií i-tého jedince je pravděpodobnost jeho přežití násobená velikostí populace). Tento počet je ale obecně reálné číslo – každý jedinec se do nově vytvářené populace zkopíruje pouze tolikrát, kolik udává celá část n(i).
6
Ve druhé fázi se zbývající volná místa v populaci, jejichž počet se rovná součtu desetinných částí všech n(i), obsadí tak, že se vybere potřebný počet jedinců z populace seřazené podle velikosti desetinných částí n(i). Zbytkový stochastický výběr (Reminder stochastic sampling) Tato metoda je obměnou deterministického výběru. První fáze probíhá naprosto stejně. Ve druhé fázi se pro rozdělení neobsazených míst v nové generaci aplikuje klasická ruletová selekce. I tato metoda napravuje vliv malé populace. Turnajová selekce (Tournament selection) Tato metoda využívá jiného principu výběru než metody předchozí. Pro obsazení každého jedince v nové generaci se PopSize-krát uspořádá turnaj. Ze staré generace se náhodně vybírají n-tice chromozomů (v nichž se chromozomy buď mohou, nebo nesmí opakovat) a do nové generace se vkládají vždy nejlepší jedinci z těchto n-tic. Volbou n se dá také ovlivňovat selekční tlak (čím větší n, tím větší selekční tlak). V krajním případě, kdy n = PopSize a chromozomy se v n-tici nemohou opakovat, by byla nová populace tvořena ze samých nejlepších jedinců populace stávající (předčasná konvergence).
2.3.3
Rekombinace
Za krokem Rekombinace se skrývá uplatnění dvou genetických operátorů – křížení a mutace. Oběma dohromady se říká rekombinační operátory, protože vytvářejí z rodičů potomky.
2.3.4
Křížení
Křížení je reprodukční operátor, který simuluje náhodnou výměnu informací obsažených v rodičích při vytváření nového potomka. Jeho působením by se měly vytvářet lepší chromozomy. V evolučních algoritmech (EA) obecně mohou být jedinci reprezentováni libovolnou datovou strukturou, k níž je samozřejmě třeba vytvořit vlastní operátor křížení. Mluvíme-li ale o GA, které využívají lineární binární chromozomy, můžeme použít křížení jednobodové, dvoubodové nebo vícebodové. Body, ve kterých dochází ke křížení, se volí náhodně. Volbou n bodů křížení se oba rodiče rozdělí na n+1 částí. Vlastní křížení probíhá tak, že do prvního potomka se zkopírují např. liché části z prvního rodiče a sudé z druhého. U druhého potomka je tomu opačně. Četnost křížení se volí nastavením pravděpodobnosti křížení, což je jeden ze základních parametrů GA (typicky se volí přibližně 0.75). Optimální hodnota závisí na konkrétním řešeném problému a stanovuje se empiricky. Přihlíží se také k obecně přijímanému empirickému pravidlu, že pro malé populace se nastavuje velká pravděpodobnost křížení a naopak. Mezi další varianty křížení patří rovnoměrné křížení. Rovnoměrné křížení je n-bodové křížení, u něhož se nevolí n konkrétních bodů, ale u každého bitu se náhodně rozhoduje s pravděpodobností 0.5, do kterého z potomků bude patřit. Bylo pozorováno, že pomocí křížení se dosahuje rychlejšího prohledávání stavového prostoru, než pomocí mutace, při
7
použití účelových funkcí, které obsahují nelineární vztahy mezi jednotlivými bity řetězců [FlexGA1998]. Pokud je pravděpodobnost, že ke křížení dojde za určitým bitem, závislá na pozici v řetězci, říkáme, že operátor křížení má polohové zaměření. Pokud rozdělení počtu bitů prohozených operátorem křížení není rovnoměrné, říkáme, že křížení má distribuční zaměření. Jednobodové křížení má maximální polohové a minimální distribuční zaměření, zatímco u rovnoměrného křížení je to naopak. Jedno a dvoubodové křížení v homogenní populaci generují málo odlišné jednotlivce. Rovnoměrné křížení naproti tomu prohazuje bity nezávisle na jejich pozici. Proto se doporučuje používat u menších populací, kde zaručuje prohledání větší oblasti stavového prostoru. Ve velkých populacích, kde se rozmanitost chromozomů zajišťuje spíše jejich počtem, je vhodnější dvoubodové křížení.
2.3.5
Mutace
Na mutaci se obvykle pohlíží jako na méně důležitý, druhořadý reprodukční operátor, který dokáže vrátit nazpět neuváženě ztracené hodnoty genů (alely), zabraňuje předčasné konvergenci a poskytuje možnosti náhodného prohledávání v blízkém okolí „zkonvergované“ populace (blízké okolí je třeba chápat jako množinu chromozomů, kteří se liší od jedinců v populaci změnou v minimálním počtu bitů). Mutace tedy umožňuje GA dostat se z lokálního extrému účelové funkce. Jak často dojde k uplatnění tohoto operátoru určuje pravděpodobnost mutace, která je dalším ze základních parametrů GA. Typicky se nastavuje na hodnotu velice malou (1% i méně) a v některých implementacích se dokonce dynamicky mění podle míry konvergence populace. Vlastní mutace probíhá ve své základní podobě tak, že se procházejí všechny bity v populaci a s pravděpodobností Pmut je jejich hodnota změněna na opačnou. Průměrně je tedy změněna hodnota nmut = Pmut ⋅ L ⋅ PopSize bitů, přičemž všechny mutace se mohou vyskytnout v 1 až nmut chromozomech. Pokud se pravděpodobnost mutace nastaví velká, ztrácí se výhody GA a prohledávání stavového prostoru přechází v prohledávání náhodné. Výzkumy ukazují [FlexGA1998], že u malých populací by měla být nastavená velká pravděpodobnost mutace a opačně. Dá se to vysvětlit tím, že u malých populací mutace napomáhá k prohledání větší části stavového prostoru, zatímco u velkých populací je velikost prohledaného stavového prostoru zaručena velikostí populace.
2.4
Parametry GA
Jednoduchý předpis GA uvedený v odstavci 2.3 je nejrůznějšími způsoby ovlivňován mnoha parametry. Podívejme se teď na ně podrobněji a jednotlivě.
2.4.1
Velikost populace
Počet jedinců v populaci je jedním z nejdůležitějších atributů, který musíme nastavit, pokud chceme GA použít. Otázka volby adekvátní velikosti populace je velice obtížná, protože silně závisí na obtížnosti problému. Pokud bude populace příliš malá, GA nemusí 8
mít dostatek informací, aby identifikoval dobré rysy řešení [Harik1996]. Velká populace naopak může znamenat plýtvání časem při zpracovávání nepotřebných jedinců, což může vést ke značnému snížení efektivity. V literatuře [Harik1996, Cantú-Paz1999c] jsou uvedeny vztahy, pomocí nichž lze pro známé účelové funkce a za určitých zjednodušujících podmínek vypočítat takovou velikost populace, která pro daný problém minimalizuje výpočetní čas. Tyto vztahy však nejsou natolik triviální, jak by si většina uživatelů GA přála, a vyskytují se v nich členy, jejichž význam není na první pohled zřejmý a jejichž hodnota se nesnadno určuje. Příklad použití těchto vztahů najdete v kapitole 5.
2.4.2
Elitismus
V průběhu vývoje GA je možné, že nejlepší jedinec v populaci vlivem náhodných procesů odumře a v nově vytvořené populaci se již neobjeví. GA tak může „zapomenout“ kvalitní nalezené řešení, pokud si ho „nezapamatuje“ někde mimo populaci. Elitismus představuje způsob, jakým se dá tomuto nežádoucímu jevu předejít. Při jeho použití je několik (typicky 1 či 2) nejlepších jedinců přímo přeneseno do nově vytvářené populace. Kvalita nejlepšího řešení nalezeného genetickým algoritmem se pak v průběhu vývoje může pouze zvyšovat.
2.4.3
Velikost překrytí
Tento parametr se uplatňuje při tvorbě nové generace jedinců. Existují implementace GA s nulovým překrytím [Goldberg1989], tzn. že využívají nepřekrývající se populace. Všichni jedinci z nově vytvořené populace prošli evolučním cyklem, a pokud jsou některé z nich shodné s nějakým jedincem z předchozí generace, pak je to pouze vlivem náhody. Jiné implementace GA [DeJong1975] zase naopak zcela záměrně podrobují evoluci pouze část populace, tzn. že každou generaci se vytvoří např. pouze 60% nových jedinců, zatímco zbylých 40% jedinců zůstává v populaci z předchozí generace.
2.4.4
Nahrazovací strategie
Často opomíjeným parametrem GA jsou také nahrazovací strategie. Po selekci se z rodičů pomocí reprodukčních operátorů vytvoří sada potomků, které by měly být součástí nově vytvářené generace. Které jedince v populaci ale nahradit nově vytvořenými? Existuje mnoho přístupů. Je zřejmé, že nahrazovací strategie se neuplatní u GA, který využívá nepřekrývající se populace. Tam je vytvořena populace zcela nová, která prostě nahradí starou. Pokud se ale použije překrývajících se populací, je třeba rozhodnout, které jedince nahradit nově vzniklými. Potomci mohou např. nahradit své vlastní rodiče, nejhorší nebo náhodně vybrané jedince z populace nebo třeba jedince, kterým jsou nejvíce podobné – to často závisí na konkrétní implementaci. Někdy se také nově vygenerovaní jednotlivci prostě připojí k populaci, z níž jsou potom odebráni nejhorší jedinci, čímž populace opět získá svou původní velikost. Nové chromozomy se tedy do nové generace mohou nebo nemusí dostat – to záleží na jejich kvalitě. Nejčastěji používaným přístupem je náhrada nejhorších jedinců.
9
2.5
Druhy GA
V průběhu doby, kdy se GA používají, mnoho experimentátorů vyvinulo vlastní druhy GA a dali jim různé názvy, čímž vytvořili podle mého názoru mylný dojem, že mezi různými druhy GA jsou značné rozdíly. Všechny GA podle mne pracují ve své podstatě podle stejného předpisu a vývoj populace je řízen pomocí sady parametrů popsaných výše. Na druhy GA tak můžeme nahlížet jen jako na sady typických hodnot parametrů, a pokud řekneme, že určitý GA je takového a takového druhu, znamená to pouze to, že přibližně víme, jaké hodnoty parametrů tento GA používá. Následuje stručný popis několika druhů GA a jejich modifikací.
•
Jednoduchý GA (Simple GA).
•
Tento algoritmus popsal Goldberg ve své knize [Goldberg1989]. Používá nepřekrývající se populace a volitelně i elitismus. GA se stálým stavem (Steady-State GA) Tento algoritmus je podobný algoritmu popsanému DeJongem [DeJong1975]. Používá překrývající se populace a je tedy třeba vybrat nahrazovací strategii.
•
Inkrementální GA (Incremental GA) Jedná se o variantu předchozího typu GA. Také používá překrývající se populace, ale s velkým překrytím. Typicky se v každé generaci vytvoří pouze jeden nebo dva potomci. I zde je třeba určit nahrazovací strategii. Nejčastěji se nahrazují nejhorší jedinci v populaci.
•
Mikro GA (µGA) Jedná se o variantu GA s velice malou populací. Ukazuje se, že µGA se dostává do oblasti blízké optimu rychleji než SGA [FlexGA1998]. Oproti SGA používá µGA mnohem menší populace – typicky o 5 jedincích. Obyčejné GA s malými populacemi nevykazují dostatečně dobré chování díky nedostatku informací ke zpracování a předčasné konvergenci, proto se u µGA pravidelně zavádějí do populace noví jedinci. Téměř vždy se volí elitistická selekce. Jako míru kvality tohoto typu GA je třeba brát nejlepší dosud nalezené řešení a žádné jiné statistické „průměrovací“ míry. GA se stochastickým kódováním (Stochastic GA) Tento algoritmus využívá dynamické kódování řetězců. Ty pak nepředstavují konkrétní řešení problému, ale celé prohledávané regiony stavového prostoru charakterizované normálním rozdělením s vektorem středních hodnot a s variační maticí. V průběhu evoluce se pak mění právě popis rozdělení, tj. střední hodnoty a variační matice, čímž se prohledávané regiony posouvají do slibnějších oblastí stavového prostoru. Nalezení většího počtu extrémů – Niching Technika zvaná niching (od niche – nika, výklenek) se používá, pokud chceme zjistit větší počet řešení. GA musí obhospodařovat stabilní populace na okolí několika extrémů. Fitness jedinců na různě dobrých extrémech je uměle „normalizována“, čímž vytvořené skupiny jedinců získají stabilitu. Počet jedinců v té které části populace je vlastně jinou mírou kvality extrému, který tato část populace obývá. Příslušnost jedince
•
•
10
k výklenku určuje buď míra s vlastnostmi vzdálenosti (časově a výpočetně náročnější) nebo „značka“, která je součástí chromozomu, ale neúčastní se evoluce.
2.6
Práce s omezeními
Omezením není myšleno určení rozsahu každého z parametrů. Určení rozsahu parametrů vymezuje vlastně stavový prostor úlohy – n-rozměrný interval (hyperkrychli), ve které GA vyhledává řešení. Problémy nastanou až tehdy, když je obor přípustných řešení podmnožinou stavového prostoru. To se může stát např. tehdy, když jsou jednotlivé parametry optimalizované pomocí GA na sobě vzájemně závislé. Co pak udělat s jedinci, kteří vzniknou působením rekombinačních operátorů, ale přitom představují nepřípustná řešení? Používají se v zásadě tři postupy, jak se s takovými omezeními vypořádat.
2.6.1
Pokutové funkce
Nevyhovující řešení je ponecháno v populaci, ale záměrně se prohlásí za málo kvalitní, takže v dalším běhu GA samo „odumře“. Tato metoda je velice jednoduchá, ale efektivně pracuje pouze u slabých omezení, kde je poměr počtu přípustných řešení ku počtu prvků prohledávaného prostoru dostatečně velký. Pokud je totiž většina vygenerovaných řešení přípustná, pak se v každé generaci malé množství nepřípustných řešení opravdu eliminuje. Pokud by byla ale většina vygenerovaných jedinců nepřípustná, pak je velká šance, že tato nepřípustná řešení budou přežívat i do dalších generací.
2.6.2
Dekodéry a opravné algoritmy
Na nelegální jedince se snažíme uplatnit speciální postupy, kterými by se chromozomy „legalizovaly“. Tyto postupy obyčejně vyžadují transformaci genotypu na fenotyp a bývají výpočetně velice nákladné. Existují dvě varianty těchto postupů:
•
•
2.6.3
Oprava. Fyzické nahrazení nevyhovujícího jedince v populaci nejbližším vyhovujícím (ve smyslu určité metriky). Tato náhrada se pak účastní další evoluce místo původního jedince. Dekódování. Nepřípustný jedinec zůstane v populaci a účastní se další evoluce. Pro určení jeho kvality se ale použije ohodnocení nejbližšího přípustného řešení.
Problémově závislá reprezentace
Ideálním řešením problému s omezeními je případ, kdy se povede najít takovou reprezentaci řešení úlohy, jejíž každá instance je řešením přípustným. Jinou možností je najít takové rekombinační operátory, které by generovaly pouze přípustná řešení. Nalezení jednoho ani druhého však není obecně jednoduchou úlohou (spíš naopak) a často se oba přístupy kombinují. Takto sestavený GA je pak ale specifický pro jeden konkrétní typ úlohy.
11
2.7
Stavební bloky, schéma-teorém
Jak jsem již uvedl v odstavci 2.3, pokud nás zajímá, proč genetické algoritmy fungují, dostaneme většinou vágní odpověď, že v jedincích identifikují kladné rysy, které kombinují s jinými, zatímco záporné rysy během evoluce odumírají. Co ale jsou ony kladné rysy? Představa „kladných vlastností“ se formalizuje konceptem stavebních bloků. Stavební bloky jsou schémata, která představují dobře přizpůsobené sady vlastností, jež lze najít u většiny dobrých řešení. Jinak řečeno, pro určité typy problémů lze vypozorovat, že mezi přibližně stejně dobrými jedinci v populaci existuje podobnost v tom smyslu, že tito jedinci obsahují na některých svých pozicích stejné bity. Lze tedy říct, že kvalitu jedince hodně ovlivní obsazení určitých konkrétních pozic, zatímco na obsazení ostatních pozic záleží méně. Podobnostmi mezi řetězci se zabývá hypotéza o schématech. Narozdíl od řetězců, které jsou tvořeny pouze abecedou obsahující dva prvky {0,1}, má abeceda schémat navíc ještě jeden prvek - *. Tvoří ji tedy množina {0,1,*}. Pokud se ve schématu objeví symbol *, pak schéma reprezentuje všechny řetězce, které na tomto místě obsahují jakýkoli konkrétní symbol a shodují se v ostatních pozicích se schématem. Pokud tedy schéma obsahuje n symbolů *, pak v případě binární abecedy chromozomů reprezentuje 2n řetězců. Každému schématu H se přiřazuje jeho řád o(H), což je počet specifických pozic (nul a jedniček) ve schématu. Schéma řádu o(H) obsahuje L-o(H) symbolů *, kde L je délka schématu. Takové schéma tedy pokrývá 2L-o(H) řetězců. Definiční délka schématu δ(H) je největší vzdálenost dvou specifických symbolů ve schématu. Schémata řádu 0 a 1 (neobsahují žádný nebo pouze jeden konkrétní symbol) mají definiční délku 0. Celkový vliv genetických operátorů na schémata vyjadřuje následující vztah: δ (H ) f (H ) (2.1) m( H , t + 1) ≥ m( H , t ) ⋅ ⋅ 1 − PC ⋅ − PM ⋅ o( H ) , L −1 f kde jednotlivé symboly mají následující význam: m( H , t ) počet řetězců v populaci, které pokrývá schéma H v čase t (v t-té generaci)
f (H )
fitness schématu (průměrné ohodnocení jedinců odpovídajících schématu)
f
střední fitness populace
PC
pravděpodobnost křížení
PM
pravděpodobnost mutace
δ (H )
definiční délka schématu délka schématu řád schématu
L o(H)
Jednotlivé členy v závorce odpovídají postupně selekci, křížení a mutaci, které byly popsány v předcházejících odstavcích.
12
Rozborem vztahu (2.1) lze určit, že stavební bloky chromozomů tvoří krátká nadprůměrná schémata nízkého řádu. Krátká proto, aby s co největší pravděpodobností nebyla porušena křížením, a nízkého řádu, aby co nejpravděpodobněji přežila uplatnění mutace. Zvětšením pravděpodobnosti křížení se zvětší nejen rekombinace stavebních bloků, ale také pravděpodobnost, že budou zničeni i dobří jedinci. Jedno a dvoubodové křížení zachovávají velké množství stavebních bloků, zatímco rovnoměrné křížení prohazuje bity nezávisle na jejich pozici a velké množství stavebních bloků tak poruší. Vztah (2.1) popisující vzrůstající podíl dobrých jedinců v populaci se dá slovy zapsat jako [Michalewicz1995]: Schéma-teorém: Počet krátkých, nadprůměrných schémat nízkého řádu se s přibývajícími generacemi genetického algoritmu v populaci exponenciálně zvyšuje. Okamžitým důsledkem tohoto teorému je, že GA prozkoumávají stavový prostor prostřednictvím schémat s výše uvedenými vlastnostmi, které jsou následně použity k výměně informací během křížení [Michalewicz1995]: Hypotéza o stavebních blocích: GA vyhledává ve stavovém prostoru optimální řešení identifikací a skládáním krátkých, nadprůměrných schémat nízkého řádu, která se označují jako stavební bloky. Hypotéza o stavebních blocích je jinými slovy vyjádřené ono vágní tvrzení uvedené na začátku odstavce 2.7. Zde je vidět, že toto tvrzení není samoúčelné a že existují dobré důvody předpokládat, že hypotéza o stavebních blocích platí.
2.8
Shrnutí
V této kapitole byly popsány základní vlastnosti a principy jednoduchých GA. GA se používají při řešení úloh v mnoha odvětvích, a to jak technických (počítačové vědy, strojírenství, robotika,… ), tak i netechnických (obchod, plánování, rozvrhování,…) [Goldberg1994]. Mezi velké zápory, které brání masivnějšímu rozšíření SGA, patří také poměrně dlouhá doba běhu u složitých problémů. Jednou z možností, jak urychlit běh GA je paralelizace. Již z popisu uvedeného v této kapitole je zřejmé, že mnoho kroků během vývoje GA je možno úspěšně paralelizovat. O jednotlivých možnostech paralelizace pojednává následující kapitola.
13
3 Paralelní genetické algoritmy GA mohou pro vyřešení některých reálných problémů vyžadovat velké množství (desetitisíce či statisíce) volání účelové funkce. V závislosti na čase potřebném k ohodnocení jednoho chromozomu může běh GA trvat celé dny, měsíce nebo dokonce roky, než nalezne přijatelné řešení. Naštěstí GA pracují s populací nezávislých řešení, díky čemuž je snadné rozdělit výpočetní nároky mezi několik procesorů. Paralelní charakter GA byl rozpoznán již před mnoha lety a mnoho experimentátorů použilo paralelní GA (PGA) ke snížení doby potřebné k nalezení řešení značně složitých problémů. Ve skutečnosti by někdo mohl říct, že GA jsou paralelní již ve své podstatě a že tedy není těžké vytvořit rychlé PGA. PGA jsou ale složité nelineární algoritmy ovlivňované mnoha parametry, které určují efektivitu prohledání stavového prostoru a kvalitu nalezeného řešení. Součástí návrhu PGA je např. i rozhodnutí, zda použít jednu populaci či několik populací. V obou případech je třeba opatrně zvolit velikost populace (nebo populací). Pokud chceme navíc použít více populací, musíme určit kolik. Populace mohou zůstat oddělené nebo mezi sebou mohou komunikovat a vyměňovat si jedince. Komunikace s sebou nese další rozhodnutí ohledně komunikačních topologií, počtu vyměňovaných jedinců a četnosti komunikace. Obyčejně se tyto parametry nastavují buď podle výsledků několika provedených experimentů nebo jsou nalezeny náhodou. Problémem těchto přístupů je, že často vedou na plýtvání komunikačními zdroji nebo na neadekvátní kvalitu prohledávání stavového prostoru. Díky tomu se může stát, že experimentátorům se PGA jeví jako nepraktické nebo nevhodné k použití. V této kapitole je popsáno, co vše lze na GA paralelizovat a najdete zde rozdělení PGA podle nejčastěji používaných modelů.
14
3.1
Paralelní model vs. paralelní implementace
Při použití termínu „paralelní genetický algoritmus“ je třeba rozlišovat mezi případy, kdy slovo „paralelní“ označuje paralelní model GA a kdy paralelní implementaci GA.
•
•
Modely. Sekvenční model GA (přesněji nazývaný globální model) má jedinou populaci a neklade žádná omezení na to, který jedinec může rekombinovat s jiným. Globální model GA se tradičně slučuje s jednoduchým GA, který bývá popisován v literatuře. V paralelním modelu GA je buď více populací (ostrovní model) nebo jedna populace rozdělená do mnoha subpopulací. Mluvíme-li ovšem o modelu, neklademe žádná omezení na skutečnou implementaci. Implementace. Sekvenční i paralelní modely GA mohou být implementovány paralelně i sekvenčně. Sekvenční implementace globálního modelu je tradiční přístup popisovaný ve většině literatury o GA. Jeden proces běžící na jednom uniprocesoru provádí všechny výpočty. V paralelní implementaci globálního modelu mohou být některé nebo všechny kroky GA (selekce, křížení, mutace, ohodnocování) prováděny současně v několika procesech běžících na paralelním počítači nebo na síti spolupracujících počítačů. V sekvenční implementaci paralelního modelu GA běží několik procesů (každý se stará o svou subpopulaci) a sdílejí strojový čas jednoho procesoru. V paralelní implementaci paralelního modelu běží každý z procesů na „svém“ procesoru paralelního počítače nebo sítě pracovních stanic.
Je zřejmé, že sekvenční implementace paralelních modelů nepřináší proti sekvenční implementaci globálního modelu žádné úspory času, spíše by tomu mělo být naopak. Umožňuje nám ale studovat jevy, které se u PGA projevují. Samozřejmě, že pro praktické využití paralelních modelů GA je přirozenější a efektivnější navržený paralelní model také paralelně implementovat. Pokud se v dalším textu objeví výraz paralelní GA (PGA), mám tím na mysli paralelní model GA. Pokud by se mělo jednat o paralelní implementaci některého z modelů, pak to bude výslovně uvedeno.
3.2
Možnosti paralelizace
Jak již bylo řečeno, GA jsou díky své struktuře velice vhodné pro paralelní implementace, protože v nich spousta činností probíhá nezávisle (nebo je lze přizpůsobit tak, aby nezávisle probíhaly). První pokusy o paralelní implementace využívaly globální model GA. Následující rozdělení modelů PGA je převzato z [Cantú-Paz1999c]:
3.2.1
Paralelizace globálního modelu
Algoritmus obhospodařuje jednu populaci stejně jako u obyčejného sekvenčního GA. Máme-li ovšem k dispozici více procesorů, není důvod, proč populaci nerozdělit na několik částí, jejichž ohodnocení bychom svěřili jednotlivým procesorům [Bethke1976, Grefenstette1981]. Ohodnocování jednotlivých chromozomů zřejmě není závislé na ničem
15
jiném, takže se dá velice snadno paralelizovat. Tento přístup, nazývaný „master-slave“, využívá výpočetní možnosti procesorů „slave“ jen z části. Uplatnění všech genetických operátorů je prováděno na procesoru „master“. Komunikace mezi procesorem „master“ a procesory „slave“ probíhá tehdy, když „master“ odesílá skupiny jedinců jednotlivým „slaveům“ k ohodnocení a když procesory „slave“ vrací vypočtené hodnoty účelové funkce procesoru „master“. S jistou dávkou opatrnosti se však dá rozdělit mezi jednotlivé procesory „slave“ i uplatňování genetických operátorů. Protože je v modelu jedna populace, selekce bere v úvahu všechny jedince a každý chromozom má šanci reprodukovat se se všemi ostatními. Pokud je algoritmus synchronní (v každé generaci se čeká na dokončení ohodnocování celé populace), algoritmus se chová stejně jako sekvenční GA. Asynchronní implementace (procesory nečekají na dokončení ohodnocení celé populace) se svou činností liší od obyčejného GA a používají se jen zřídka. Pokud se v dalším textu objeví zmínka o globálním modelu, myslí se tím synchronní implementace paralelizace globálního modelu.
3.2.2
Vícekmenové PGA (Multi-deme PGA)
V tomto modelu je využito již o něco složitější myšlenky. Populace je rozdělena do několika subpopulací, neboli kmenů, které se vyvíjejí izolovaně od ostatních a příležitostně si mezi sebou vymění některé ze svých chromozomů [Grefenstette1981]. Této výměně jedinců se říká migrace a je ovlivňována několika parametry (viz. kapitola 4). Rozdělení na kmeny lze považovat za tak úplné, že na každý kmen lze pohlížet jako na zcela samostatný GA (se vším, co k tomu náleží: je možno použít odlišné selekční metody, odlišné metody křížení a mutace, dokonce i odlišné účelové funkce). Vícekmenové PGA zavádějí nové principy v činnosti GA a jejich chování je odlišné od chování jednoduchých GA. V globálním modelu probíhá selekce i reprodukce v rámci celé populace, zatímco u vícekmenových PGA berou genetické operátory v úvahu jen jedince v rámci kmene. Někdy se jim také říká „ostrovní“ PGA, protože v populační genetice existuje model pro relativně izolované populace, kterému se říká ostrovní model. Protože velikost jednotlivých kmenů je menší než velikost celé populace u jednoduchých GA, dalo by se předpokládat, že PGA bude rychleji konvergovat. Tento předpoklad se potvrzuje, ale zároveň bylo zjištěno, že kvalita nalezeného řešení může být horší [Grosso1985]. Podle stupně rozdělení populace na kmeny se navíc rozlišují dvě podskupiny tohoto modelu: • Hrubě dělené PGA (Coarse-Grained PGA) – populace rozdělena do několika poměrně velkých subpopulací [Grosso1985]. • Jemně dělené PGA (Fine-Grained PGA) – populace rozdělena do velkého počtu velmi malých subpopulací. Extrémním případem by bylo, kdyby ke každému chromozomu byl přiřazen jeden procesor. Tento model je vhodný pro masivně paralelní architektury počítačů, ale dá se implementovat na jakémkoli multiprocesoru.
16
Jemně i hrubě dělené PGA využívají stejných principů a hranice mezi nimi se těžko stanovuje (pokud vůbec existuje). Přesto může být někdy užitečné toto rozdělení provádět. Já sám jsem si tedy stanovil následující hranici mezi hrubě děleným a jemně děleným PGA: pokud je počet kmenů menší než počet jedinců v každém z nich, lze mluvit o hrubě děleném PGA, pokud je tomu naopak, pak takový PGA nazývám jemně děleným.
3.2.3
Hybridní (hierarchické) PGA
Jedná se o poslední model paralelizace. Jak už název napovídá, tato metoda používá kombinaci některých výše zmíněných metod. Snaží se přitom využít dobrých vlastností každé z nich a potlačit jejich nedostatky. Poprvé se tento nápad objevil v [Grefenstette1981]. Základní myšlenka je jednoduchá: použijte PGA s několika kmeny, které jsou samy tvořeny nějakou formou PGA. Ti, kteří používají tento přístup, si od něj slibují lepší výkon, než by měla kterákoliv jeho samotná součást. Jako příklad lze uvést třeba implementaci s několika „master-slave“ PGA na nižší úrovni tvořících kmeny hrubě děleného PGA na úrovni vyšší [Cantú-Paz1999c].
3.3
Problém nadměrného urychlení
Jedním z kontroverzních témat týkajících se PGA je problém nadměrného urychlení (Superlinear Speedup Problem). Spočívá v rozporu mezi teoretickými předpoklady a empirickými výsledky. Teoretická úvaha říká přibližně toto: pokud vyřešení libovolné úlohy trvá jedinému procesoru dobu T, pak je logické tvrdit, že N procesorům bude trvat řešení té samé úlohy minimálně dobu T/N (předpokládá se přitom, že celkový počet výpočetních úkonů potřebný k vyřešení úlohy je pro oba případy stejný). Tedy celý výpočetní proces se při použití N procesorů může urychlit maximálně N-krát. Podle empirických výsledků dochází ale mnohdy i k více než N-násobnému zkrácení výpočetní doby, což je předmětem diskusí na téma nadměrného urychlení. Bylo vytvořeno několik pokusů o vysvětlení tohoto jevu. Nejsmysluplnější se zdá být vysvětlení, které napadá snad jediný napadnutelný předpoklad výše uvedené teoretické úvahy, který říká, že celkový objem výpočetní práce je shodný pro paralelní i pro sekvenční model GA. Možné vysvětlení nadměrného urychlení je to, že paralelní modely nějakým způsobem provádějí méně činnosti než modely sekvenční. Redukce výpočtů je podle jedné hypotézy způsobena hlavně zvýšením selekčního tlaku, za které je odpovědná migrace jedinců mezi populacemi [Cantú-Paz1999c]. Migrace ale není jediným možným vysvětlením tohoto jevu. Jiným vysvětlením může být i to, že menší populace se vejdou celé do vyrovnávacích pamětí procesorů [Belding1995], nebo nesprávné určení velikosti populace, takže není zaručena konvergence ke stejně kvalitnímu řešení.
3.4
Shrnutí
Tato kapitola poskytla stručný přehled paralelních modelů GA, principů jejich činnosti, popis jejich vzájemných odlišností i odlišností vůči jednoduchým GA. V odstavci 3.3 byl
17
popsán jev nadměrného urychlení vyskytující se u PGA využívajících migraci a právě migrace byla označena jako možné vysvětlení tohoto jevu. Migrační operátor si proto zasluhuje zvláštní pozornost a je mu věnována celá následující kapitola.
18
4 Migrační strategie Jak již bylo řečeno, migrační strategie (krátce migrace) má v PGA za úkol provádět výměnu jedinců (migrantů) mezi jednotlivými kmeny. Proč je vlastně ale migrace zapotřebí? Představme si, co se stane, rozdělíme-li populaci jednoduchého GA na r kmenů, jejichž vývoj bude probíhat odděleně. Dostaneme tedy vlastně r genetických algoritmů a každý z těchto r kmenů dosáhne různě kvalitního řešení. Povrchní úvaha nám může napovědět, že více kmenů znamená více pokusů o vyřešení problému, a tedy i větší šanci na nalezení dostatečně kvalitního řešení. Bohužel jsme přitom zapomněli na fakt, že každý z kmenů pracuje s r-krát menší populací, která konverguje mnohem rychleji než původní celková populace jednoduchého GA. Migrace pro nás tedy představuje způsob, kterým chceme udržet různorodost populace na dostatečné úrovni tak, aby byla zajištěna požadovaná kvalita prohledání stavového prostoru. Předtím, než se migrací budu zabývat podrobněji, je třeba si stanovit, čím je migrace definována a co se vlastně za ní skrývá. Definice migrace zatím není nikde exaktně stanovena a různí experimentátoři některé z jejích parametrů zanedbávají nebo vůbec neuvažují. Pro účely této diplomové práce představuje migrace proces výměny chromozomů mezi kmeny, který určují čtyři parametry, z nichž tři jsou netriviální:
• Migrační kritérium • Komunikační topologie • Migrační koeficient • Způsob přenosu migrantů (jedinců nebo schémat) Podívejme se nyní na význam jednotlivých parametrů a na jejich vliv na běh PGA.
4.1
Migrační kritérium
Tento parametr určuje, ve kterých okamžicích bude k migraci docházet. Kritérium zde představuje spoušť, pomocí níž je migrace vyvolávána. Podle způsobu spouštění se 19
migrace dělí na synchronní, kdy migrace probíhá v konstantních intervalech, a na asynchronní, kdy komunikace mezi kmeny probíhá jen jako reakce na určitou událost.
4.1.1
Synchronní migrace
Většina vícekmenových PGA využívá synchronní migraci. Její výhodou je, že migrační kritérium je jednoduché, a proto se snadno implementuje a jeho vyhodnocení vyžaduje malé množství strojového času (jedná se pouze o porovnání současné generace vývoje PGA s předdefinovaným migračním intervalem). Nevýhodou synchronní migrace je to, že vůbec nezohledňuje otázku, kdy je vhodná doba pro uskutečnění migrace. Pozorování ukazují, že příliš častá nebo příliš řídká migrace může degradovat efektivitu algoritmu [Tanese1987]. Při konstantním migračním intervalu mohou totiž nastat dva nežádoucí případy:
•
Příliš častá migrace (hraniční případ – migrace probíhá každou generaci). Takovým nastavením do značné míry potlačíme hlavní rys hrubě dělených PGA – oddělený vývoj kmenů. Počet správných stavebních bloků v migrujících jedincích nemusí být dostatečný k tomu, aby ovlivnil prohledávání stavového prostoru správným směrem. Zjednodušeně řečeno, většina migrujících jedinců nebude natolik dobrá, aby pro cílovou populaci znamenala významnější přínos. Migrace v tomto případě tedy probíhá zbytečně často a plýtvá tak komunikačními zdroji. Nesmíme zapomínat, že vývoj jednotlivých kmenů může probíhat na geograficky značně vzdálených počítačích, a velké množství komunikací značně snižuje efektivitu a zvyšuje náklady na běh programu.
•
Příliš řídká migrace (hraniční případ – izolované kmeny). Pokud bude k výměně jedinců docházet jen zřídka, dáváme tím PGA možnost, aby v jednotlivých kmenech vyvinul jedince představující různá lokální optima. Protože kmeny v PGA bývají řádově menší než populace u jednoduchých GA, snáze a rychleji předčasně konvergují k lokálním optimům. Protože mutace bývá u PGA značně nebo úplně potlačena, představuje migrace jediný způsob, jak vnést do subpopulací nový genetický materiál. Na dalších parametrech (migračním koeficientu a kvalitě migrujících jedinců) pak bude záležet to, jaký vliv bude mít tento „injektovaný“ nový genetický materiál na cílový kmen, tzn. zda bude dostatečně silný, aby populaci nějak ovlivnil. Protože běh GA je ve své podstatě náhodný, může se stát, že vlivem stochastických procesů nebudou nově zařazení jedinci pro vývoj populace vůbec použiti.
4.1.2
Asynchronní migrace
Jak již bylo uvedeno, asynchronní migrace využívá kritéria, která spouštějí migraci jako reakci na jistou událost. Podmínky vyskytující se v těchto kritériích mají za úkol se co nejvíce přiblížit odpovědi na otázku, kdy je vhodné migraci provést. Většina takových kritérií obsahuje ve své podmínce míru konvergence populace, kterou porovnává s předem daným prahem [Grosso1985]. Vyhodnocení takového kritéria
20
je časově mnohem nákladnější, než vyhodnocení kritéria u synchronní migrace, právě díky výpočtu míry konvergence. Asynchronní migrace může probíhat v zásadě dvěma způsoby: (1) výměna jedinců se vyvolá buď pro všechny kmeny hromadně a proběhne najednou v jedné generaci, nebo (2) se bude týkat pouze jednoho kmene (který splní migrační kritérium) a s ním souvisejících kmenů (podle komunikační topologie). Příkladem prvního typu asynchronní migrace může být strategie [Braun1990], která výměnu spouští poté, co všechny kmeny zcela zkonvergovaly (autor užívá termín „zdegenerovaly“). V souvislosti se zkonvergováním kmenů se zavádí nový pojem – epocha. Epocha představuje počet generací, po které se musí kmen vyvíjet, než dojde k jeho úplné konvergenci. Migrace je tedy spouštěna na konci každé epochy. Jinými slovy, epocha představuje část vývoje kmene mezi dvěma migracemi. Při použití Braunova migračního kritéria jsou epochy pro všechny kmeny vždy stejně dlouhé. Pro účely této práce se ale délka epoch může pro každý kmen lišit.
4.1.2.1
Míra konvergence
Jakožto hlavní veličina sledovaná v podmínkách kritérií asynchronní migrace si míra konvergence zaslouží podrobnější pohled. Její použití je logické. Má-li migrační kritérium poskytnout odpověď na otázku, zda je už třeba provést migraci, musí sledovat veličinu, která určitým způsobem kvantifikuje schopnost kmene vyvinout lepší řešení. Klesne-li míra této schopnosti pod nastavený práh, je třeba vyvolat přísun nového genetického materiálu. Konvergence obecně popisuje stejnorodost populace. Stejnorodá populace má samozřejmě menší schopnost vytvořit lepší jedince, jedná se tedy o míru opačnou, než byla popsána v minulém odstavci, a jako s opačnou s ní také musíme pracovat: migrace by se měla vyvolat, stoupne-li míra konvergence nad daný práh. Konkrétní definice míry konvergence se různí a každý experimentátor s PGA si může nadefinovat míru vlastní. Každá míra konvergence by ale měla splňovat následující vlastnosti: • Číslo z intervalu <0;1> • Pro zcela stejnorodou populaci nabývat hodnoty 1 • Pro zcela různorodou populaci nabývat hodnoty 0 Stejnorodost jedinců lze navíc posuzovat z různých hledisek. Může se jednat o stejnorodost ohodnocení nebo o stejnorodost reprezentace jedinců. Zřejmě totiž platí, že jedinci se stejnou reprezentací mají také stejné ohodnocení, ale obecně nemusí platit, že jedinci se stejným ohodnocením mají shodnou reprezentaci. Přesnějším popisem stejnorodosti populace by určitě byla konvergence založená na reprezentaci jedinců. Porovnávání reprezentace a následný výpočet konvergence je však časově náročné, proto se téměř výlučně využívá konvergence ohodnocení. Jako první kandidát na míru konvergence se okamžitě nabízí rozptyl (nebo směrodatná odchylka) ohodnocení jedinců v populaci. Tyto míry by se ale musely nějakým způsobem normalizovat, aby splňovaly výše kladené podmínky na míru konvergence.
21
Jako jiné příklady míry konvergence (popisující stejnorodost ohodnocení jedinců v populaci) lze např. uvést: • Populační konvergence. Zohledňuje stejnorodost populace pro generaci g. Pro maximalizační problémy:
convP ( g ) =
Avg ( g ) Max ( g )
(4.1)
Min ( g ) Avg ( g )
(4.2)
Pro minimalizační problémy:
convP ( g ) = kde
convP ( g ) je hodnota konvergence v generaci g, Avg (g ) je průměrné ohodnocení jedinců v populaci v generaci g, Min ( g )
Max(g) •
je minimální ohodnocení jedince v populaci v generaci g, je maximální ohodnocení jedince v populaci v generaci g.
Generační („časová“) konvergence. Zohledňuje časový vývoj nejlepších nalezených jedinců. Jinak řečeno, generační konvergence nabývá hodnoty 1, jestliže v předchozích n generacích nedošlo k vylepšení ohodnocení nejlepšího jedince. Pro maximalizační problémy:
convG (g ) =
Max ( g − n) Max ( g )
(4.3)
Min (g ) Min (g − n)
(4.4)
Pro minimalizační problémy:
convG ( g ) =
Význam členů vztahů (4.3) a (4.4) je shodný s významy členů vztahů (4.1) a (4.2). Takto definované míry konvergence navíc vyžadují striktně kladné hodnoty účelové funkce. V této práci je užita konvergence populační.
4.2
Komunikační topologie
Tradičně opomíjeným parametrem PGA je topologie propojení mezi jednotlivými kmeny. Topologie je přitom důležitým faktorem ovlivňujícím efektivitu PGA, protože určuje, jak rychle (nebo jak pomalu) se dobrý jedinec rozšíří do dalších kmenů. Komunikační topologie je také hlavním faktorem ovlivňujícím náklady na migraci. Hustě propojená topologie vám sice zaručí lepší promísení jedinců z jednotlivých kmenů, zároveň má ale také značné nároky na komunikaci. Topologie se podle okamžiku vzniku dají rozdělit na statické a dynamické.
22
4.2.1
Statické topologie
Hlavním trendem při výzkumu vícekmenových PGA bylo použití statických topologií. Způsob propojení jednotlivých kmenů byl znám již před začátkem běhu PGA a během něj se neměnil. Mnoho implementací PGA se statickou topologií přirozeně využívalo topologie počítačové sítě dostupné experimentátorům, běžné jsou např. implementace na hyperkrychlích [Cohoon1991], [Tanese1987] nebo na prstencích [Gordon1993].
4.2.2
Dynamické topologie
V rozlehlých počítačových sítích, jejichž topologie není předem známa a navíc se s časem mění (vznikají a zanikají komunikační kanály mezi jednotlivými částmi sítě), nelze statickou topologii propojení kmenů použít. V dynamických topologiích není komunikace kmene omezena na předem danou a neměnnou sadu jiných kmenů. Místo toho se za běhu PGA vybírá kmen, který splňuje určité kritérium. Jak již bylo řečeno v úvodu této kapitoly, migrace pro nás představuje způsob, jak udržet různorodost kmenů na dostatečné úrovni. Při snaze o dosažení tohoto cíle sehrává velice důležitou roli výběr zdrojového kmene, ze kterého budou jedinci migrovat do kmene cílového. Představme si situaci, kdy dva kmeny, mezi nimiž má proběhnout migrace, dokonvergovaly k přibližně stejným řešením. Vezmeme nejlepší jedince ze zdrojové populace (snažíme se přenést nejlepší vlastnosti) a nahradíme jimi nejhorší jedince v populaci cílové (potlačujeme špatné rysy). Vše se zdá být v pořádku až do chvíle, než si uvědomíme, že jsme z cílové populace odstranili ty chromozomy, které v ní zajišťovaly alespoň minimální úroveň různorodosti, a nahradili jsme je chromozomy, které konvergenci cílové populace značně zvýšily. Migrace má v takovém případě přesně opačný efekt, než jaký by měla mít. Pro výběr dvojic kmenů se proto typicky používá kritérium založené na míře vzdálenosti mezi dvěma subpopulacemi nebo mezi reprezentanty každé z nich [Lin1994]. Míru vzdálenosti dvou jedinců lze založit buď na genotypu nebo na fenotypu.
•
•
Genotypická vzdálenost. Jedinou smysluplnou mírou vzdálenosti pro genotypy se zdá být Hammingova metrika. Vzdálenost dvou jedinců je rovna počtu bitů, v nichž se oba jedinci liší. Tuto míru vzdálenosti lze bez připomínek uplatnit pouze na binární jedince, které pro nás nepředstavují opravdu nic jiného, než sadu jedniček a nul. Pro všechny ostatní typy jedinců je vhodnější založit míru vzdálenosti na fenotypu. Příklad: Mějme čísla –7 až 7 reprezentována ve dvojkové soustavě jedničkovým doplňkem. Číslo 7 je tedy vyjádřeno jako 0111, číslo 6 jako 0110 a číslo –7 jako 1111. Hammingova vzdálenost binární reprezentace čísla 7 a čísla 6 je 1, stejně jako vzdálenost binárních reprezentací čísel 7 a –7, což pro většinu problémů není právě žádoucí. Fenotypická vzdálenost. Pokud chceme počítat smysluplnou vzdálenost většiny typů jedinců, nezbývá nám, než provádět převod genotypu na fenotyp (což může být zdlouhavé) a v prostoru fenotypu zvolit určitou metriku, jichž je nekonečné množství. Přesto, že je tento způsob určování vzdálenosti pracnější, než výpočet vzdálenosti v Hammingově metrice, vyjadřuje přesněji to, co intuitivně chápeme pod
23
pojmem vzdálenosti. Není ale pravidlem, že výběr na základě fenotypu musí dávat lepší výsledky než výběr podle genotypu.
4.2.3
Stupeň propojení – DOC
Stupeň propojení topologie (DOC – degree of connectivity) určuje hustotu topologie, neboli od kolika dalších kmenů subpopulace přebírá migrující jedince. Pokud má topologie velký stupeň propojení, budou se dobrá řešení šířit rychle, pokud je síť kmenů propojena jen řídce, kvalitní jedinci se budou šířit pomaleji a vývoj kmenů bude probíhat izolovaněji. To na druhou stranu zase umožní zaměřit prohledávání do různých oblastí stavového prostoru a vyvinout tak různá řešení, která se mohou později zkombinovat a vytvořit lepší jedince. Bylo ověřeno [Cantú-Paz1997a], že různé topologie se stejným stupněm propojení dosahují téměř shodné kvality výsledků po proběhnutí stejného počtu epoch. To tedy znamená, že nejdůležitějším parametrem topologie sítě je právě stupeň propojení, protože nejvýznamněji ovlivňuje efektivitu PGA. Empirické studie [Cantú-Paz1994] ukázaly, že PGA s hustě propojenou topologií jsou schopné najít globální řešení s menším počtem vyhodnocování kriteriální funkce, než PGA s řídce propojenými kmeny. To s sebou samozřejmě zase nese zvýšené náklady na komunikaci. Studie byla prováděna na plně propojených topologiích, 4-D hyperkrychlích, na toroidní síti 4x4 a na jednosměrných i obousměrných prstencích.
4.3
Migrační koeficient
Migrační koeficient je jediným triviálním parametrem migrace. Je to číslo, které udává, kolik jedinců má být v cílové populaci změněno. Podle způsobu přenosu jedinců (viz. odst. 4.4) může také udávat skutečný počet jedinců vybraných ze zdrojové populace a fyzicky přenesených do populace cílové. Společně s četností migrace a stupněm propojení topologie určuje migrační koeficient množství nového genetického materiálu injektovaného do subpopulace. Vyvstává zde otázka, zda je lepší migrovat častěji menší množství jedinců nebo zřídka větší dávku. Pokud přihlédneme k nákladům na komunikaci, zdá se efektivnější druhá možnost, protože při ní dochází k menšímu množství navazování a rušení spojení mezi kmeny (či mezi vzdálenými počítači). Pro volbu velikosti migračního koeficientu existují dvě přirozené hranice: na jedné straně můžeme chtít zajistit co nejmenší vliv sousedních kmenů, pak nastavíme migrační koeficient nulový a PGA se změní na sadu izolovaných populací (stejně, jako když zvolíme migrační kritérium, které výměnu jedinců nikdy nespustí); na straně druhé můžeme naopak požadovat maximální vliv sousedních kmenů, ovšem při zachování hlavních rysů kmene, který přísun genetického materiálu vyžaduje. Formálně zapsáno, migrační koeficient má smysl volit z intervalu:
nmig ∈ 0 ;
24
nD δ +1
kde
n mig
je migrační koeficient,
nD
je velikost kmene,
δ
je stupeň propojení topologie (DOC).
Pozorování ukazují, že existuje jistá kritická hodnota migračního koeficientu, pod níž je efektivita algoritmu snižována relativní izolací kmenů a nad níž PGA může nalézt stejné řešení jako globální GA [Grosso1985].
4.4
Způsob přenosu migrantů
GA jsou silně inspirovány jevy, které byly rozpoznány a popsány v několika různých vědách – v genetice, evoluční teorii nebo třeba v demografii. Nejinak je tomu i s migrací, která nás provází po celou dobu lidské existence.
4.4.1
Migrace jedinců
Vzhledem k tomu, jak migrace probíhá v přírodě, je zcela přirozené, že se až dosud prováděla jako přesun konkrétních jedinců, většinou nejlepších v populaci. Avšak i tito nejlepší jedinci v populaci mohou obsahovat nežádoucí geny, které se vnesou do cílové populace.
4.4.2
Migrace schémat
Přenosu nežádoucích genů se snaží zabránit nový způsob přenosu jedinců, který je navržen v této práci. Zdrojovou populaci podrobí zkoumání a extrahuje z ní její dobré rysy (pokusí se najít dobré stavební bloky). Ty pak ve formě schématu přenese do cílové populace, kde bude schéma „přetisknuto“ přes takový počet jedinců, který udává migrační koeficient. Identifikace přenášených schémat je v této práci realizována tak, že se pro každý gen spočítá poměrný výskyt jednotlivých alel vzhledem k velikosti populace. Přesáhne-li četnost některé z alel určitý práh, např. 80%, je tato alela zařazena do migrujícího schématu. Pro binární řetězce lze tvorbu schémat tedy popsat takto: pro každý bit chromozomu se spočítá výskyt symbolů „0“ a „1“ přes celou subpopulaci, a kde bude výskyt některého ze symbolů větší než daný práh, tam se do schématu zařadí příslušný symbol. Do bitů, na kterých ani „0“ ani „1“ nedosáhly požadovaného prahu, se vloží symbol „*“. Práh má smysl volit 1 v intervalu ; 1 , kde k je počet možných alel daného genu. Pro binární řetězce je tedy k 1 přípustný interval ;1 . 2 Je třeba si také uvědomit, že migrace schémat se bude lišit od migrace jedinců jedině tehdy, pokud populace zdrojového kmene nebude ještě zkonvergovaná. V plně zkonvergované populaci výše uvedený proces tvorby schématu sice bude pracovat, ale jeho výsledkem bude schéma pokrývající jediného jedince – jedince, jímž je tvořena celá
25
zdrojová populace. Jak bude tvorba schémat účinná záleží na konkrétním nastavení prahu pro tvorbu schémat a na aktuální míře konvergence zdrojové populace. Nežádoucí chování tohoto typu migrace tedy může nastat hlavně v případě asynchronní hromadné migrace (pokud by práh pro tvorbu schématu byl nastaven nižší než míra konvergence populace, která spouští migraci, téměř jistě přejde migrace schémat v migraci jedinců).
4.4.3
Úprava ohodnocení migrujících jedinců
Dalším faktorem, který má znatelný vliv na velikost účinku migrace, je fitness migrujících jedinců. Pokud totiž jedinci nebudou dostatečně kvalitní v porovnání s chromozomy cílové populace, snadno se může stát, že ihned následující generaci budou selekcí z populace vyřazeni a že tedy do evolučního procesu populace vůbec nezasáhnou. Neovlivní tedy ani různorodost populace. To ve svém důsledku znamená, že migrace bude mít menší účinek a bude proto vyžadována častěji, což vede na plýtvání komunikačními zdroji. Aby se alespoň trochu zamezilo tomuto nežádoucímu vlivu, je možné upravit ohodnocení migrujících jedinců při jejich vkládání do cílové populace na vyšší hodnotu (např. na ohodnocení nejlepšího jedince v populaci). Tím se zamezí tomu, aby nové chromozomy byly z populace vyřazeni selekcí, a tak se přímo zúčastní vývoje kmene alespoň v jedné generaci.
4.5
Cíl experimentů
V předchozích čtyřech odstavcích byly popsány důležité aspekty ovlivňující účinnost migračních strategií. V tabulce Tab. 1 jsou shrnuty rozdíly mezi vlastnostmi, které mívají konvenčně používané migrační strategie, a mezi mnou doporučenými atributy, které by měly zajistit lepší účinnost a efektivitu migračních strategií. Některé vlastnosti migrace jsou v této práci použity poprvé. Je to použití asynchronní individuální migrace, migrace schémat a úprava fitness u migrujících jedinců. V následující kapitole je uvedena série experimentů, které by měly potvrdit či vyvrátit pravdivost předpokládaných účinků jednotlivých atributů migrace na vývoj PGA. Všechny atributy jsou na jedné z referenčních funkcí otestovány jednotlivě, čímž se ověřuje, zda nové nastavení plní naše očekávání. Na závěr jsou vybrané hodnoty atributů sestaveny dohromady a takto vzniklá migrační strategie je otestována na všech referenčních úlohách. Předpokládám přitom, že jednotlivé rysy migrace jsou relativně nezávislé, že se vzájemně neovlivňují, což nemusí být apriori splněno (a také to splněno není – nemá smysl třeba mluvit o synchronní individuální migraci).
26
Konvenčně Atribut používaný doporučený atribut v této práci
Předpokládaný přínos
Asynchronní migrace
Migrace nebude spouštěna v konstantních intervalech, ale v okamžiku, kdy „bude třeba“. Komunikace mezi kmeny by měla probíhat v optimální míře – neměla by být ani příliš častá (plýtvání komunikačními zdroji) ani řídká (plýtvání výpočetními zdroji).
Hromadná migrace
Individuální migrace
Každý kmen si bude moci vyžádat přísun nového genetického materiálu v okamžiku, kdy to potřebuje, a bude pokračovat ve vývoji. Nebude muset čekat, až budou migraci vyžadovat i všechny ostatní kmeny. Mělo by dojít ke zkrácení doby potřebné pro nalezení stejně kvalitního řešení.
Statická topologie
Dynamická topologie
Ke každému cílovému kmeni vyžadujícímu migraci jsou vybírány zdrojové kmeny na základě míry vzdálenosti. Takto prováděná migrace by měla lépe bránit předčasné konvergenci.
Migrace schémat
Ze zdrojové populace se vyberou kladné rysy a přenesou se v podobě schématu do populace cílové. Migrace schémat by měla omezit přenos špatných vlastností ze zdrojové populace, zároveň zajistit menší narušení kladných vlastností populace cílové a ve větší míře zachovat její různorodost.
S úpravou ohodnocení
Chromozomům vkládaným do cílové populace bude zvýšeno ohodnocení, aby se zúčastnily vývoje alespoň 1 generaci po migraci. Migrace by měla mít vyšší účinek a měla by být vyvolávána méně často.
Synchronní migrace
Migrace jedinců
Bez úpravy ohodnocení
Tab. 1. Porovnání konvenčně používaných a nově navržených vlastností operátoru migrace.
27
5 Experimenty K důkladnému ověření všech hypotéz vyslovených v předchozích kapitolách by bylo třeba provést značně rozsáhlé série testů s nejrůznějšími kombinacemi nastavení jednotlivých parametrů PGA a migrace. Na to však není v této práci prostor. Rozhodl jsem se proto ověřit své domněnky týkající se parametrů migrace (viz. tabulka Tab. 1) nejdříve jednotlivě na jedné z testovacích úloh (10xF2 – viz. následující odstavec). Následně jsem parametry zkombinoval a s takto vytvořenou migrační strategií jsem provedl experimenty na všech testovacích úlohách. Všechny uvedené výsledky jsou průměrnými hodnotami z několika běhů jednotlivých GA.
5.1
Referenční úlohy
Pro ověření vlastností různých nastavení migračních operátorů jsem použil 7 referenčních úloh, které se často užívají pro srovnání kvality různých evolučních algoritmů. Ve třech z nich jde o minimalizaci reálné funkce dvou proměnných, ve dvou jde o nalezení extrému klamné funkce a zbylé dvě referenční úlohy představují dvě různé konfigurace problému obchodního cestujícího.
5.1.1
Reálné funkce dvou proměnných
Jedná se o DeJongovu funkci F22 [DeJong1975] a Whitleyho funkce F101 a F103 [Whitley1996]. Jsou to nelineární neseparabilní funkce dvou proměnných s mnoha lokálními a jediným globálním extrémem. Nalezení jejich globálního extrému na určitém intervalu není triviální úloha, a proto se tyto funkce používají jako referenční úlohy.
2
Při
přepisování
(
)
funkce
F2
jsem
udělal
chybu.
Skutečný
tvar
této
funkce
je
f (x, y ) = 100 ⋅ x − y + (1 − x ) . Protože se chybu podařilo objevit až v pozdní fázi práce, nestihl jsem ji už opravit (znamenalo by to opakovaní velkého množství experimentů). Tato chyba ale není nijak zásadní, protože nás nezajímá konkrétní řešení daného problému, ale porovnání různých metod řešení. 2
2
2
28
Název
Definice
(
F2
f ( x , y ) = 100 ⋅ x 2 − y 2
F101
f ( x , y ) = − x ⋅ sin
F103
f ( x , y ) = 0 .5 +
) + (1 − x ) 2
2
x − ( y + 47 ) − ( y + 47 ) ⋅ sin
sin 2
(
y + 47 +
x 2
)
x 2 ⋅ 100 + y 2 − 0.5
[1 + 0.001 ⋅ (x − y ) ]
2 2
Tab. 2. Definice použitých testovacích funkcí dvou neznámých.
Definiční obor
Počet bitů
Rozlišení v
xay
xay
xay
F2
− 2 . 048 ; 2 . 047
12
0.001
0.0
F101
− 512 ; 511
10
1.0
-955.96
F103
− 100 ; 100
10
0.19550343
0.0
Název
min(F)
arg(min(F))
[1 .0 ; 1 .0 ] [511 .0 ; 403 .0 ]
[− 48 .19; − 48 .19 ]
Tab. 3. Parametry a vlastnosti použitých testovacích funkcí 2 proměnných.
Celý problém je navíc ztížen tím, že chromozomy jsou pro každou funkci tvořeny 10 uměle vytvořenými stavebními bloky – 10 páry proměnných x a y. Ohodnocení chromozomu je pak součtem 10 funkčních hodnot – součtem ohodnocení všech deseti párů. Chromozomy pro funkce 10xF2, 10xF101 a 10xF103 mají tedy délku postupně 240, 200 a 200 bitů.
Obr. 1. Průběh funkce F2(x, y) na intervalu − 2 . 048 ; 2 . 047
29
× − 2 . 048 ; 2 . 047
Obr. 2. Průběh funkce F101(x, y) na intervalu − 512 ; 511 × − 512 ; 511
Obr. 3. Průběh funkce F103(x, y) na intervalu − 100 ; 100
30
× − 100 ; 100
5.1.2
Klamné funkce
Jako další testovací funkce jsem použil 4-bitovou klamnou funkci DF3 [Whitley1995] a 4-bitovou částečně klamnou funkci PDF [Kubalík2000]. U obou funkcí se hledá maximum a chromozomy jsou tvořeny 50 kopiemi 4-bitových stavebních bloků. Klamná funkce DF3 (viz obrázek Obr. 4) obsahuje klamný atraktor 0000. Tento řetězec je atraktorem proto, že schémata řádu nižšího než 4, pokrývající tento řetězec, mají vyšší fitness než schémata, která daný řetězec nepokrývají. „Klamnost“ atraktoru vyplývá z toho, že řetězec sám má poměrně nízkou fitness a jeho přitažlivost je způsobena vysokým ohodnocením jeho sousedů (0001, 0010, 0100 a 1000).
Obr. 4. Definice klamné funkce DF3.
Obtížnost částečně klamné funkce PDF (viz obrázek Obr. 5) plyne částečně z klamnosti některých schémat, ale hlavně v problematickém kombinování důležitých schémat.
Obr. 5. Definice částečně klamné funkce PDF.
31
5.1.3
Problém obchodního cestujícího (TSP)
Posledními referenčními úlohami jsou dvě instance problému obchodního cestujícího – TSP30 a TSP50 (obě převzaty z [I-1]). Jedná se o nalezení nejkratšího cyklu, který prochází všemi městy rozmístěnými v pravoúhlé síti. Souřadnice měst pro oba problémy jsou uvedeny v tabulce Tab. 4. Jsou zde uvedeny jako příklad problému řešeného pomocí evolučních algoritmů (EA) – jedinci nejsou reprezentováni binárními řetězci, ale seznamem celých čísel. Délka nejkratších cyklů je 423.741 pro TSP30 a 422 pro TSP50. x
y
x
y
x
y
x
y
1
54
67
16
41
26
1
5
6
26
37
52
2
54
62
17
45
21
2
5
25
27
37
69
3
37
84
18
58
35
3
5
64
28
38
46
4
41
94
19
62
32
4
7
38
29
39
10
5
2
99
20
82
7
5
8
52
30
40
30
6
7
64
21
91
38
6
10
17
31
42
41
7
25
62
22
83
46
7
12
42
32
42
57
8
22
60
23
71
44
8
13
13
33
43
67
9
18
54
24
64
60
9
16
57
34
45
35
10
4
50
25
68
58
10
17
33
35
46
10
11
13
40
26
83
69
11
17
63
36
48
28
12
18
40
27
87
76
12
20
26
37
49
49
13
24
42
28
74
78
13
21
10
38
51
21
14
25
38
29
71
71
14
21
47
39
52
33
15
44
35
30
58
69
15
25
32
40
52
41
16
25
55
41
52
64
17
27
23
42
56
37
18
27
68
43
57
58
19
30
15
44
58
27
20
30
48
45
58
48
21
31
32
46
59
15
22
31
62
47
61
33
23
32
22
48
62
42
24
32
39
49
62
63
25
36
16
50
63
69
Tab. 4. Konfigurace problémů obchodního cestujícího TSP30 a TSP50
32
Obr. 6. Grafické znázornění pozic měst problémů obchodního cestujícího TSP30 a TSP50.
5.2
Volba nastavení parametrů PGA
Skutečně precizní prozkoumání vlivu migrace na průběh PGA vyžaduje obrovské množství provedených pokusů pro všechny možné kombinace hodnot parametrů PGA. Na tak rozsáhlé testování není v této práci místo. Musel jsem se omezit na jedno nastavení parametrů PGA a pro ně provést sérii testů. Pravděpodobnost mutace jsem se rozhodl nastavit nulovou Pmutace = 0 , protože mutace je vzhledem k migraci ve zvláštním postavení. Mutace i migrace mají pro kmen podobný význam – představují přísun nového genetického materiálu. Pokud chci tedy zkoumat migraci, je nutné omezit vlivy ostatních genetických operátorů, které by mohly mít podobný účinek. Jedině tak půjde určit, že za pozorované jevy je opravdu zodpovědná migrace. Na obrázku Obr. 7 je znázorněno porovnání běhů PGA bez mutace a s mutací. Je vidět, že zvláště pro větší migrační intervaly je mutace velice užitečná, ale jen těžko bychom její účinky odlišovali od účinků migrace. Pokud nebude u jednotlivých pokusů uvedeno jinak, parametry jsou nastaveny podle tabulky Tab. 5. V uvedené tabulce nejsou všechny parametry, které PGA ke své činnosti potřebuje. Volbě nastavení chybějících parametrů jsou věnovány následující odstavce.
33
Obr. 7. Porovnání vývoje PGA bez mutace (vlevo) a s mutací Pmutace = 0.005 (vpravo)
Parametr
Hodnota
Druh kmenů
Simple GA (v každé generaci se vytváří zcela nová populace)
Selekce
Reminder Stochastic Sampling
Křížení
F2, F101, F103, DF3, PDF: dvoubodové TSP30, TSP50: Edge Recombination
Pkřížení
1.0
Mutace
F2, F101, F103, DF3, PDF: Flip TSP30, TSP50: Inversion + Reciprocal Exchange
Pmutace
0.0
Elitismus
ANO
Škálování
Lineární
Doba vývoje
500 generací Tab. 5. Nastavení parametrů PGA
5.2.1
Volba velikosti populace
Velikost populace je hlavní faktor určující kvalitu řešení nalezeného pomocí GA po určitém počtu generací. Harik, Cantú-Paz, Goldberg a Miller [Harik1996] odvodili vztah pro určení vhodné velikosti populace, pokud ovšem předem známe optimum účelové funkce a stavební bloky. To ve svém důsledku znamená, že vztah je použitelný pouze pro známé testovací úlohy. Pro praktické úlohy by mohl posloužit maximálně jako vodítko. Rozhodl jsem se demonstrovat jeho použití na jedné z testovacích úloh, abych ukázal, že jeho aplikace není zcela triviální. Odvození předpokládá použití turnajové selekce, což v mém případě není splněno. Výsledek výpočtů je proto třeba brát pouze jako přibližný. Pro odvození vztahu byl použit následující model. 34
Model hazardního hráče (Gambler’s Ruin Model – GR model) Náhodné procházky jsou matematické nástroje, které se dají použít k predikci výsledku určitých stochastických procesů. Nejzákladnější náhodná procházka využívá „ukazovátko“, které se pohybuje v jednorozměrném prostoru doleva a doprava s určitými pravděpodobnostmi. Velikost kroku je konstantní a někdy je pohyb ukazovátka omezen bariérami umístěnými v některých bodech prostoru. Pro GR model se používá 1D náhodná procházka se dvěma absorbujícími bariérami, které zachytí ukazovátko, jakmile dosáhne některé z nich. Problém hazardního hráče je klasickým příkladem náhodné procházky s absorbujícími bariérami v bodech 0 (hráč ztratil všechen svůj kapitál) a n (hráč získal všechen kapitál svého soupeře). Na počátku hry je ukazovátko v bodě x0 = a , který představuje počáteční kapitál hráče. V každém kroku hry může hráč získat jednu jednotku na svém soupeři s pravděpodobností p , jeho soupeř ji naopak může vyhrát s pravděpodobností q = 1 − p . Cílem hráče je dostat se na bariéru x = n . Z literatury je známa pravděpodobnost, že hráč dosáhne svého cíle, jako x0
q 1 − p Pn = n q 1 − p
(5.1)
Tento model lze aplikovat na úlohu určení optimální velikosti populace n . Na jednotlivé kroky evoluce je třeba nahlížet jako na proces rozhodování mezi dvěma stavebními bloky. Pozice ukazovátka představuje počet stavebních bloků chromozomu, které zkonvergovaly ke správným alelám. Prostor je opět omezen dvěma bariérami x = 0 a x = n , které reprezentují konvergenci populace ke špatnému a správnému řešení. Počáteční pozice ukazovátka x0 představuje očekávaný počet kopií nejlepšího stavebního n bloku v náhodně inicializované populaci. Platí, že x0 = k , kde k je řád stavebního bloku, 2 p představuje pravděpodobnost správného rozhodnutí mezi dvěma stavebními bloky a q je pravděpodobnost špatného rozhodnutí. Tento model opouští představu generací v GA a předpokládá, že jednotlivá rozhodnutí mezi stavebními bloky jsou činěna postupně. Předpokládá se také, že je užita turnajová selekce (pro jiná selekční schémata je třeba model upravit). Z výrazu (5.1) lze odvodit velikost populace n . Musíme si uvědomit, že v našem případě bývá p > 1 − p a x0 je obvykle malé vzhledem k velikosti populace n . Pro vzrůstající hodnoty n se jmenovatel výrazu (5.1) blíží k 1 rychleji než čitatel. Za těchto n podmínek a substitucí za x0 = k a q = 1 − p můžeme výraz (5.1) zjednodušit na tvar 2 n
1 − p 2k Pn ≈ 1 − p Z (5.2) lze vyjádřit velikost populace n jako
35
(5.2)
n=
ln (1 − Pn ) 1− p ln p
(5.3)
1
2k
Kalibrace GR modelu Aby se dal vztah (5.3) použít pro odhad velikosti populace, lze postupovat v zásadě dvěma způsoby. Buď můžeme nalézt hodnoty proměnných p a k teoreticky a dosadit je do uvedeného modelu, nebo se dají přibližně určit empiricky po provedení několika pokusů. Postupoval jsem druhým způsobem. Všechny problémově závislé parametry modelu (5.2) lze sloučit do jediného parametru. Model pak lze popsat vztahem Pbb = 1 − y n ,
(5.4)
1
1− p . kde y = p Abych určil hodnotu parametru y , provedl jsem sérii experimentů pro různé velikosti populace s testovací funkcí 10xF2. Každý chromozom tady obsahuje 10 přirozených stavebních bloků F2. Parametr Pbb jsem měřil jako podíl dobrých stavebních bloků 2k
v chromozomu po konvergenci populace. Výsledky jsou uvedeny v tabulce Tab. 6 a jsou to průměrné hodnoty z několika běhů GA.
n Pbb
50
100
200
400
0.02
0.04
0.16
0.26
Tab. 6. Závislost kvality nalezeného řešení na velikosti populace
Z tabulky Tab. 6 je zřejmé, že bude třeba mnohem větší populace, pokud bychom požadovali kvalitnější řešení. Je třeba si také uvědomit, že uvedený způsob měření kvality chromozomů (podíl dobrých stavebních bloků) se značně liší od určování kvality pomocí účelové funkce. Chromozom, kterému dobře zkonvergovalo 9 stavebních bloků z 10 může mít ohodnocení mnohem horší než chromozom, ve kterém úplně nezkonvergoval ani jediný stavební blok. Nyní můžeme model (5.4) přizpůsobit změřeným datům z tabulky Tab. 6. Použil jsem metodu nejmenších čtverců (příkaz nlinfit systému MATLAB). Zjištěná hodnota parametru je y = 0.9993 . Porovnání změřených dat a hodnot vypočtených pomocí modelu je na obrázku Obr. 8. Z rovnice (5.4) lze vyjádřit velikost populace n jako n=
ln(1 − Pbb ) ln( y )
36
(5.5)
Volba velikosti populace Budu-li po GA požadovat řešení, ve kterých bude alespoň 8 z 10 stavebních bloků dobře zkonvergovaných ( Pbb = 0.8 ), mohu pro daný problém pomocí GR modelu alespoň přibližně určit potřebnou velikost populace jako
n0 =
ln(1 − 0.8) ≈ 2298 jedinců ln(0.9993)
Vývoj tak velké populace by ale trval neúnosně dlouho. Protože v následujících experimentech nejde ani tak o kvalitu výsledného nalezeného řešení, ale spíš o zjištění vlivu jednotlivých parametrů na trend vývoje, budu používat menší populaci o velikosti
n0 = 200 jedinců .
Obr. 8. Porovnání GR modelu a naměřených dat.
5.2.2
Volba ostatních parametrů
Zbývá určit několik parametrů, které jsou pro PGA a pro migraci zcela zásadní. Je to optimální stupeň propojení δ * , optimální počet kmenů r * a kritický počet epoch τ C . Cantú-Paz [Cantú-Paz1999c] odvodil pro tyto veličiny vztahy na základě minimalizace doby běhu PGA, která se dá spočítat jako TPGA = τ (g ⋅ n D ⋅ T f + δ ⋅ Tc )
37
(5.6)
Pro velikost kmene můžeme psát nD =
n0 r
(5.7)
Pro optimální stupeň propojení platí g ⋅ n0 ⋅ T f δ * = 2 ⋅ (τ C − 1) ⋅ Tc
2
3
(5.8)
Pro optimální počet kmenů platí r* = g ⋅
δ − 1 n0 ⋅ T f ⋅ Tc δ
(5.9)
Kritický počet epoch, který představuje omezení platnosti předešlých vztahů, se spočítá jako
τC =
r −1
δ
+1
(5.10)
Ve vztazích (5.6) až (5.10) mají jednotlivé symboly následující význam:
τ g
počet epoch vývoje PGA doba trvání epochy v generacích (zjistitelná experimentálně)
n0
celkový počet jedinců v populaci (součet velikostí kmenů)
nD
počet jedinců v kmenu
Tf
čas potřebný na ohodnocení jednoho jedince (experimentálně)
Tc
čas potřebný na přenos n mig jedinců z jednoho kmene do druhého (experimentálně)
δ
stupeň propojení topologie počet kmenů
r
Abychom vypočetli parametry n D , δ * , r * a τ C , měli bychom řešit soustavu čtyř nelineárních rovnic (5.7) až (5.10). Mezi těmito rovnicemi však existuje mnoho na první pohled zřejmých, ale i skrytých vazeb, a tato soustava není obecně algebraicky řešitelná. Postupoval jsem proto jinak. Uvedené rovnice jsou užitečnější, pokud některé z parametrů známe. V praxi velmi často existují fyzikální omezení, jako je např. počet dostupných procesorů, který určuje možný počet kmenů. Já jsem se rozhodl zvolit stupeň propojení topologie δ = 2 - každý kmen bude při migraci dostávat jedince od jiných dvou kmenů. Další výpočty jsou proto platné pro všechny sítě s tímto stupněm propojení (obousměrný prstenec, +1+2, +2+3, atd. – viz. Obr. 9). Zafixováním parametru δ se soustava zredukovala na soustavu tří rovnic a odstranily se některé závislosti mezi nimi. Tuto soustavu již lze řešit algebraicky.
38
Obr. 9. Příklady topologií se stupněm propojení 2. a) obousměrný prstenec, b) +1+2, c) +2+3
Ještě předtím je ale nutné prozkoumat parametr g . Jak jsem již uvedl, g představuje dobu trvání epochy neboli kolik generací kmeni trvá, než zkonverguje. Tato veličina ale silně závisí na velikosti kmene, kterou se teprve snažím zjistit. Je proto třeba sestavit model závislosti g na n D . Tento model by měl být co nejjednodušší, aby řešitelnost soustavy zůstala zachována. Proto jsem ho zvolil pouze ve tvaru
g = k ⋅ nD
(5.11)
Pro zjištění konstanty k jsem opět provedl sérii experimentů. Výsledky v tabulce Tab. 7 jsou opět průměrnými hodnotami z několika běhů. Velikost kmene n D Délka epochy g
50
100
200
400
131,1
231,9
397,9
759,5
Tab. 7. Závislost délky epochy na velikosti kmene.
Metodou nejmenších čtverců jsem zjistil hodnotu konstanty k = 1.9441 . Závislost g (n D ) má tedy tvar
g = 1.9441 ⋅ n D
(5.12)
Obr. 10 ukazuje porovnání změřených hodnot a hodnot generovaných modelem. Připomínám, že vztah (5.12) je platný pouze pro kmeny o velikosti menší než 400. Pro větší kmeny se výsledky mohou značně lišit od skutečnosti.
39
Obr. 10. Porovnání naměřených dat a hodnot modelu pro určení délky epochy
Nyní už mohu přistoupit k výpočtu zbývajících parametrů. Po dosazení rovnic (5.11) a (5.7) do rovnice (5.9) lze vyjádřit optimální počet kmenů jako 2
δ − 1 n0 ⋅ T f r = k⋅ ⋅ Tc δ *
3
(5.13)
Konstanty T f a Tc lze zjistit empiricky. Z výsledků svých pokusů jsem určil jejich hodnoty na T f ≅ 0.64 ms a Tc ≅ 1.5 ms . Všechny hodnoty potřebné pro výpočet jsou již známy a lze je dosadit do rovnice (5.13)
r * = 3 1.9441 ⋅
2 − 1 200 2 ⋅ 0.64 ⋅ = 21.34 ≅ 20 kmenů 1.5 2
Dosazením do rovnic (5.7) a (5.10) získáme i zbývající parametry nD =
τC =
r −1
δ
n0 200 = = 10 jedinců r 20
+1 =
20 − 1 + 1 = 14.43 ≅ 14 epoch 2
Protože jsem se rozhodl použít maximální migrační koeficient, počet migrujících jedinců jsem v experimentech nastavil na n 10 n mig = D = = 3.33 ≅ 3 jedinci δ +1 2 +1
40
Všechny uvedené parametry PGA jsou souhrnně uvedeny v tabulce Tab. 8. Podle těchto zvolených a vypočtených parametrů lze takto nastavený PGA zařadit do skupiny jemně dělených PGA. Stupeň propojení δ
Počet kmenů r
Velikost kmene n D
Migrační koeficient n mig
2
20
10
3
Tab. 8. Zvolené a vypočtené parametry PGA
Je třeba zdůraznit, že uvedený výpočet parametrů PGA je přibližně platný pro problém optimalizace funkce 10xF2. Přestože hodnoty parametrů tedy nemají žádný vztah k ostatním testovacím funkcím, rozhodl jsem se použít tyto parametry ve všech následujících experimentech. Obsahem této práce je zkoumání vlivů parametrů migrace na trend vývoje PGA, nikoli nalezení optimálního řešení konkrétních testovacích úloh, a chyba, které se zde dopouštím, není z tohoto hlediska důležitá. V následujících odstavcích jsou uvedeny experimenty, které mají prověřit správnost předpokládaného vlivu různých nastavení migrace na běh PGA, jak byly uvedeny v tabulce Tab. 1. Všechny jsou postupně ověřeny na funkci 10xF2.
5.3
Migrace synchronní vs. asynchronní, hromadná vs. individuální
Přesto, že „synchronnost“ a „hromadnost“ jsou různé atributy migrace, nejsou na sobě zcela nezávislé. Obě souvisejí s migračním kritériem. To, zda bude migrace synchronní nebo asynchronní, je ovlivněno přímo tvarem migračního kritéria. Naproti tomu to, zda migraci nazveme hromadnou, resp. individuální, závisí zase na způsobu spouštění migračního kritéria (zda bude brát v úvahu celou populaci PGA nebo jen subpopulace jednotlivých kmenů). Je zřejmé, že nemá smysl mluvit o synchronní individuální migraci (je-li migrace vyvolávána synchronně, pak je tak vyvolávána pro všechny kmeny najednou, tedy hromadně). Experimenty v tomto odstavci proto porovnávají tři různé druhy migrace: • Synchronní • Asynchronní hromadnou • Asynchronní individuální
Synchronní migrace Synchronní migrace ovlivňuje běh PGA v závislosti na tom, jaký zvolíme migrační interval. Vlivy řídké i často probíhající migrace byly diskutovány výše. Mezi oběma těmito krajními případy však existuje relativně rozsáhlá oblast nastavení migračního intervalu, ve které se chování PGA liší jen minimálně. Z grafů na obrázku Obr. 11 a Obr. 12 budeme jen těžko odečítat konkrétní hodnoty, jsou ale dostatečně názorné na to, abychom si utvořili představu, jaké chování vykazuje PGA pro celý rozsah možného nastavení migračního intervalu. Na obrázku Obr. 11 je znázorněn vývoj nejlepšího dosud nalezeného
41
řešení (BSF – best-so-far). Migrační interval byl nastaven v rozmezí od 1 generace až po izolované kmeny IK. Obr. 12 zobrazuje průběh směrodatné odchylky v populaci tvořené nejlepšími jedinci z každého kmene (master populace). Z obou zmíněných grafů lze odvodit následující:
•
•
•
Migrace probíhající každou generaci značně přispívá k předčasné konvergenci populace (směrodatná odchylka klesne na 0 a PGA není bez mutace schopen vyvinout lepší řešení). Z grafů je vidět, že již cca od 100. generace je populace zcela zkonvergovaná (nejen, že jednotlivé kmeny zkonvergovaly, ale zkonvergovaly všechny k témuž řešení – nulová směrodatná odchylka master populace). Při opačném extrému (izolované kmeny IK) jednotlivé kmeny rychle zkonvergují k navzájem různým řešením (velká směrodatná odchylka master populace). Protože je ale migrace zakázána, neexistuje způsob, jak by kmeny mohly vzájemně své výsledky zkombinovat. Nejlepších výsledků dosahuje PGA (pro problém 10xF2 a dané nastavení) při migračním intervalu cca 10-20 generací (fitness nalezeného řešení po 500 generacích je lepší než PGA našel pro migrační interval 1 a dokonce výrazně lepší než v případě izolovaných kmenů).
Tato pozorování potvrzují teoretické domněnky učiněné v článku 4.1.1. Navíc údaje o počtu přenesených jedinců za celý běh PGA významně hovoří ve prospěch méně časté migrace.
Migrační interval 1 Počet migrantů
10
60000 6000
20
30
40
50
100
200
IK
3000
1920
1440
1200
600
240
0
Tab. 9. Celkový počet migrantů v průběhu vývoje PGA v závislosti na migračním intervalu.
42
Obr. 11. Průběh BSF během vývoje PGA v závislosti na migračním intervalu.
Obr. 12. Průběh směrodatné odchylky v master-populaci
43
Obr. 13. Synchronní migrace: průběh BSF v závislosti na migračním intervalu
Obr. 14. Synchronní migrace: průběh směrodatné odchylky v závislosti na migračním intervalu
44
Asynchronní hromadná a individuální migrace Na obrázku Obr. 15 až Obr. 20 je znázorněno porovnání zbývajících dvou typů migrace – asynchronní hromadné a asynchronní individuální – pro migraci spouštěnou různými hodnotami prahu konvergence. Z obrázků Obr. 15 a Obr. 16 je vidět, že asynchronní individuální migrace dosahuje pro všechny testované hodnoty prahu kvalitnějších řešení, a to během významně menšího počtu generací. Na druhou stranu ale celá populace značně rychle konverguje (viz obrázky Obr. 17 a Obr. 18), takže PGA využívající individuální migraci nebude schopen (při absenci mutace) najít lepší řešení. Hromadná migrace naproti tomu udržuje v populaci vyšší různorodost, a proto je možné, že by takový PGA při dalším vývoji byl schopen nalézt lepší řešení. Obrázky Obr. 19 a Obr. 20 znázorňují vývoj celkového počet migrantů během evoluce PGA. Z tohoto hlediska by se mohla zdát individuální migrace značně horší než migrace hromadná, protože během vývoje PGA přenášela řádově 10x více jedinců. To je ale způsobeno rychlou konvergencí kmenů (které pak vyžadují migraci každou generaci) a nedokonalostí realizace migračního kritéria („Migruj, když kmen potřebuje.“). Lepší migrační kritérium by mělo spouštět migraci pouze tehdy, pokud nedošlo k úplné konvergenci všech kmenů PGA ke stejnému řešení („Migruj, když kmen potřebuje a když je naděje, že dostane odlišné jedince.“). Tento problém bude ale v praktických úlohách značně potlačen mutací, která jistou různorodost populace bude zajišťovat neustále. Tato pozorování opět odpovídají teoretickému předpokladu učiněnému v tabulce Tab. 1, že individuální migrace bude potřebovat kratší dobu (měřeno v generacích) k nalezení stejně kvalitního řešení než migrace hromadná. Porovnáme-li asynchronní individuální migraci s migrací synchronní, vidíme, že výsledkem obou (při nejlepším nastavení) bylo nalezení zhruba stejně kvalitního řešení (fitness BSF byla v obou případech cca 2.3). Individuální migrace ale vykazuje rychlejší konvergenci než synchronní migrace (synchronní migrace tedy lépe udržuje schopnost PGA vyvinout lepší řešení). Zamyslíme-li se ještě jednou nad tím, čím se vlastně synchronní a asynchronní individuální migrace liší, dojdeme k závěru, že jen v migračním kritériu, které určuje okamžiky, kdy se má migrace spouštět. Proč tedy vymýšlet nějaké složité kritérium založené na konvergenci populace, když pomocí jednoduchého kritéria užívaného v synchronní migraci lze nalézt stejně kvalitní řešení? Odpověď je jednoduchá: synchronní migrace využívá kritérium, které spouští výměnu jedinců v konstantních, předem daných intervalech bez ohledu na to, jaký problém PGA řeší. Naproti tomu u asynchronní migrace kritérium založené na konvergenci využívá jakousi dodatečnou znalost o řešeném problému – totiž znalost, jak dobře si PGA s daným problémem umí poradit, vyjádřenou jako rychlost konvergence. Podle této veličiny pak odvozuje okamžiky, kdy bude migrace spuštěna. PGA využívající takové migrační kritérium je tedy lépe přizpůsoben na řešení různých problémů.
45
Obr. 15. Asynchronní hromadná migrace: průběh BSF v závislosti na prahu konvergence
Obr. 16. Asynchronní individuální migrace: průběh BSF v závislosti na prahu konvergence
46
Obr. 17. Asynchronní hromadná migrace: průběh směrodatné odchylky v master-populaci
Obr. 18. Asynchronní individuální migrace: průběh směrodatné odchylky v master-populaci
47
Obr. 19. Asynchronní hromadná migrace: vývoj celkového počtu migrantů
Obr. 20. Asynchronní individuální migrace: vývoj celkového počtu migrantů
48
5.4
Statická vs. dynamická topologie
Migrační topologie bývá velice často realizována jako statická. Existují k tomu pádné důvody dané architekturou počítačových sítí či přímo architekturou paralelních procesorů. Nevidím ale důvod, proč by se PGA měly omezovat na lokální počítačové sítě. Je docela snadné si jednotlivé kmeny představit na počítačích rozmístěných v nejrůznějších místech světa. Činnost PGA pak nesmí být narušena tím, že počítač, na kterém sídlí některý z kmenů, bude po nějaký čas nedostupný, a tudíž neschopen přijímat, ale hlavně poskytovat migranty. V takovém případě je nutné od statických topologií upustit a přeorientovat se na topologie dynamické. V tomto odstavci jsou na testovací funkci 10xF2 porovnány následující druhy topologií: • Statická – obousměrný prstenec
• Dynamická – s náhodným výběrem zdrojového kmene • Dynamická – s výběrem založeným na vzdálenosti genotypu • Dynamická – s výběrem založeným na vzdálenosti fenotypu Dynamická topologie s náhodným výběrem kmene dosahuje mírně horších výsledků, než statická topologie (viz. obrázky Obr. 11 a Obr. 21). Rozdíly ale nejsou nijak dramatické a dají se vysvětlit tím, že při náhodném výběru kmenů vlivem stochastických jevů dochází k horšímu šíření genetických informací mezi jednotlivými kmeny. Tento závěr se dal očekávat a odpovídá tvrzení [Cantú-Paz1999c], že různé topologie se stejným stupněm propojení dosahují přibližně stejných výsledků. Dynamická topologie s výběrem zdrojového kmene založeným na vzdálenosti genotypů dosahuje výsledků srovnatelných se statickou topologií (pro větší migrační intervaly dokonce lepších). Zklamáním se mohou zdát výsledky dosahované topologií s výběrem zdrojového kmene na základě fenotypu. Pro testovací funkci 10xF2 vykazuje tento výběr velice špatné výsledky v porovnání se statickou topologií i s výběrem podle genotypu. Tyto výsledky se ale dají vysvětlit tvarem funkce F2. Vybíráme-li kmeny na základě maxima vzdálenosti, pak jsou migranti velice nekvalitní vzhledem k jedincům, které obsahuje cílový kmen. Proto jsou vlivem selekce v další generaci z kmene vyřazeni a neúčastní se dalšího vývoje. Tento jev by se možná dal omezit úpravou fitness jedinců vkládaných do cílové populace (viz. odstavec 4.4.3). Pro jiné účelové funkce by se také vůbec nemusel projevit. Obě tato tvrzení jsou však jen domněnky a zasloužila by si podrobnější výzkum. Větší úspěšnost topologie s výběrem na základě vzdálenosti genotypů se dá přisuzovat větší nezávislosti genotypické vzdálenosti a fitness jedince. V případě fenotypické vzdálenosti lze (pro funkci 10xF2) s velkou pravděpodobností říci, že čím větší je fenotypická vzdálenost vybraného kmene, tím horší jedinci budou přeneseni. O genotypické vzdálenosti nic takového neplatí; takový výběr tedy zachovává v populaci diverzitu a je u něj značná šance, že migranti budou dost kvalitní.
49
Obr. 21. Náhodný výběr zdrojového kmene: průběh BSF v závislosti na migračním intervalu
Obr. 22. Náhodný výběr zdrojového kmene: průběh směrodatné odchylky
50
Obr. 23. Výběr zdrojového kmene založený na vzdálenosti genotypu: průběh BSF
Obr. 24. Výběr zdrojového kmene založený na vzdálenosti genotypu: průběh směrodatné odchylky
51
Obr. 25. Výběr zdrojového kmene založený na vzdálenosti fenotypu: průběh BSF
Obr. 26. Výběr zdrojového kmene založený na vzdálenosti fenotypu: průběh směrodatné odchylky
52
5.5
Migrace jedinců vs. migrace schémat
Z obrázků Obr. 13, Obr. 14 a Obr. 27 až Obr. 32 je vidět, že PGA využívající migraci schémat nachází přibližně stejně kvalitní řešení, jako PGA využívající migraci jedinců (nezávisle na tom, jaký zvolíme práh pro tvorbu schématu). Rozdíl je ale v tom, že migrace schémat zajišťuje v celém průběhu vývoje PGA větší rozmanitost populace (čím vyšší práh pro tvorbu schématu, tím více udržuje rozmanitost populace) a že tedy omezuje předčasnou konvergenci. Z toho by se dalo usuzovat, že při migraci schémat dochází k „šetrnějším“ zásahům do cílové populace, která si tak uchovává větší množství svých vlastností, které měla před migrací. Z kvality dosažených výsledků se zdá, že při přenosu schémat opravdu dochází ke správné identifikaci kvalitních stavebních bloků zdrojové populace a k jejich zařazování do populace cílové. Tato pozorování opět odpovídají teoretickým předpokladům z tabulky Tab. 1.
5.6
Migrace bez úpravy ohodnocení vs. migrace s úpravou ohodnocení
Porovnáme-li kvalitu nalezeného řešení a směrodatnou odchylku master populace pro klasickou migraci (bez úpravy ohodnocení – viz. obrázky Obr. 13 a Obr. 14) a pro migraci s úpravou ohodnocení (obrázky Obr. 33 a Obr. 34), vidíme, že migrace s úpravou ohodnocení dosahuje výrazně lepších výsledků, než migrace bez úpravy ohodnocení. Přitom zůstává zachována přibližně stejná úroveň různorodosti populace. To potvrzuje předpoklady z tabulky Tab. 1 , že migranti, jimž je uměle zvýšeno ohodnocení, zasahují ve větší míře do vývoje cílového kmene.
53
Obr. 27. Migrace schémat, práh schématu 0.5: průběh BSF
Obr. 28. Migrace schémat, práh schématu 0.5: průběh směrodatné odchylky
54
Obr. 29. Migrace schémat, práh schématu 0.7: průběh BSF
Obr. 30. Migrace schémat, práh schématu 0.7: průběh směrodatné odchylky
55
Obr. 31. Migrace schémat, práh schématu 0.9: průběh BSF
Obr. 32. Migrace schémat, práh schématu 0.9: průběh směrodatné odchylky
56
Obr. 33. Migrace s úpravou ohodnocení jedinců: průběh BSF
Obr. 34. Migrace s úpravou ohodnocení jedinců: průběh směrodatné odchylky
57
5.7
Volba nové migrační strategie
V odstavcích 5.3 až 5.6 byly postupně ověřeny vlivy různých parametrů migrace na vývoj PGA. Tento odstavec je věnován vytvoření nové migrační strategie. Její parametry jsem zvolil na základě výsledků z předchozích odstavců a výsledků několika praktických testů. Nová migrační strategie má následující atributy:
• •
Migrace asynchronní, individuální
•
Migrace jedinců (migrace schémat dávala jen o málo lepší výsledky a tvorba schémat je časově náročnější, proto jsem se rozhodl užít migraci jedinců) Migrace s úpravou ohodnocení
•
5.8
Dynamická topologie s výběrem zdrojového kmene na základě genotypické vzdálenosti
Experimenty s referenčními funkcemi
V tomto odstavci jsou na všech 7 testovacích úlohách srovnány tři různé GA: • Jednoduchý GA
•
PGA s konvenčním operátorem migrace (synchronní hromadná migrace jedinců bez úpravy jejich ohodnocení se statickou topologií)
• PGA s nově navrženým operátorem migrace (viz. předchozí odstavec) Protože se jedná o testy na reálných úlohách a jde o účinnost PGA jako celku, rozhodl jsem se použít mutaci s pravděpodobností Pmutace = 0.002 . Otázkou také zůstává nastavení parametrů použitých při porovnání PGA s využitím konvenčního a nového operátoru migrace. Míru účinnosti migrace lze měřit jako kvalitu dosaženého řešení při přibližně stejném počtu migrantů během vývoje PGA. Rozhodl jsem se tedy postupovat tak, že jsem provedl pokusy s nově navrženým operátorem migrace, který měl nastavený práh konvergence na určitou hodnotu (tato hodnota není optimální). Následně jsem zjistil, kolik migrantů průměrně během vývoje PGA přenesl a podle této hodnoty jsem upravil nastavení migračního intervalu u konvenčně používaného operátoru migrace tak, aby výsledné hodnoty počtu migrantů byly přibližně stejné. Formálně zapsáno
MI SYNCH =
doba vývoje 500 60000 = = , N ASYNCH N ASYNCH N ASYNCH 20 ⋅ 2 ⋅ 3 r ⋅ δ ⋅ nmig
kde
MI SYNCH
je migrační interval pro konvenční operátor migrace,
N ASYNCH
je celkový počet migrantů za dobu vývoje PGA s novým operátorem migrace,
r
je počet kmenů (20),
δ
je stupeň propojení (DOC = 2),
n mig
je migrační koeficient (3).
58
5.8.1
Experimenty s funkcí 10xF2
Práh pro spuštění výměny jedinců u nového operátoru migrace jsem nastavil na 0.7. PGA s tímto novým operátorem migrace (dále ho budu označovat jako PGA-New) přenesl mezi svými kmeny průměrně 1696 jedinců. Pro výpočet migračního intervalu PGA s konvenčním operátorem migrace (dále jen PGA-Old) jsem dosadil do výše uvedeného vzorce a ekvivalentní migrační interval vychází na 35 generací. Připomínám, že optimum funkce 10xF2 je 0. Pro všechny následující experimenty (pro experimenty se všemi účelovými funkcemi) platí, že je obtížné srovnávat mezi sebou jednoduchý GA (SGA) a PGA. Na obrázku Obr. 35 je vidět, že SGA dosahuje výrazně horších výsledků, než oba PGA. To je způsobeno velice malou mírou mutace, která pro SGA představuje jediný zdroj nového genetického materiálu. Je tedy možné, že při vyšší míře mutace by SGA našel kvalitnější řešení. Při porovnávání směrodatné odchylky si musíme uvědomit, že pro SGA je vynášena směrodatná odchylka populace, zatímco pro oba PGA se zaznamenávala směrodatná odchylka master-populace (populace tvořené jedním nejlepším jedincem z každého kmene). Jedná se tedy o kvalitativně odlišné míry, směrodatná odchylka u SGA má spíše informativní charakter a nedá se se směrodatnými odchylkami obou PGA srovnávat.
Obr. 35. Účelová funkce 10xF2: průběh BSF
59
Obr. 36. Účelová funkce 10xF2: průběh směrodatné odchylky
Obr. 37. Účelová funkce 10xF2: průběh počtu migrantů
60
5.8.2
Experimenty s funkcí 10xF101
Funkce 10xF101 je značně složitější než 10xF2. Vzhledem k tvaru F101 bude mít mnohem víc jedinců ohodnocení bližší k optimu a populace se tak bude jevit více zkonvergovaná (připomínám, že jde o konvergenci ohodnocení). Práh konvergence pro migraci v PGA-New jsem proto volil vyšší (0.9), než v případě 10xF2. Ekvivalentní migrační interval pro PGA-Old byl stanoven na 32 generací. Funkci F101 jsem si z čistě praktických důvodů upravil tak, aby byla celá posunuta do kladných hodnot, přičtením konstanty 956. Optimum funkce 10xF101 je tedy cca 0.4.
Obr. 38. Účelová funkce 10xF101: průběh BSF
61
Obr. 39. Účelová funkce 10xF101: průběh směrodatné odchylky
Obr. 40. Účelová funkce 10xF101: průběh počtu migrantů
62
5.8.3
Experimenty s funkcí 10xF103
Funkce 10xF103 má přibližně stejné rozdělení hodnot fitness jako 10xF101. Práh konvergence pro migraci v PGA-New jsem proto volil stejný (0.9). Ekvivalentní migrační interval pro PGA-Old byl stanoven na 46 generací, což značí pomalejší konvergenci a tedy i větší obtížnost funkce. Optimum funkce 10xF103 je 0.
Obr. 41. Účelová funkce 10xF103: průběh BSF
Obr. 42. Účelová funkce 10xF103: průběh směrodatné odchylky
63
Obr. 43. Účelová funkce 10xF103: průběh počtu migrantů
5.8.4
Experimenty s funkcí 50xDF3
Podle několika experimentů jsem zjistil, že GA s funkcí 50xDF3 konverguje mnohem rychleji než v předchozích případech. Nastavil jsem tedy vyšší práh konvergence pro PGANew (0.98). Ekvivalentní migrační interval pro PGA-Old byl stanoven na 25 generací. Optimum funkce 50xDF3 je 1500.
Obr. 44. Účelová funkce 50xDF3: průběh BSF
64
Obr. 45. Účelová funkce 50xDF3: průběh směrodatné odchylky
Obr. 46. Účelová funkce 50xDF3: průběh počtu migrantů.
65
5.8.5
Experimenty s funkcí 50xPDF
Funkce 50xPDF je podobného typu jako funkce 50xDF3. Práh konvergence pro PGA-New jsem proto ponechal stejný (0.98). Ekvivalentní migrační interval pro PGA-Old byl stanoven na 9 generací. Optimum funkce 50xPDF je 500.
Obr. 47. Účelová funkce 50xPDF: průběh BSF
Obr. 48. Účelová funkce 50xPDF: průběh směrodatné odchylky
66
.
Obr. 49. Účelová funkce 50xPDF: průběh počtu migrantů
5.8.6
Experimenty s funkcí TSP30
Pro funkce TSP30 a TSP50 jsem se z praktických důvodů rozhodl omezit velikost populace snížením počtu kmenů na 10. Celkový počet jedinců v PGA je tedy 100. Vzorec pro výpočet ekvivalentního migračního intervalu pro PGA-Old je třeba upravit na vztah
MI SYNCH =
doba vývoje 500 30000 = = . N ASYNCH N ASYNCH N ASYNCH r ⋅ δ ⋅ nmig 10 ⋅ 2 ⋅ 3
Optimum funkce TSP30 je 423.741. Práh konvergence jsem nastavil na 0.98. Díky rychlé konvergenci je míra migrace u PGA-New v závěrečných fázích vysoká, celkový počet migrantů dosahuje průměrně hodnoty 11467, a ekvivalentní migrační interval pro PGAOld proto vychází 2 (migrace tedy bude probíhat velice často).
67
Obr. 50. Účelová funkce TSP30: průběh BSF
Obr. 51. Účelová funkce TSP30: průběh směrodatné odchylky
68
Obr. 52. Účelová funkce TSP30: průběh počtu migrantů
5.8.7
Experimenty s funkcí TSP50
Problém TSP50 je mnohem složitější než TSP30. Velikost stavového prostoru u TSP30 je dána výrazem 30!, u TSP50 je to už 50!. Tomu odpovídá i značně pomalejší konvergence PGA-New při stejném prahu 0.98. Průměrný celkový počet migrantů byl 1039, ekvivalentní migrační interval pro PGA-Old je 28. Optimum funkce TSP50 je 422.
Obr. 53. Účelová funkce TSP50: průběh BSF
69
Obr. 54. Účelová funkce TSP50: průběh směrodatné odchylky
Obr. 55. Účelová funkce TSP50: průběh počtu migrantů
70
5.8.8
Diskuse výsledků experimentů
Ve všech experimentech dosahuje PGA lepšího řešení než SGA, což není překvapivý závěr (vzhledem k minimální míře mutace). Z průběhů směrodatné odchylky je také vidět, že SGA špatně konverguje. V případě funkce 10xF103 dokonce směrodatná odchylka ohodnocení populace vzrůstá, což si vysvětluji tvarem této funkce. Při náhodné inicializaci bude většina jedinců ležet v „rovinaté“ oblasti funkčních hodnot. Během vývoje bude v této oblasti díky rekombinaci vznikat stále značné množství jedinců, na druhé straně se ale podaří vyvinout lepší řešení – a směrodatná odchylka populace tedy poroste. Nová migrační strategie si v porovnání s konvenčně používanou vede střídavě úspěšně. Obě dosahují přibližně shodných výsledků – v některých případech si lépe vede starý operátor migrace, v jiných zase nový. Experimenty ale prokázaly značnou citlivost nového operátoru migrace i na malou změnu parametrů, což by si zasluhovalo další studium. Zajímavé výsledky jsou vidět na průbězích vývoje počtu migrantů během evoluce PGA s novým operátorem migrace u problémů, jejichž jedinci jsou reprezentováni binárními řetězci (všechny úlohy kromě obou TSP). Přestože je použito stejné migrační kritérium, má průběh počtu migrantů pro funkce 10xF2, 10xF101 a 10xF103 tvar konkávní (což je překvapivé), zatímco pro funkce 50xDF3 a 50xPDF konvexní. Zajímavé je, že v případě prvních třech funkcí se jedná o minimalizaci a v případě zbylých dvou o maximalizaci. V současné době nejsem schopen uspokojivě odpovědět na otázku, zda se tu projevuje nějaká zákonitost, či zda je to jen náhoda. Mohu se jen domnívat, že důvodem tohoto jevu může být charakter optimalizovaných funkcí (tvar rozdělení hodnot fitness) nebo nedokonalost míry konvergence, která vykazuje odlišné vlastnosti pro minimalizaci a maximalizaci. Zajímavé by bylo provést experimenty s dokonalejší mírou konvergence nebo s mírou konvergence na základě genotypu chromozomu. Při řešení problému TSP30 se jevila lépe nová migrační strategie. Její úspěšnost byla ale způsobena konstantní vysokou mírou migrace konvenčního migračního operátoru, která zapříčinila rychlou (a také předčasnou) konvergenci PGA-Old. Ještě výraznější se zdá být efektivita PGA-New při optimalizaci složitějšího problému TSP50. Zde se však jedná spíše o opačný extrém – řídká migrace brání v šíření kvalitních řešení mezi kmeny PGA-Old. V závěru vývoje probíhá u PGA-New migrace častěji a ten je díky tomu schopen vyvinout kvalitnější řešení. Ze všech sledovaných úloh se dá také vypozorovat, že větší míra migrace způsobuje rychlejší konvergenci, což jen potvrzuje teoretické předpoklady. Pokud tedy po PGA požadujeme řešení rychle (a nezáleží nám tolik na jeho kvalitě), je třeba volit kritérium, které spouští migraci častěji na počátku vývoje. Takto nastavený PGA se dostává do oblasti blízké optimu rychleji než PGA s nižší mírou migrace, pak ovšem předčasně konverguje a jeho vývoj se zastaví. PGA s nižší mírou migrace potřebuje sice delší čas, aby se dostal na stejnou úroveň, jako PGA s častější migrací, má ale většinou ještě dostatek informací k tomu, aby vyvinul řešení kvalitnější. Tyto závěry se velice podobají pozorováním u jednoduchých GA (rychlá konvergence mívá za následek rychlé nalezení méně kvalitního řešení, pomalejší konvergence způsobuje nalezení lepšího řešení, ale za delší dobu).
71
6 Závěr V této sekci jsou shrnuty poznatky jednotlivých kapitol a jsou zde diskutovány problémy, které si zaslouží další pozornost. V kapitolách 1, 2 a 3 jsou shrnuty všeobecné poznatky o jednoduchých GA a o paralelních modelech a paralelních implementacích PGA. Kapitola 3 navíc poskytuje přehled základních možností paralelizace GA a rozdělení PGA do základních modelů. Je zde zmíněno i jedno z nejkontroverznějších témat týkajících se PGA - problém nadměrného urychlení. Kapitola 4 se už plně zaměřuje na hlavní téma této práce – na migrační strategie. Identifikuje základní vlastnosti migrační strategie (migrační kritérium, migrační koeficient, topologii a způsob přenosu migrantů). Jsou zde z teoretického hlediska diskutovány vlivy možných nastavení atributů migrace na běh PGA a v závěru kapitoly je sestavena migrační strategie, která by z teoretického hlediska měla poskytovat lepší výsledky než strategie konvenčně používaná. Kapitola 5 je už věnována praktickým testům migračních strategií na referenčních úlohách, které jsou definovány v úvodu kapitoly. Jsou zde uvedeny zvolené parametry experimentů, příklad výpočtu velikosti populace pomocí modelu hazardního hráče a příklad stanovení počtu kmenů, stupně propojení a migračního koeficientu na základě vztahů odvozených Cantú-Pazem. Jednotlivé vlastnosti identifikované v kapitole 4 jsou jedna po druhé otestovány na jedné z referenčních úloh (10xF2). Empirické výsledky těchto pokusů se zdají být v dobré shodě s předpokládanými účinky zvolených parametrů. Na základě těchto experimentů je vytvořena konkrétní nová migrační strategie, která se od teoreticky doporučené strategie (viz. závěr kapitoly 4) liší jen minimálně (zůstává u použití migrace jedinců). Účinnost tohoto nového migračního operátoru je porovnána na všech referenčních úlohách. Výsledky ukazují, že PGA s novým operátorem migrace dosahuje obdobných výsledků, jako PGA s konvenčním operátorem. Nový operátor migrace je ale mnohem lépe přizpůsoben k práci v nehomogenním prostředí (na Internetu, jako součást multiagentních systémů, …). Je třeba podotknout, že PGA s konvenčním operátorem migrace je schopný dosáhnout lepších výsledků (pro jiné hodnoty migračních intervalů), než jsou uvedeny 72
v této práci. Migrační interval byl upraven tak, aby PGA s oběma druhy migračních strategií dosáhly za dobu svého vývoje stejného počtu přenesených jedinců z důvodu smysluplného porovnání účinnosti migrace. Z toho nelze usuzovat, že PGA s novým migračním operátorem dosahuje (v „absolutním“ měřítku) horších výsledků než PGA s konvenční migrací. Je možné (a domnívám se, že i pravděpodobné), že nová migrační strategie vzhledem ke své citlivosti na nastavení parametrů může dosáhnout lepších výsledků, než jaké jsou uvedeny v této práci. Důkladné prozkoumání všech vlastností musí být ale předmětem mnohem rozsáhlejší a systematičtější studie. Chtěl bych podotknout, že míry kvality PGA používané v této práci zcela ignorují skutečnou časovou náročnost jednotlivých operací. „Čas“ je zde měřen pouze v generacích. Pokud ale migrace není spouštěna příliš často, lze se domnívat, že při vývoji kmenů bude časově dominovat ohodnocení jedinců a řazení jedinců v kmenech nad časovou náročností migrace – jinými slovy, že časová náročnost pomocných operací migrace (určení konvergence pro migrační kritérium, výběr kmene na základě vzdálenosti genotypů či fenotypů, tvorba schémat) bude zanedbatelná v porovnání s celkovou dobou, kterou si migrace vyžádá (navazování spojení, pomocné operace, vlastní přenos migrantů, rušení spojení). V experimentech je použita míra konvergence kmene počítaná na základě ohodnocení jedinců. Míra, kterou jsem užil, se v průběhu experimentů ukázala jako nedokonalá, proto by v dalším výzkumu stálo za námahu buď sestavit jinou, kvalitnější míru konvergence na základě ohodnocení nebo přejít na míru konvergence počítanou na základě genotypů, která je podle mého názoru mnohem dokonalejší, ale také časově náročnější. Zajímavé by mohlo být také využití kompozitního migračního kritéria, které by kombinovalo vlastnosti generačního a konvergenčního kritéria (migrační interval by v něm byl zdola omezen generačním kritériem). Tato práce ukázala, že jakkoli se nám může zdát operátor migrace triviální, je ve skutečnosti ovlivňován mnoha parametry, na jejichž nastavení je značně citlivý. Důkladnému zkoumání vlivu jednotlivých parametrů, časové náročnosti i výše zmíněným problémům bych se rád věnoval během svého doktorandského studia.
73
Poděkování Závěrem bych rád vyslovil několik upřímných poděkování. V první řadě chci poděkovat svým rodičům a celé své rodině. Děkuji vám za trpělivost, obětavost a shovívavost, kterou jste prokazovali během posledních měsíců v míře přímo nevídané, a za neutuchající podporu po celou dobu mého vzdělávání. Doufám, že vám to budu schopen někdy oplatit. Dále bych chtěl poděkovat vedoucímu své diplomové práce, ing. Jiřímu Kubalíkovi, za příjemnou spolupráci, za spoustu cenných námětů i praktických rad, za kritické připomínky i za přátelské povzbuzení ve chvílích, kdy jsem ztrácel optimismus. Nakonec (ale ne v poslední řadě) bych rád poděkoval všem svým přátelům za to, že jsem se v jejich společnosti dokázal vždy odpoutat od každodenních starostí a problémů. Všem vám ze srdce děkuji.
74
Reference [Belding1995]
Belding T. C. (1995). The Distributed Genetic Algorithm Revisited. In: Eschelman L. (Ed.), Proceedings of the Sixth International Conference on Genetic Algorithms (pp. 114-121). San Francisco, CA: Morgan Kaufmann.
[Bethke1976]
Bethke A. D. (1976). Comparison of Genetic Algorithms and Gradient-based Optimizers on Parallel Processors. Technical Report No. 197. Ann Arbor, MI: University of Michigan, Logic of Computers Group.
[Braun1990]
Braun H. C. (1990). On Solving Travelling Salesman Problems by Genetic Algorithms. In: Schwefel H.-P., Männer R. (Eds.), Parallel Problem Solving from Nature (pp. 129-133). Berlin: Springer-Verlag.
[Cantú-Paz1994]
Cantú-Paz E., Mejía-Olvera M. (1994). Experimental Results in Distributed Genetic Algorithm. In: International Symposiym on Applied Corporate Computing. (pp. 99-108). Monterrey, Mexico.
[Cantú-Paz1998]
Cantú-Paz E. (1998). A Survey of Parallel Genetic Algorithms. Technical Report (IlliGAL Report No. 98007). University of Illinois at Urbana-Champagne.
[Cantú-Paz1999a]
Cantú-Paz E. (1999). Topologies, Migration Rates, and Multi-Population Parallel Genetic Algorithms. Technical Report (IlliGAL Report No. 99007). University of Illinois at Urbana-Champagne.
[Cantú-Paz1999b]
Cantú-Paz E. (1999). Migration Policies, Selection Pressure, and Parallel Evolutionary Algorithms. Technical Report (IlliGAL Report No. 99015). University of Illinois at Urbana-Champagne.
[Cantú-Paz1999c]
Cantú-Paz E. (1999). Designing Efficient and Accurate Parallel Genetic Algorithms. PhD Dissertation. Also available as technical report (IlliGAL Report No. 99017). University of Illinois at Urbana-Champagne.
[Cohoon1991]
Cohoon J. P., Martin W. N., Richards D. S. (1991). A Multi-population Genetic Algorithm for Solving the K-partition Problem on Hypercubes. In: Below R. K., Booker L. B. (Eds.), Proceedings of the Fourth Internetional Conference on Genetic Algorithm (pp. 244-248). San Mateo, CA: Morgan Kaufmann.
[DeJong1975]
De Jong K. (1975): An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD Dissertation. Dept. Of Computer and Communication Sciences. University of Michigan. Ann Arbor.
[FlexGA1998]
FlexGA (1998): A MATLAB Library of GA components, Users’s Guide. Flexible Intelligence Group, L.L.C.
[Goldberg1989]
Goldberg D. E. (1989). Genetic Algorithms in Search, Optimisation, and Machine Learning. New York: Addison-Wesley.
[Goldberg1994]
Goldberg D. E. (1994). Genetic and Evolutionary Algorithms Come of Age. Communications of the ACM, 37(3), 113-119.
75
[Gordon1993]
Gordon V. S., Whitley D. (1993). Seriál and Parallel Genetic Algorithms as Function Optimizers. In: Forrest S. (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms (pp. 177-183). San Mateo, CA: Morgan Kaufman.
[Grefenstette1981] Grefenstette J. J. (1981): Parallel Adaptive Algorithms for Function Optimization. Technical report No. CS-81-19. Nashville, TN: Vanderbilt University, Computer Science Department. [Grosso1985]
Grosso P. B. (1985). Computer Simulations of Genetic Adaptations: Parallel Subcomponent Interaction in a Multilocus Model. Unpublished doctoral dissertation, University of Michigan. (University Microfilms No. 8520908).
[Harik1996]
Harik G., Cantú-Paz E., Goldberg D. E., Miller B. L. (1996): The Gambler’s Ruin Problem, Genetic Algorithms, and the Sizing of Populations. Technical Report (IlliGAL Report No. 96004). University of Illinois at Urbana-Champaign.
[Kubalík2000]
Kubalík J., Lažanský J. (2000): A New Genetic Operator Maintaining Population Diversity. In: AIP Conference Proceedings, CASYS 2000, Liege, Belgium, August 7 –12
[Lin1994]
Lin S.-C., Punch W., Goodman E. (1994). Coarse-grained Parallel Genetic Algorithms: Categorization and New Approach. In: Sixth IEEE Symposium on Parallel and Distributed Processing. Los Alamitos, CA: IEEE Computer Society Press.
[Mařík1993]
Mařík V., Štěpánková O., Lažanský J. a kol. (1993). Umělá inteligence (1). Academia, Praha, ISBN 80-200-0496-3
[Michalewicz1995] Michalewicz Z. (1995). Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, Berlin. [Tanese1987]
Tanese R. (1987). Parallel Genetic Algorithm for a Hypercube. In: Grefenstette J. J. (Ed.), Proceedings of the Second Internetional Conference on Genetic Algorithms (pp. 177-183). Hillsdale, NJ: Lawrence Erlbaum Associates.
[Wall1996]
Wall M. B. (1996). GAlib: A C++ Library of Genetic Algorithms Components, Documentation Revision B. Massachusetts Institute of Technology.
[Whitley1995]
Whitley D. (1995). Fundamental Principles of Deception in Genetic Search. In: Foundations of Genetic Algorithms, G. Rawlins ed., Morgan Kaufmann, pp. 221-241
[Whitley1996]
Whitley D., Mathias K., Rana S., Dzubera J. (1996). Evaluating Evolutionary Algorithms. Artificial Intelligence Volume 85, pp. 245-2761
Zdroje na Internetu [I-1]
A Library of Traveling Salesman and Related Problem Instances. ftp titan.rice.edu (ftp 128.42.1.30)
[I-2]
Knihovna GALib http://lancet.mit.edu/galib-2.4/GAlib.html
76
Příloha A: Popis prostředí pro experimenty Knihovna GAlib Jako základ pro experimentování s GA jsem si vybral knihovnu GAlib vytvořenou na MIT v Massachusetts, která je dostupná na Internetu (viz. [I-2]) a která pracuje i v mně blízkém vývojovém prostředí MS Visual C++ pod Windows 98. Jedná se o sadu komponentů pro genetické a evoluční algoritmy vytvořenou v jazyce C++. Tato knihovna mě doslova oslnila tím, jak vrchovatou měrou využívá všech konceptů typických pro OOP i specifických rysů jazyků C a C++. Dokumentaci a bližší specifikace této knihovny můžete nalézt buď v [Wall1996] nebo v [I-2]. Zde se zmíním jen o nejdůležitějších vlastnostech.
Charakteristika GAlibu Základním prvkem knihovny je třída GAGeneticAlgorithm, reprezentující vlastní GA. Tato třída obhospodařuje populaci jedinců, provádí její vývoj, udržuje statistiky o vývoji GA, atd. Populaci představuje třída GAPopulation. Ta se skládá ze seznamu jedinců představovaných třídou GAGenome, udržuje statistiky o současné populaci, umí řadit jedince podle objective score (ohodnocení jedince dané účelovou funkcí) i podle fitness value (hodnota objective score přepočítaná škálovací funkcí). Třída GAGenome je základní třídou pro všechny struktury, pomocí nichž chceme popsat formát řešení našeho konkrétního problému. Jinak řečeno, každý chromozom, který chceme v GA použít musí být potomkem třídy GAGenome. Každý objekt třídy GAGenome má také své vlastní způsoby, jak provést inicializaci, křížení, mutaci i ohodnocení. GAlib nabízí bohatou sadu vestavěných typů chromozomů, selekčních a škálovacích schémat i typů genetických algoritmů:
• •
•
•
Třídy odvozené z GAGeneticAlgorithm: jednoduchý GA (GASimpleGA), GA se stálým stavem (GASteadyStateGA) a inkrementální GA (GAIncrementalGA) Selekční schémata odvozená od GASelectionScheme: pořadová selekce (GARankSelector), ruletová sel. (GARouletteWheelSelection), turnajová sel. (GATournamentSelector), zbytkový stochastický výběr (GASRSSelector), deterministický výběr (GADSSelector), atd. Škálovací schémata odvozená od GAScalingScheme: bez škálování (GANoScaling), lineární škálování (GALinearScaling), GAPowerLawScaling, GASharing, GASigmaTruncationScaling Typy chromozomů odvozené od GAGenome: 1-D binární řetězec (GA1DBinaryString), 2-D a 3-D binární řetězce, seznam objektů binární chromozom s převodem na celá čísla (GAListGenome), (GABin2DecGenome), strom (GATreeGenome) a spoustu dalších
77
Použití GAlibu Řešit optimalizační problém pomocí GAlibu je velice snadné. Ve většině případů stačí pouze nastavit parametry, definovat účelovou funkci (tomu se nevyhneme) a spustit algoritmus. Typický program pak vypadá takto: float Objective(GAGenome&) { // definice účelové funkce } main() { GA1DBinaryStringGenome genome(length, Objective);// vytvoř genom GASimpleGA ga(genome);
// vytvoř GA
ga.populationSize(popsize);
// uprav velikost pop.
ga.nGenerations(ngens);
// nastav délku evoluce
ga.pMutation(pmut);
// pst. mutace
ga.pCrossover(pcross);
// pst. křížení
GASigmaTruncationScaling sts;
// vytvoř škálovací schéma
ga.scaling(sts);
// nastav ho do GA
ga.evolve();
// spusť GA
cout << ga.statistics() << endl;
// přečti si výsledky
}
Přizpůsobení GAlibu je také velice snadné. Stačí odvodit novou třídu a přepsat příslušné metody. Někdy nemusíte dělat ani to (třeba v případě metod pro inicializaci, křížení a mutaci) – stačí napsat jednu funkci a říci objektu genetického algoritmu, aby ji používal. Po celou dobu práce s GAlibem jsem nenarazil na věc, která by nešla jednoduchým způsobem upravit.
Chyby v GAlibu Při práci s touto knihovnou se mi podařilo odhalit několik nepřesností i vyložených chyb. Turnajová selekce nepoužívá náhodný výběr s jedinců, mezi nimiž uspořádá turnaj – místo toho s-krát spouští ruletovou selekci a teprve z těchto jedinců vybírá nejlepšího. Pořadová selekce zase nespouští ruletovou selekci nad pořadím jedinců uspořádaných podle fitness – místo toho pokaždé vybírá nejlepšího jedince. Velice závažnou chybu jsem odhalil v selekčním schématu Stochastic Reminder Sampling, kde se pro minimalizační problémy špatně počítá předpokládaný podíl jedince v populaci další generace. Chyba se neprojevila hned na místě, ale až při rušení objektu jako problém s přístupem k paměti. SRSSelection tedy nepracuje tak, jak má, ale není to na první pohled vidět, což je velice záludné. Protože jsem však tuto selekční metodu používal, chybu jsem samozřejmě opravil.
78
Nadstavba knihovny GAlib pro PGA Abych mohl provádět experimenty s paralelními modely GA, byl jsem nucen doplnit knihovnu GAlib o několik tříd, které dané experimenty umožňují. Předně je nutné si stanovit, čím pro nás bude představován kmen v PGA. Já jsem kmen definoval jako samostatný genetický algoritmus, který ale navíc musí být schopen požádat o migraci. Tak vznikla třída PGADeme, jejímž virtuálním předkem je GAGeneticAlgorithm: class PGADeme : public virtual GAGeneticAlgorithm { ... GABoolean NeedsToMigrate() const; ... }
Snadným způsobem pak vytvoříme kmeny, které se chovají jako jednoduchý GA, případně jako jiný typ GA, a to pomocí vícenásobné dědičnosti: class PGASimpleDeme : public PGADeme, public GASimpleGA { ... }
Jako vlastní paralelní genetický algoritmus jsem vytvořil třídu PGAParallelGA. Sama je potomkem GAGeneticAlgorithm (protože musí vykazovat chování genetického algoritmu, i když je vnitřně paralelizovaná) , která v sobě obsahuje seznam kmenů a metod pro práci s nimi. Další třídou, která je nutná pro práci PGA je třída migrační strategie PGAMigrator. Tato třída je odpovědná za migraci. Musí tedy vědět jestli je požadována migrace hromadná či individuální, musí umět vybrat zdrojový kmen podle určitého kritéria, vybrat (případně i vytvořit) migranty a vložit je určitým způsobem do cílového kmene. Její deklarace vypadá přibližně takto (tato třída je abstraktní a nelze ji tedy instanciovat): class PGADeme : public virtual GAGeneticAlgorithm { ... int Migrate(BOOL ForceMigration = FALSE); int MigrateToDeme(unsigned int target); virtual void SelectSourceDemes(unsigned int target); virtual void SelectMigrants(unsigned int source)=0; virtual void InsertMigsToDeme(unsigned int target)=0; ... }
Od
této
třídy
jsou odvozeny dvě třídy PGARegularMigrator a PGASchemaMigrator. První z nich reprezentuje migraci jedinců a druhá migraci schémat. Kromě těchto tříd jsou součástí nadstavby ještě další pomocné třídy, které zde ale nebudu popisovat (mj. statistiky pro PGA a sady parametrů pro PGA). Příklad jednoduchého programu využívajícího tyto třídy by mohl vypadat takto: 79
float Objective(GAGenome&) { // definice účelové funkce } main() { // vytvoř genom GA1DBinaryStringGenome genome(length, Objective); // vytvoř PGA s přednastavenými hodnotami parametrů PGAParallelGA pga(genome); // vytvoř migrační operátor PGARegularMigrator mig(pga); // řekni PGA, aby ho používal pga.migrator(mig); // uprav libovolné parametry... pga.nDemes(10);
// změň počet kmenů
pga.nMigrants(3);
// změň počet migrantů
... pga.evolve();
// spusť GA
cout << pga.pgastatistics() << endl;
// přečti si výsledky
}
Výsledný kód si zachovává jednoduchost použití ve stylu GAlibu.
Uživatelský komfort V rámci této diplomové práce jsem plánoval vytvoření aplikace GALab, která by umožňovala snadné a komfortní provádění nejrůznějších experimentů s GA a PGA, a to i po velkých sériích. To předpokládalo ukládání hodnot do databáze a vytvoření uživatelského rozhraní, v němž by se snadno experimenty nastavovaly, spouštěly, kontrolovaly a vyhodnocovaly. První část tohoto úkolu se mi splnit podařilo (ukládání do databáze), druhou zatím ne (experimenty je třeba nastavovat i spouštět přímo ze zdrojového kódu).
Záznam do databáze Vytvořil jsem relační databázi (GALab.mdb) v Microsoft Accessu, která v jedné skupině svých tabulek obsahuje seznam a popis schopností budoucího GALabu, v druhé skupině obsahuje prostor na uložení konfigurací problémů i experimetů a do třetí skupiny se ukládají data o průběhu jednotlivých experimentů. Model databáze je na následujícím obrázku.
80
Obr. 56. Struktura relační databáze GALab.
81
Příloha B: Zdrojový kód nadstavby knihovny GAlib pro PGA. Mnou vytvořené zdrojové kódy spolu s knihovnou GAlib se nacházejí na CD, které je vloženo na zadních deskách této práce.
82
