Semestrální práce

Paralelní genetické algoritmy

 

Petr Pošík, 5/18

20.2.2000

Katedra kybernetiky

Fakulta elektrotechnická

České vysoké učení technické Praha

xposik@rtime.felk.cvut.cz, posa@volny.cz

 

Úvod

GA byly úspěšně aplikovány na problémy z různých oblastí lidské činnosti. Obecně jsou schopné najít dobrá řešení úloh v přijatelně krátkém čase, ale pokud se aplikují na rozsáhlejší a obtížnější problémy, roste čas potřebný k nalezení dostatečně kvalitních řešení. To podnítilo různé pokusy, jak urychlit GA, a jedna z nejslibnějších možností je paralelní implementace.

Při použití termínu “paralelní genetický algoritmus” by se mělo rozlišovat mezi paralelními modely, jejich paralelními nebo sekvenčními implementacemi a mezi počítačovým hardwarem.

Modely

Model sekvenčního 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. Tento sekvenční GA je tradičním modelem 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í.

Implementace

Paralelní i sekvenční 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 pracovních stanic.

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.

Modely PGA

  1. Paralelizace globálního modelu (Global Parallelization)
    Algoritmus obhospodařuje jednu populaci jako u obyčejného sekvenčního GA. Paralelizace se týká ohodnocování jednotlivců v populaci a uplatňování genetických operátorů. Ohodnocování jednotlivých chromozomů zřejmě není závislé na ničem jiném, takže se dá velice snadno paralelizovat. U genetických operátorů se dá s jistou opatrností paralelizace také použít. 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.

  2. Hrubě dělené PGA (Coarse-Grained 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ů. Této výměně jedinců se říká migrace a je ovlivňována několika parametry. Hrubě dělené PGA zavádějí nové postupy v činnosti GA a jejich chování je odlišné od chování jednoduchých GA. 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 SGA, 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ší.

  3. Jemně dělené PGA (Fine-Grained PGA)
    Populace je v tomto modelu rozdělena do velkého počtu velmi malých subpopulací. Ideálním případem by bylo, kdyby ke každému dostupnému zpracovávacímu elementu (procesoru) byl přiřazen jediný chromozom. Tento model je vhodný pro masivně paralelní architektury počítačů, ale dá se implementovat na jakémkoli multiprocesoru. Stejně jako hrubě dělený PGA má odlišné chování než obyčejné GA. V globálním modelu probíhá selekce i reprodukce v rámci celé populace, zatímco v hrubě i jemně dělených PGA berou genetické operátory v úvahu jen jednotlivce v rámci kmene.

  4. Hybridní 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. 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.

Topologie

Při provádění migrace je třeba určit počet migrujících jedinců, zdrojovou a cílovou populaci. Přitom by bylo vhodné, aby všechny kmeny dostaly stejné množství “genetické informace” z ostatních kmenů. Vytvářejí se proto různé topologie jejich propojení (do kruhu, do sítě, do hyperkrychle, …).

Z hlediska analýzy činnosti PGA není ani tak důležité, odkud (ze kterého kmene) noví jednotlivci pocházejí, jde spíš o to, kolik nových jedinců je do populace zaneseno. Všechny přenosy jsou z tohoto pohledu ekvivalentní.

Samotná topologie (způsob propojení kmenů) je ale důležitá při analýze časové náročnosti PGA. Je totiž třeba vzít v úvahu časové náklady na komunikaci mezi populacemi. Je jasné, že z tohoto hlediska nelze považovat všechna možná propojení za stejná (přenos jedinců z populace B do populace A bude trvat jinou dobu než přenos z populace C).

Problém nadměrného urychlení (Superlinear Speedups)

Jedním z kontroverzních témat týkajících se PGA je právě problém nadměrného urychlení. 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 k více než N-násobnému zkrácení výpočetní doby, což je právě 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. Jediné 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 této teorie způsobena hlavně zvýšením selekčního tlaku, které má za následek migrace jedinců mezi populacemi. 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ů, nebo nesprávné určení velikosti populace, takže není zaručena konvergence ke stejně kvalitnímu řešení.

Doba převládnutí (Takeover Time)

Jako důkaz tvrzení, že migrace opravdu způsobuje nárust selekčního tlaku lze uvést jednoduchou analýzu činnosti PGA pomocí veličiny nazvané doba převládnutí.

Předpokládejme velmi zjednodušený populační model, který bere v úvahu jen dva typy jednotlivců: dobré a špatné. Dále předpokládejme, že v počáteční populaci je pouze jeden jediný dobrý jedinec, a že celý vývoj probíhá pouze díky operátoru selekce a během vývoje se neuplatňuje ani rekombinace ani mutace. Doba převládnutí je potom počet generací, po které musí takovýto GA běžet, než dobré řešení zaplní celou populaci.

Nechť označuje poměr počtu dobrých jedinců v populaci vzhledem k celkové velikosti populace v čase t a označuje poměr špatných jedinců v populaci. Pro tuto demonstraci použijeme jednoduchou turnajovou selekci s velikostí s (podobné výpočty lze provést i pro ostatní druhy selekce). Špatný jednotlivec přežije pouze tehdy, pokud jsou všechny chromozomy účastnící se turnaje špatné. Platí tedy

.

Protože Q=1-P, pro vývoj dobrých jedinců platí

.

Tuto rovnici rozšíříme o vliv migrace. Předpokládejme, že migrace probíhá každou generaci (což je horní hranice jejího uplatňování) a že probíhá po provedení selekce, takže její efekt lze popsat přidáním jednoho členu do poslední rovnice, který se bude lišit pro různé nahrazovací strategie.

Ze čtyř možných nahrazovacích strategií je nejjednodušší (a také nejčastěji používaná) ta, kde dobří jedinci (pocházející z jiných kmenů) nahrazují jedince špatné. V každé generaci se potom zvětší počet dobrých jedinců o , což je migrační tempo (počet jedinců, které do populace přijdou z jiných kmenů). Diferenční rovnice pro toto schéma potom vypadá následovně:

V dalším případě, kdy migrují dobří jednotlivci a nahrazují jedince náhodně vybrané, je zvýšení počtu dobrých jedinců rovno počtu nahrazených špatných jedinců po uplatnění selekce. Pravděpodobnost výběru špatného jedince v t+1. generaci je , a proto podíl špatných jedinců nahrazených dobrými činí . Diferenční rovnice pro tento případ pak vypadá takto:

Pro popis případu, kdy náhodně vybraní jedinci nahrazují špatné, můžeme použít podobný postup. Tentokrát ale musíme spočítat, kolik jedinců přicházejících z ostatních kmenů je dobrých. Protože jedinci, kteří budou migrovat jsou vybíráni náhodně, je podíl dobrých migrujících jedinců stejný jako podíl dobrých jedinců v celé populaci, tedy . Výsledná rovnice bude mít tedy tvar

Pokud náhodně vybraní jedinci z jiných kmenů nahrazují náhodně vybrané jedince tohoto kmene, což je poslední nahrazovací strategie, dá se předpokládat, že podíl dobrých jednotlivců v populaci se měnit nebude, takže tato strategie nemá vliv na celkovou dobu převládnutí. GA s jedinou populací by konvergoval stejnou rychlostí jako PGA používající tuto migrační politiku.

Pro nalezení dob převládnutí pro čtyři uvedené migrační politiky jednoduše iterujeme odvozené diferenční rovnice, dokud nedosáhne nebo nepřesáhne 1. Počáteční podmínka iterací je (jediný dobrý jedinec v populaci).

Na obrázku 1 jsou zobrazeny doby převládnutí pro kmeny o velikosti n=10000 jedinců s párovou turnajovou selekcí (s=2). Je vidět, že se zvyšujícím se migračním tempem se zvyšuje i rychlost konvergence a že nejrychlejší konvergence dosahuje ta migrační politika, ve které dobří jedinci nahrazují špatné.

Je třeba říct, že zvýšení selekčního tlaku nezpůsobuje vlastně samotná migrace, ale spíše nahrazovací strategie, které jsou úzce spjaty s jednotlivými migračními politikami.

Tato jednoduchá ukázka demonstruje značný rozdíl mezi jednotlivými migračními politikami a dokazuje, že migrační politika je jedním z důležitých faktorů, které musejí být brány v úvahu při návrhu PGA. Podobných výsledků lze dosáhnout i při použití jiných metod odhadu doby konvergence populace u PGA. Tyto metody si nekladou tolik omezení a jejich předpoklady jsou mnohem realističtější než v tomto případě. A přesto, že předpovědi učiněné pomocí těchto metod jsou přesnější, kvalitativně se moc neliší od odhadů učiněných na základě doby převládnutí.

Obr. 1 Doby převládnutí různých migračních politik v závislosti na migračním tempu

Závěr a zaměření dalšího úsilí

V celé teorii o GA chybí něco (funkce, veličina, …), čím by se daly jednotlivé modely a implementace GA a PGA porovnat ohledně kvality a rychlosti nalezení řešení. Něco, co by člověka opravňovalo vyslovit např. větu: “Jednoduchý GA s X jedinci v populaci s pravděpodobností křížení Y a s pravděpodobností mutace Z při použití ruletové selekce bude mít stejné průměrné vlastnosti jako paralelní genetický algoritmus obhospodařující A kmenů o B jedincích s migrační politikou C.” Vhodným kandidátem na takovouto veličinu se ukazuje být selekční tlak. Bohužel ho však neumíme zatím spočítat pro všechny druhy GA, takže není zatím obecně použitelný. Metody výpočtu selekčního tlaku jsou v současnosti předmětem velkého úsilí mnoha vědců.

V další práci bych se rád věnoval vývoji určitého typu optimálního operátoru migrace. V analýzách PGA i v různých implementacích se migrace objevuje dost často po každé generaci, což je podle mého názoru zbytečné. Migrace probíhající každou generaci může výrazně zvýšit čas potřebný pro komunikaci mezi jednotlivými procesory nebo pracovními stanicemi. Navíc ve většině případů nebudou migrující jedinci moc odlišní od těch, kteří migrovali minulou generaci, takže neponesou významné množství nové informace. Jak ale určit vhodný okamžik pro migraci?

Jednou z možností je najít nějakou metodu pro určení optimálního intervalu (počtu generací), po kterém by migrace probíhala. Tento způsob je z jistého hlediska jednodušší, protože migrace by pak probíhala jednorázově, synchronně a bez problémů. Na druhé straně by se ale jednotlivé kmeny mohly nacházet v různém stádiu připravenosti k migraci, tzn. že z hlediska jednotlivých kmenů by k migraci nemuselo docházet v optimálním okamžiku.

Jiným možným přístupem by bylo nechat samotné kmeny rozhodnout o tom, kdy je pro ně vhodné migraci provést. Jako měřítko optimality by bylo možné zvolit například konvergenci populace – pokud by nedošlo k vylepšení nejlepšího jedince v populaci po určitý počet generací, kmen by se rozhodl, že si vymění některé jedince s jiným kmenem zvoleným podle určité metody. Tento přístup zároveň ale odstraňuje pevnou topologii propojení kmenů, protože výběr populací, mezi nimiž by se výměna jedinců uskutečňovala by byl do značné míry náhodný.

Další obměnou předešlého principu by bylo zavedení jakési centrální vyrovnávací paměti migrujících jedinců. Topologie propojení by se potom přeměnila na hvězdicovité schéma, v jehož středu by byla centrální paměť. Když by kmen cítil potřebu výměny jedinců, prostě by své jedince odložil do centrální paměti a zároveň by si z ní odebral jiné jedince, které tam vložily v minulé době jiné kmeny. Zajímavé by mohlo být např. porovnání, zda by se významně lišily vlastnosti takového PGA, kdyby měla centrální paměť podobu fronty a podobu zásobníku. Tento model s sebou nese ale i problém, co dělat, když v centrální paměti nejsou žádní jedinci, kterými by mohl kmen osvěžit svůj genetický materiál.

Všechny tyto metody si ale vyžadují podrobnější rozbor a provedení mnoha experimentů.