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

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 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ými[1] 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.

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].

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.

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 a . Ruletová selekce jim přiřadí pravděpodobnosti přežití a . Pořadová selekce je nejprve uspořádá podle velikosti , a nad tímto pořadím proběhne ruletová selekce. Výsledkem je tedy a . 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: (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).

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 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í P_mut je jejich hodnota změněna na opačnou. Průměrně je tedy změněna hodnota bitů, přičemž všechny mutace se mohou vyskytnout v 1 až n_mut 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í 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ů.

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 (mGA)

Jedná se o variantu GA s velice malou populací. Ukazuje se, že mGA se dostává do oblasti blízké optimu rychleji než SGA [FlexGA1998]. Oproti SGA používá mGA 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 mGA 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 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ů:

· 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í.

2.6.3 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.

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 2ⁿ ř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á 2^L-o(H) řetězců.

Definiční délka schématu d(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:

, (2.1)

kde jednotlivé symboly mají následující význam:

	počet řetězců v populaci, které pokrývá schéma H v čase t (v t-té generaci)
	fitness schématu (průměrné ohodnocení jedinců odpovídajících schématu)
	střední fitness populace
	pravděpodobnost křížení
	pravděpodobnost mutace
	definiční délka schématu
L	délka schématu
o(H)	řád schématu

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.

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.

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ů.

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 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.

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 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.

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 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 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.

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:

(4.1)

Pro minimalizační problémy:

(4.2)

	je hodnota konvergence v generaci g,
	je průměrné ohodnocení jedinců v populaci v generaci g,
	je minimální ohodnocení jedince v populaci v generaci g,
	je maximální ohodnocení jedince v populaci v generaci g.

kde

· 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:

(4.3)

Pro minimalizační problémy:

(4.4)

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é.

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 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:

	je migrační koeficient,
	je velikost kmene,
	je stupeň propojení topologie (DOC).

kde

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 v intervalu , kde k je počet možných alel daného genu. Pro binární řetězce je tedy přípustný interval .

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á 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).

Konvenčně používaný atribut	Atribut doporučený v této práci	Předpokládaný přínos
Synchronní migrace	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 jedinců	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.
Bez úpravy ohodnocení	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.

Tab. 1. Porovnání konvenčně používaných a nově navržených vlastností operátoru migrace.

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 F2[2] [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.

Název	Definice
F2
F101
F103

Tab. 2. Definice použitých testovacích funkcí dvou neznámých.

Název	Definiční obor x a y	Počet bitů x a y	Rozlišení v x a y	min(F)	arg(min(F))
F2		12	0.001	0.0
F101		10	1.0	-955.96
F103		10	0.19550343	0.0

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

Obr. 2. Průběh funkce F101(x, y) na intervalu

Obr. 3. Průběh funkce F103(x, y) na intervalu

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.

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

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 , 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.

Obr. 7. Porovnání vývoje PGA bez mutace (vlevo) a s mutací P_mutace = 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
P_křížení	1.0
Mutace	F2, F101, F103, DF3, PDF: Flip TSP30, TSP50: Inversion + Reciprocal Exchange
P_mutace	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.

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 (hráč ztratil všechen svůj kapitál) a (hráč získal všechen kapitál svého soupeře). Na počátku hry je ukazovátko v bodě , 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í , jeho soupeř ji naopak může vyhrát s pravděpodobností . Cílem hráče je dostat se na bariéru . Z literatury je známa pravděpodobnost, že hráč dosáhne svého cíle, jako

(5.1)

Tento model lze aplikovat na úlohu určení optimální velikosti populace . 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 a , které reprezentují konvergenci populace ke špatnému a správnému řešení. Počáteční pozice ukazovátka představuje očekávaný počet kopií nejlepšího stavebního bloku v náhodně inicializované populaci. Platí, že , kde je řád stavebního bloku, představuje pravděpodobnost správného rozhodnutí mezi dvěma stavebními bloky a 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 . Musíme si uvědomit, že v našem případě bývá a je obvykle malé vzhledem k velikosti populace . Pro vzrůstající hodnoty se jmenovatel výrazu (5.1) blíží k 1 rychleji než čitatel. Za těchto podmínek a substitucí za a můžeme výraz (5.1) zjednodušit na tvar

(5.2)

Z (5.2) lze vyjádřit velikost populace jako

(5.3)

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 a 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

, (5.4)

kde .

Abych určil hodnotu parametru , 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 jsem měřil jako podíl dobrých stavebních bloků 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.

	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 . 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 jako

(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 (), mohu pro daný problém pomocí GR modelu alespoň přibližně určit potřebnou velikost populace jako

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

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ů a kritický počet epoch . Cantú-Paz [Cantú-Paz1999c] odvodil pro tyto veličiny vztahy na základě minimalizace doby běhu PGA, která se dá spočítat jako

(5.6)

Pro velikost kmene můžeme psát

(5.7)

Pro optimální stupeň propojení platí

(5.8)

Pro optimální počet kmenů platí

(5.9)

Kritický počet epoch, který představuje omezení platnosti předešlých vztahů, se spočítá jako

(5.10)

Ve vztazích (5.6) až (5.10) mají jednotlivé symboly následující význam:

	počet epoch vývoje PGA
	doba trvání epochy v generacích (zjistitelná experimentálně)
	celkový počet jedinců v populaci (součet velikostí kmenů)
	počet jedinců v kmenu
	čas potřebný na ohodnocení jednoho jedince (experimentálně)
	čas potřebný na přenos jedinců z jednoho kmene do druhého (experimentálně)
	stupeň propojení topologie
	počet kmenů

Abychom vypočetli parametry , , a , 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 - 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.

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 . Jak jsem již uvedl, 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 na . Tento model by měl být co nejjednodušší, aby řešitelnost soustavy zůstala zachována. Proto jsem ho zvolil pouze ve tvaru

(5.11)

Pro zjištění konstanty 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	50	100	200	400
Délka epochy	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 . Závislost má tedy tvar

(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.

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

(5.13)

Konstanty a lze zjistit empiricky. Z výsledků svých pokusů jsem určil jejich hodnoty na a . Všechny hodnoty potřebné pro výpočet jsou již známy a lze je dosadit do rovnice (5.13)

Dosazením do rovnic (5.7) a (5.10) získáme i zbývající parametry

Protože jsem se rozhodl použít maximální migrační koeficient, počet migrujících jedinců jsem v experimentech nastavil na

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ů	Velikost kmene	Migrační koeficient
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 ř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	10	20	30	40	50	100	200	IK
Počet migrantů	60000	6000	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.

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

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

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ů.

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

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

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ů

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

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

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

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

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.

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

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

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

Obr. 33. Migrace s úpravou ohodnocení jedinců: průběh BSF

Obr. 34. Migrace s úpravou ohodnocení jedinců: průběh směrodatné odchylky

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í

· Dynamická topologie s výběrem zdrojového kmene na základě genotypické vzdálenosti

· 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 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í . 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

, kde

	je migrační interval pro konvenční operátor migrace,
	je celkový počet migrantů za dobu vývoje PGA s novým operátorem migrace,
	je počet kmenů (20),
	je stupeň propojení (DOC = 2),
	je migrační koeficient (3).

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

Obr. 36. Účelová funkce 10xF2: průběh směrodatné odchylky

Obr. 37. Účelová funkce 10xF2: průběh počtu migrantů

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

Obr. 39. Účelová funkce 10xF101: průběh směrodatné odchylky

Obr. 40. Účelová funkce 10xF101: průběh počtu migrantů

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

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 PGA-New (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

Obr. 45. Účelová funkce 50xDF3: průběh směrodatné odchylky

Obr. 46. Účelová funkce 50xDF3: průběh počtu migrantů.

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

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

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 PGA-Old proto vychází 2 (migrace tedy bude probíhat velice často).

Obr. 50. Účelová funkce TSP30: průběh BSF

Obr. 51. Účelová funkce TSP30: průběh směrodatné odchylky

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

Obr. 54. Účelová funkce TSP50: průběh směrodatné odchylky

Obr. 55. Účelová funkce TSP50: průběh počtu migrantů

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).

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 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.

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.

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.
[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

[1] 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.

[2] Při přepisování funkce F2 jsem udělal chybu. Skutečný tvar této funkce je . 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í.

	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

	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

	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