České vysoké učení technické v Praze Fakulta elektrotechnická
Diplomová práce
Přepínání metaheuristik Aleš Kučík
Vedoucí práce: Ing. Jan Koutník, Ph.D. Studijní program: Elektrotechnika a informatika, dobíhající, Magisterský Obor: Výpočetní technika květen 2009
ii
Poděkování Rád bych poděkoval vedoucímu diplomové práce Ing. Janu Koutníkovi, Ph.D. za odborné vedení, podněty a připomínky. Děkuji všem lidem, kteří mě podporovali během studia.
iii
iv
Prohlášení Prohlašuji, že jsem svou diplomovu práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon). V Mladých Bukách dne 20.5.2009
…..............................
v
vi
Abstract The work examines proposal of metaheuristics switching technique for optimalization problems. There are implemented selected metaheuristics and metaheuristic switching algorithm – simulated annealing, genetic algorithm and ant colony optimalization. Performance of algorithms is tested on travelling salesman problem.
Abstrakt Práce zkoumá možnost využití metody přepínání metaheuristik k řešení optimalizačních úloh. Ve své práci implementuji vybrané metaheuristiky a samotný alg. přepínání – simulované ochlazování, genetický algoritmus a algoritmus optimalizace mravenčí kolonie . Výkonost jednotlivých algoritmů je testována na problému obchodního cestujícího.
vii
viii
Obsah 1 Úvod........................................................................................................................................1 1.1 Význam metaheuristik.....................................................................................................1 1.2 Cíl práce..........................................................................................................................1 2 Analýza a návrh implementace metaheuristik.........................................................................2 2.1 Simulované ochlazování .................................................................................................2 2.2 Genetický algoritmus (GA).............................................................................................4 2.3 Optimalizace mravenčí kolonie (ACO)...........................................................................5 2.4 Algoritmus přepínání metaheuristik................................................................................6 2.4.1 Požadované vlastnosti..............................................................................................6 2.4.2 Návrh implementace................................................................................................6 2.4.2.1 SA....................................................................................................................7 2.4.2.2 ACO.................................................................................................................7 2.4.2.3 GA....................................................................................................................7 3 Implementace .........................................................................................................................8 3.1 Implementace metaheurisik.............................................................................................8 3.1.1 Implementace ACO.................................................................................................8 3.1.2 Implementace SA....................................................................................................9 3.1.3 Implementace GA....................................................................................................9 3.1.4 Přepínaná metaheuristika.......................................................................................10 3.2 Implementace TSP........................................................................................................10 4 Testování...............................................................................................................................11 4.1 Časové složitosti metaheuristik.....................................................................................11 4.1.1 Časová složitost ACO............................................................................................11 4.1.2 Časová složitost SA...............................................................................................11 4.1.3 Časová složitost GA..............................................................................................12 4.2 Návrh testů....................................................................................................................12 4.2.1 Definice testů.........................................................................................................13 4.2.1.1 Parametry SA.................................................................................................14 4.2.1.2 Parametry GA................................................................................................15 4.2.1.3 Parametry ACO..............................................................................................15 4.2.1.4 Ukázka nastavení testů...................................................................................15 4.3 Výsledky testů...............................................................................................................17 5 Závěr.....................................................................................................................................26 6 Literatura...............................................................................................................................28 7 Odkazy..................................................................................................................................28
ix
x
1 Úvod
1.1 Význam metaheuristik V dnešní době jsme svědky rychlého růstu výpočetního výkonu, jak běžných osobních počítačů tak i specializovaných výpočetních center. Přesto zde existuje skupina problémů, u kterých není dosud znám algoritmus řešící úlohu v rozumném čase nebo za rozumnou cenu (cenu za výpočetní výkon). Do této kategorie spadají především tzv. NP problémy. Jedná se o skupinu úloh u nichž není znám algoritmus řešící úlohu v polynomiálním čase. Jsou to například různé optimalizační kombinatorické problémy (obarvení grafu, obchodní cestující, rešitelnost booleovských formulí). Protože jsou tyto problémy ryze praktické (vrtání děr v desce plošných spojů, rozvržení jízd v autodopravě), je důležité hledat i jiné praktičtejší způsoby řešení. U optimalizačních úloh se snažíme nalézt takovou konfiguraci proměnných, abychom dosáhli minimalizace/maximalizace optimalizačního kritéria (cenová funkce). Pokud se spokojíme jen s dostatečně „dobrým“ řešením, můžeme použít metaheuristik. Metaheuristika je obecná metoda prohledávání stavového prostoru. Metaheuristika kombinuje dané procedury, ve snaze získat mnohem efektivnější algoritmus. Hlavním problémem metaheuristik je možnost uváznutí v lokálních extrémech. V tomto případě metaheuristika není schopná nalézt globální optimum. Obecně lze říci, že některé metaheuristiky jsou v řešení dané úlohy úspěšnější než jiné.
1.2 Cíl práce Cílem této práce je návrh a implementace sekvenční kombinace několika vybraných metaheuristik a konečné porovnání výkonnosti algoritmu. V této práci bych především chtěl ověřit možnost zlepšení algoritmů jejich vhodnou kombinací. Konkrétní úkoly jsou: • • • •
Implementace vybraných metaheuristik – mravenčí kolonie (ACO), simulované ochlazování (SA) a genetický algoritmus (GA). Návrh a implementace algoritmu pro přepínání mezi metaheuristikami. Implementace algoritmů pro testovací úlohu – obchodní cestující (TSP). Měření výkonnosti algoritmů.
1
2 Analýza a návrh implementace metaheuristik
2.1 Simulované ochlazování Simulované ochlazování je technika pro globální optimalizaci. Jedná se o iterativní algoritmus, kdy se s časem postupně vylepšuje aktuální řešení. Strategie procházení stavového prostoru řadí tuto techniku mezi lokální prohledávací metody - jako další možný stav se zkoumá některý z bezprostředních sousedů (sousednost stavů zde závisí na implementaci funkce pro generování nového stavu). Metoda byla poprvé popsána v práci Optimalization by Simulated Annealing [3] . Myšlenka SA je založena na technice řízeného ochlazování slitiny. Na počátku je slitina zahřátá na vysokou teplotu, kdy jednotlivé atomy mají dostatek energie k volnému pohybu a mohou se tak dostat na pozice s vyšší energií. Pomalé ochlazování poskytuje dostatek času k optimálnějšímu rozmístění atomů - minimalizaci potenciální energie. Algoritmus analogicky zabraňuje předčasnému uváznutí v lokálním minimu tím, že je dočasně umožněno přijmout i horší řešení než aktuální. Pravděpodobnost přijmutí horšího řešení s časem postupně klesá. Algoritmus končí po splnění ukončovací podmínky.
1. t = t0 2. s = init() 3. e = energy(s) 4. while(t>tN) 5. while(not equilibrium) 6. snew = neighbour(s) 7. enew = energy(snew) 8. 9. if((enew<e) or (P(e, enew, t)>rand())) 10. e = enew 11. s = snew 12. t = cooling(t) Na začátku algoritmus inicializuje počáteční teplotu, vygeneruje a ohodnotí počáteční stav (1-3). Následuje hlavní smyčka algoritmu, která skončí po splnění ukončovací podmínky, typicky pokud aktualní teplota klesne pod dané minimum (4). Podnínka pro dosažení teplotního equilibria umožňuje lépe řídit ochlazovací proces (5). Obvykle se jedná o nějaký daný počet iterací nebo počet přijatých zhoršujících stavů. Uvnitř smyček se generují nové zkoumané stavy (6-7), které jsou porovnávány s aktuálním stavem. Nové řešení je přijato pokud je jeho energie nižší. Je možné přijmou i horší řešení s pravděpodobností P(e,enew,t) (9). Po dosažení equilibria se sníží teplota ochlazovací funkcí (12).
2
Pro použití metaheuristiky simulovaného ochlazovaní je potřeba zvolit reprezentaci stavu a implementovat jednotlive funkce. • • • •
•
init() - generuje nějaké náhodné počáteční řešení. energy(s) - spočítá energii pro daný stav (platí pravidlo, čím menší energie tím lepší řešení). neighbour(s) – generuje nový stav na základě aktuálního stavu P(e,enew,t) - pravděpodobnostní funkce. Obecně lze zvolit jakoukoli funkci, kde s klesající teplotou t klesá i pravděpodobnost přijetí nového horšího stavu e=e−e new0 a zároveň klesá i s klesající e . Obvykle se používá vztah e−e new P e , e new , t=exp Tuto funkci také poprvé použil S. Kirkpatrick ve své t práci. Pravděpodobnostní funkce je založena na statistickém rozložení Maxwel-Bolzmanovy fce – popisující statistické rozložení energií částic při dané teplotě. cooling(t)- funkce definující průběh ochlazování. Lze použít jakoukoli klesající funkci. Často se volí exponenciální t n1=a∗t n nebo lineární funkce t n1=at n .
Velice důležitá je volba parametrů t 0 , t N , a , kde a je parametr ochlazovací funkce. • Společně parametry určují kolik proběhne iterací vnitřku cyklu (počet zkoumaných stavů). Je důležité parametry zvolit tak, aby proběhl dostatečný počet iterací a řešení stihlo konvergovat k optimu. t 0 - je počáteční teplota. Pokud je zvolena příliš vysoká, prohledávání zbytečně • probíhá dlohou dobu pouze náhodně. Napak příliš nízká teplota může způsobit předčasné uváznutí v lokálním minimu. t N - je koncová teplota. Pokud je zvolena příliš vysoká, řešení nestihne • konvergovat k optimu. Pokud je hodnota příliš nízká, hrozí zbytečné prohledávání okolí minima. Pro volbu parametrů neexistuje žádné obecné pravidlo a je potřeba zvolit parametry na základě předchozích testů. Špatná volba parametrů může způsobit neuspokojivé výsledky metaheuristiky.
3
2.2 Genetický algoritmus (GA) Genetické algoritmy patří do širší rodiny evolučních algoritmů. Jsou inspirovány evolučními mechanismy v přírodě, jako jsou selekce a reprodukce. Selekční tlak zlepšuje řešení tím, že pro reprodukci jsou vybráni jen nejvhodnější kandidáti z hlediska ohodnocení fitness funkcí. Reprodukce vytváří nová řešení z vybraných jedinců. 1. init(population) 2. while(not finished) 3.
parents = selection(population)
4.
newGeneration = breed(parents)
5.
population = merge(population, newGeneration)
Nejprve je inicializována populace (1). Následuje běh hlavního cyklu dokud není splněna ukončovací podmínka, typicky je dán počet iterací. V havním cyklu jsou selekčním operátorem vybráni rodiče pro nové potomky (3). Selekčních algoritmů existuje velké množství. Jsou to například: •
rulet rule – pravděpodobnost volby jednice je dána vztahem
p i=
fitnessi N
∑ fitness j j
•
rank – pravděpodobnost volby jedince je dána podobným vztahem jeko u rulet rule s tím rozdílem, že jedinec není hodnocen na základě fitness funkce, ale na pořadí mezi rank i p i= N ostatními jedinci (pořadí je určeno fitness funkcí). , kde funkce ∑ rank j j
rank() vrací pro nejlepšího jedince N a pro nejhoršího 1 (cekový počet jedinců je N). Nová generace se vytváří z rodičů operátory křížení (crossover) a mutace (mutation) (5). Jejich implementace závisí na konkrétním problému a jakým způsobem je implementován chromosom, který charakterizuje jedince. Nakonec hlavního cyklu je potřeba provést spojení nové generace s populací (5). Někdy se nahrazuje celá populace novou generací, v jiných případech se nahrazují pouze nejslabší jedinci.
4
2.3 Optimalizace mravenčí kolonie (ACO) Algoritmus mravenčí kolonie patří do skupiny algoritmů tzv. swarm intelligence (kolektivní inteligence, inteligence hejna). Jedná se o algoritmy, kde skupina agentů pracuje na základě vzájemné interakce a interakci s prostředím. Přestože se tito agenti řídí jednoduchými pravidly v globálním měřítku dochází ke vzniku složitého chování. ACO se inspiruje reálným chováním mravenců v přírodě. Tuto metodu poprvé navrhl ve své doktorandské práci M. Dorigo [5] . V ACO jsou agenty mravenci, kteří budují nové cesty na základě feromonových značek (intrakce mezi agenty) a na základě informace o prostředí. 1. init() 2. while(not finished) 3. build_solutions() 4. deposit_pheromone() 5. update_pheromone() Nejprve je potřeba inicializovat matici feromonů na nějakou nenulovou hodnotu (1). Poté běží hlavní cyklus dokud není splněna podmínka pro ukončení. V hlavním cyklu nejdříve jednotliví mravenci vybudují svá řešení. Mravenec na začátku náhodně vybere jeden uzel. Potom náhodně volí přes jakou hranu se přesune na sousední uzel. Pravděpodobnost, že zvolí danou hranu, je dána vztahem: p i , j= • • •
i , j ∗i , j , kde ∑ i , j ∗i , j
i , j - je hodnota feromonu na hraně i,j i , j - je ohodnocení vhodnosti pro hranu i,j , - koeficienty určující významnost daných parametrů ve vztahu
Po vybudování řešení je vybráno jedno nejlepší a na jeho základě mravenec označkuje feromonem novou cestu (4), zpravidla má hodnota feromonu funkční vztah s kvalitou řešení. Vtomto bodě se jednotlivé implementace ACO liší. V některých variantách označují svoji trasu všichni mravenci. Na závěr cyklu je provedena aktualizace hodnoty feromonu. Hodnota feromonu je upravena vztahem: i , j =∗i , j i , j , kde • •
- je koeficient odpařování, kterým se sníží hodnota feromonu na hraně i,j i , j - je nový přírůstek feromonu, který přidal mravenec během posleního značení
5
2.4 Algoritmus přepínání metaheuristik 2.4.1 Požadované vlastnosti Hlavním požadavkem na algoritmus pro přepínání metaheuristik je zachování maxima informací z dosavadního hledání při přechodu mezi jednotlivými algoritmy. Tento požadavek je důležitým předpokladem pro získání kvalitativně lepšího řešení než při pouhém samostatném spouštění jednotlivých metaheuristik. Je potřeba vyřešit jakým způsobem zacházet s informacemi o dosavadním řešením v rámci algoritmu přepínání a jakým způsobem inicializovat jednotlivé meteheuristiky před jejich spuštěním, tak aby mohly využít dosavadních řešení.
2.4.2 Návrh implementace Jako nejvhodnější pro splnění požadavků se nabízí implementace ve formě evolučního algoritmu. Základní charakteristikou evolučních algoritmů je udržování populace, selekce, změna na základě vybraných jedinců a nahrazení předchozí populace novou. Schéma navrhovaného algoritmu: 1. init(G) 2. evaluate(G) 3. while(!finished) 4. S = select(G) 5. M = metaheuristick(S) 6. G = merge(G, M)
Počáteční inicializace populace jedinců (1). Ohodnocení jedinců tak, aby bylo možné na základě ohodocení volit vhodné kandidáty při selekci (2). Dokud není splněna ukončovací podmínka běží cyklus (3-6). Selekce vybere z populace skupinu jedinců, kteří inicializují spouštěnou metaheuristiku (4). Proběhne výpočet pomocí dané metaheuristiky (5). Pro každou iteraci může být definována jiná metaheuristika nebo případně jiná konfigurace parametrů. Výstupem spuštěné metaheuristiky muže být kromě nejlepšího řešení i několik dalších stavů představujícíh prohledávanou oblast stavového prosotoru a tím částečně zachovat více informací o průběhu hledání. Nakonec dojde k vytvoření nové generace z výsledků provedené metaheuristiky a původní populace (6). Inicializace a generované výsledky se liší podle jednotlivých metaheuristik. Následující kapitoly jsou analyzou možností inicializace a sběru výsledků použitelných pro další výpočet.
6
2.4.2.1 SA
Simulované ochlazování nepracuje s žádnou skupinou jedinců ani neuchovává historii výpočtu, z které by vycházelo. V jednom okamžiku zde existuje pouze jedno aktuální řešení. Proto lze algoritmus inicializovat pouze jediným počátečním řešením. Po skončení algoritmu je výstupem jediné řešení. Navrhovaná implementace inicializace množinou jedinců je spouštět SA sekvenčně pro jednotlivé jedince a výstupem bude množina výsledných řešení.
2.4.2.2 ACO
Mravenci budují svá řešení na základě hodnoty feromonu a jisté heuristické funkce, která hodnotí nadějnost hrany pro výsledné řešení (podrobněji viz. kapitola 2.3) . Hodnoty feromonu jsou historií předchozích řešení a lze je využít pro inicializaci algoritmu přepínanou metaheuristikou. Selekcí vybraná část populace, před spuštěním samotné metaheuristiky ACO, inicializuje feromonem jednotlivé cesty a tím se přenese informaci o historii dosavadního řešení přepínanou metaheuristikou. Výsledkem ACO není pouze nejlepší nalezené řešení, ale je tu ještě historie prohledávání uložená formou feromonů. Poslední generace mravenců v sobě obsahuje právě tuto informaci o nějpravděpodobnějších řešeních. Proto výstupem metaheuristiky nebude jen samotné nejlepší řešení, ale i několik zvolených řešení vybudovaných během poslední iterace.
2.4.2.3 GA
Genetický algoritmus má k implementaci přepínané metaheuristiky nejblíž. Oba patří do stejné rodiny evolučních algoritmů, proto mají mnoho vlastností společných. Z hlediska implementace inicializace a konverze výsledků GA v prostředí přepínané metaheuristiky je důležité, že oba algoritmy pracují s populací jedinců. Proto vstupní množina jedinců se stává součástí počáteční populace GA a výstupem GA je kromě nejlepšího řešení i celá populace.
7
3 Implementace V této části se zaměřím na popis implementace programu pro testování algoritmů na úloze obchodního cestujícího (TSP). Implementaci jsem provedl v jazyce Java. V teorii grafů lze úlohu TSP popsat jako hledání co nejkratší Hamiltonovské kružnice v grafu. Základní vlastnotí Hamiltonovské kružnice je, že každý uzel je navštíven právě jednou. Jedná se o NP úplný problém.
3.1 Implementace metaheurisik Jednotlivé metaheuristiky včetně přepínané metaheuristiky jsou pouze jakýmsi obecným předpisem nezávislým na konkrétní úloze. Tomuto přístupu se říká černá skříňka (blackbox). Úkolem programátora je potom doimplementovat funkce specifické pro daný problém. Tento přístup jsem se snažil zachovat při implementaci. Metaheuristiky jsem implementoval jako generické třídy a části závislé na daném problému jsou implementovány formou rozhranní případně abstraktních tříd.
3.1.1 Implementace ACO Metaheuristika mravenčí kolonie je implementována v balíčku aco jenž obsahuje soubory: •
AntColonyOptimalization.java – implementuje běh metaheuristiky.
•
Ant.java – implementuje agenta, který na základě pravděpodobnostní matice buduje cestu v grafu a podle daného řešení značí cestu feromonem.
•
AcoDesirability.java – interface pro třídu poskytující informaci o vhodnosti dané hrany pro další postup mravence. Tato část je závislá na řešeném problému. Většinou se jedná o nějakou heuristickou funkci.
•
WeightGraph.java – třída implementuje matici feromonů a předpočítanou matici vah jednotlivích hran na jejichž základě se pohybuje mravenec.
•
AcoEvaluator.java – interface pro implementaci hodnotící funkce.
8
3.1.2 Implementace SA Metaheuristika simulovaného ochlazování je implementována v balíčku sa, obsahuje následující třídy: •
SimulatedAnnealing.java – generická třída implementující běh metaheuristiky.
•
SaState.java – interface pro reprezentaci stavu SA.
•
SaCool.java – interface ochlazovacích tříd. •
SaCoolLinear.java – implementace lineárního ochlazování.
•
SaCoolExponential.java – implementace exponenciálního ochlazovaní.
•
SaEquilibrium.java - základní implementace třídy pro testování podmínky tepelného ustálení. Lze využít pro sledování statistik počtů přijímaných zlepšujících a zhoršujících řešení, což je dobré vodítko pro nastavení parametrů t0 a tN.
•
SaUtils.java – interface pro implementaci problémově závislých funkcí pro generování nového stavu a výpočet energie stavu - nezbytných pro běh SA.
3.1.3 Implementace GA Genetický algoritmus je implementován v balíčku ga: •
GeneticAlgorithm.java – generická třída implementující běh genetického algoritmu.
•
Chromosome.java – abstraktní třída pro implementaci chromosomu.
•
GaSelector.java – interface pro třídy realizující selekční operátor. •
GaRuletRuleSelector.java – implementace rulet rule selektoru (podrobnosti kapitola 2.2)
•
GaRankSelector.java – implementace rank selektoru (podrobnosti kapitola 2.2)
•
GaBreeder.java – abstraktní třída pro implementaci operátorů křížení a mutace.
•
GaEvaluator.java – iterface třídy pro implementaci fintess funkce.
9
3.1.4 Přepínaná metaheuristika Přepínaná metaheuristika je implementována v balíku batch (ve smyslu dávkového souboru představujícího jednotlivé metaheuristiky): •
Batch.java – generická třída implementující přepínání metaheuristik. Při inicializaci přepínané metaheuristiky jsou jí předány konkrétní instance metaheuristik v pořadí v jakém budou prováděny. Metaheuristiky musí implementovat rozhranní BatchCmd.
•
BatchCmd.java – rozhranní pro metaheuristiky.
•
Selector.java – rozhraní pro třídy realizující výběr jedincům, kteří inicializují spouštěnou metaheuristiku.
•
•
AllSelector.java – implementace selektoru předávající celou populaci
•
RandSelector.java - implementace selektoru předávající N náhodných jedinců.
•
TopNSelector.java – implementace selektoru předávající N nejlepších jedinců.
BatchEvaluator.java - rozhranní pro třídu implementující funkce pro ohodnocení a porovnávání jedinců.
3.2 Implementace TSP Úloha obchodního cestujícího je implementována v několika balících: •
tsp – balíček obsahuje implementaci základních tříd pro úlohu obchodního cestujícího
•
tsp.aco – balíček obsahuje implementaci specifických částí pro ACO.
•
tsp.sa – implementace spcecifických částí pro SA.
•
tsp.ga – implementace specifických částí pro GA.
•
tsp.batch – implementace specifických částí algoritmu přepínání a hlavní funkci pro spouštění testů.
10
4 Testování V této kapitole se budu zabývat testováním výkonnosti implementovaných algoritmů. Pro srovnávání algoritmů jsem zvolil počet navštívených stavů ve stavovém prostoru úlohy (zjednodušeně by se dalo říci, že se jedná o počet volání ohodnocovací funkce v algoritmu) a jako měřítko výkonnosti délku trasy v problému obchodního cestujícího. Počet navštívených stavů jsem si pro srovnávní vybral, protože jednotlivé algoritmy se mohou velice lišit v časové náročnosti konkrétní implementace, proto by čas nebyl tím správným měřítkem. V této praci jsem si nekladl za cíl optimalizaci a každou implementaci by šlo dále vylepšovat. Implementace mnoha věcí závislých na TSP je u všech metaheuristik stejná – výpočet délky trasy (hodnotící funkce v GA, SA, ACO). Jediné co je potřeba vzít v úvahu je časová složitost algoritmů pro vytváření nových stavů, zde se vyskytují rozdíly.
4.1 Časové složitosti metaheuristik 4.1.1 Časová složitost ACO V algoritmu mravenčí kolinie se při generování nových stavů pracuje s maticema sousednosti velikosti N × N , kde N je počet měst TSP. Pro každý stav je potřeba projít N řádků a posčítat váhy pro hrany k sousedním ještě nenavštíveným uzlům N – časová složitost tedy je: N 2
4.1.2 Časová složitost SA Implementace algoritmu simulovaného ochlazování pro generování nového stavu TSP používá techniku prohození hran dvou náhodně vybraných uzlů. Reprezentace cesty v algoritmu vyžaduje prohození všech uzlů v intervalu mezi vybranými uzly – tedy v nejhorším případě N/2 uzlů. Asymptotická časová složitost operace generování sousedního stavu je: O N
11
4.1.3 Časová složitost GA Nový stav je v genetickém algoritmu generován operacemi křížení a mutace. Použitý operátor mutace je shodný s funkcí pro generování sousedního stavu SA N . Operátor křížení implementuje algoritmus křížení s rekombinací hran (ERX [10] ). Vytvoření hranové tabulky trvá dvakrát průchod přes chromosom délky N, složitost je tedy N . Operace vytváření nového potomka probíhá tak, že N-krát se z množiny sousedů vybere jeden náhodný uzel nebo pokud již žádní sousedé nezbývají je vybrán náhodně jeden z uzlů, který ještě není zahrnut v budované cestě. Operace výběru nového souseda má časovou složitost 1 a tedy složitost operátoru ERX je N . Celková složitost generování nového potomka v GA je: N
4.2 Návrh testů Při testování je potřeba vzít v úvahu rozdílnou časovou složitost pro generování nového stavu v ACO oproti SA a GA. Tento rozdíl jsem zohlednil tak, že jsem počet iterací přidělených danému algoritmu dělil počtem uzlů (měst) dané instance TSP. Každý test je navržen tak, aby spadal do některé z kategorií podle počtu iterací -10k (tisíc), 100k, 1M (milión). Samotné instance testovacích úloh TSP jsem vybíral z kolekce úloh na stránkách university Heidelberg [WWW1]. Úlohy jsem volil tak, aby se lišily jak počtem uzlů tak i jejich rozložením.
ch150 – 150 uzlů
u159 – 159 uzlů
rat575 – 575 uzlů
nrw1379 – 1379 uzlů
u2152 – 2152 uzlů pr439 – 439 uzlů Tabulka 4.0: Obrázky rozložení uzlů úloh TSP 12
4.2.1 Definice testů Testy jsou definovány formou souborů xml – všechny provedené testy lze nalézt na přiloženém CD (viz. Příloha A). Každý test byl spuštěn 100x (kromě některých instací pro 1M iterací, kdy z časových důvodů nebylo možné provést test víc jak 20x) Hodnoty v ukázkových tabulkách definicí testů mají následující význam: •
Alg. - zkratka pro danou metaheuristiku.
•
Opakování – počet opakování seznamu metaheuristik ve sloupci popis.
•
Populace – velikost základní populace.
•
Popis – popis spouštěných metaheuristik včetně zvolených parametrů.
Pro každou metaheuristiku lze zvolit řadu parametrů. V tabulkách s definicí parametru metaheuristik používám ve sloupci „Popis“ textovou reprezentaci těchto definic. Obecný formát je následující: metaheuristika(selektor, počet výsledků, …) •
metaheuristika – zkratka názvu metaheuristiky
•
selektor – název selekčního algoritmu pro výběr jedinců ze základní populace. •
all – selektor předávající celou základní populaci
•
top N – selektor předávající N nejlepších jedinců
•
rand N – selektor předávající N náhodných jedinců
•
počet výsledků – počet navrácených výsledků, které budou přidány do populace přepínané metaheuristiky.
•
zbylé parametry jsou specifické pro jednotlivé metaheuristiky
13
4.2.1.1 Parametry SA
Řetězec popisující parametry simulovaného ochlazování: SA( … ,iterace,equilibrium,t0,tN) • • • •
iterace – počet iterací hlavního cyklu simulovaného ochlazování equilibrium – počet zkoumaných stavů v rámci jedné iterace t0 – počáteční teplota tN – koncová teplota
Parametry SA jsem volil experimentálně na základě několika pokusů. Speciálně t0 a tN jsem volil na základě statistiky equilibria (počet přijatých stavů zlepšujících/zhoršujících). Počáteční teplotu jsem nastavil na teplotu při níž počet přijatých nových stavů (zlepšující a zhoršující dohromady) z celkového počtu iterací pro dosažení equilibria byl přibližně 50%. Koncovou teplotu jsem volil z oblasti, kde už nebyly přijímány žádné zhoršující stavy. Celkový počet zkoumaných stavů SA je:
stavů=iterace ×equilibrium
4.2.1.2 Parametry GA
Řetězec popisující parametry simulovaného ochlazování: GA(..., iterace, populace, potomci, mutace, selekce) •
iterace – počet opakování hlavního cyklu metaheuristiky
•
populace – velikost populace genetického algoritmu
•
potomci – počet vytvářených potomků v každém cyklu
•
mutace – pravděpodobnost mutace
•
selekce – určuje jaký algoritmus selekce se má použít •
rulet – rulet rule selekce
•
rank – rank selekce
Parametry GA jsem volil na základě několika pokusů. Celkový počet zkoumaných stavů GA je:
stavů=iterace× potomci
14
4.2.1.3 Parametry ACO
Řetězec popisující parametry algoritmu mravenčí kolonie: ACO(..., iterace, mravenci, alfa, beta, ro) • • • • •
iterace – počet opakování hlavního cyklu mravenci – počet budovaných řešení v rámci jednoho hlavního cyklu alfa – koeficient významnosti hodnoty feromonu beta – koeficient významnosti hodnoty určující vhodnost hrany ro – koeficient odpařování feromonu
Hodnoty alfa a beta jsem zvolil na základě vědecké práce zkoumající optimální parametry pro ACO [6] . Zbylé parametry jsem určil experimentálně. Celkový počet zkoumaných stavů ACO je: uzlů TSP.
stavů=iterace×mravenci×N , kde N je počet
15
4.2.1.4 Ukázka nastavení testů
Alg. Opakování Populace
Popis
SA
1
1
SA(all,1,1000,10,200,0.1)
GA
1
100
GA(all,1,1000,60,10,0.05,rank)
ACO 1
1
ACO(all,1,6,11,1,6,0.6)
batch 1
20
ACO(top 1,8,7,7,1,6,0.6), SA(top 1,1,4500,1,200,0.1), GA(top 8,5,265,50,10,0.5,rulet) Tabulka 4.1: ch150 – 10k iterací
alg. opakování populace
popis
SA
1
1
SA(all,1,10000,10,200,0.1)
GA
1
250
GA(all,1,2000,250,50,0.05,rank)
ACO 1
1
ACO(all,1,15,44,1,6,0.75)
batch 5
20
ACO(top 5,10,10,8,1,6,0.7), SA(top 1,1,500,10,200,0.1), GA(top 10,5,300,60,10,0.5,rank) Tabulka 4.2: ch150 – 100k iterací
alg. opakování populace
popis
SA
1
1
SA(all,1,10000,100,200,0,1)
GA
1
1000
GA(all,1,4000,1000,250,0.05,rank)
ACO 1
1
ACO(all,1,70,95,1,6,0.85)
batch 5
20
ACO(top 3,1,15,44,1,6,0.75), SA(top 1,1,5000,10,200,0.1), GA(top 10,5,2500,100,20,0.5,rank) Tabulka 4.3: ch150 – 1M iterací
16
4.3 Výsledky testů
Obrázek 4.1: ch150 – 10k iterací
Obrázek 4.2: ch150 – 100k iterací
17
Obrázek 4.3: ch150 – 1m iterací
Obrázek 4.4: u159 – 10k iterací
18
Obrázek 4.5: u159 – 100k iterací
Obrázek 4.6: u159 – 1m iterací
19
Obrázek 4.7: pr439 – 10k iterací
Obrázek 4.8: pr439 – 100k iterací
20
Obrázek 4.9: pr439 – 1m iterací
Obrázek 4.10: rat575 – 10k iterací 21
Obrázek 4.11: rat575 – 100k iterací
Obrázek 4.12: rat575 – 1m iterací 22
Obrázek 4.13: nrw1379 – 10k iterací
Obrázek 4.14: nrw1379 – 100k iterací
23
Obrázek 4.15: nrw1379 – 1m iterací
Obrázek 4.16: u2152 – 10k iterací
24
Obrázek 4.17: u2152 – 100k iterací
Obrázek 4.18: u2152 – 1m iterací
25
26
5 Závěr V rámci diplomové práce jsem implementoval obecné třídy pro metaheuristiky mravenčí kolonie, simulovahého ochlazování a genetický algoritmus. Dále jsem provedl návrh a implementaci algoritmu pro přepínání metaheuristik podle zadání práce. Nakonec jsem realizoval sadu testů na úloze obchodního cestujícího. V testech dokázala přepínaná metaheuristika výrazněji překonat všechny samostatné metaheuristiky jen u nejmenších testovaných instancí (ch150, u159). Jinak její výkonnost byla srovnatelná s ACO nebo mírně horší. Z tohoto hlediska se jeví její použití jako nepraktické – je nutné navíc implementovat jednotlivé heuristiky. Ovšem jako každá metaheuristika i přepínaná silně závisí na zvolených parametrech. Proto je možné, že při volbě jiných parametrů a jiné konfiguraci dílčích metaheuristik, by dosáhla lepších výsledků i u větších instancí. Problémem je, že počet možností konfigurace prudce vzrůstá oproti samostatným metaheuristikám a volba parametrů je relativně složitým úkolem. Jako další postup při zkoumání přepínaních metaheuristik by bylo zajímavé soustředit se na správnou volbu parametrů a dále provést testy i na jiných optimalizačních problémech jako jsou například úlohy splnitelnost booleovských formulí nebo barvení grafu.
27
28
6 Literatura [1] Metaheuristic (online) http://en.wikipedia.org/wiki/Metaheuristic [2] Simulated annealing (online) http://en.wikipedia.org/wiki/Simulated_annealing [3] S. Kirkpatrick, C. D. Gelat, M. P. Vecchi: Optimalization by Simulated Annealing, 1983. [4] V. Mařík, O. Štěpánková, J. Lažanský a kol: Umělá inteligence (3) 2001 [5] M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992. [6] D. Gaertner, K. Clark: On Optimal Parameters for Ant Colony Optimization Algorithms (2005) http://tweetypie.doc.ic.ac.uk/~dg00/twiki/data/Publications/ICAI-GaertnerClarkAccepted.pdf [7] Inteligence hejna (online) http://cs.wikipedia.org/wiki/Inteligence_hejna [8] Kolektivní inteligence (online) http://cs.wikipedia.org/wiki/Kolektivn%C3%AD_inteligence [9] M. Obitko: Genetic Algorithms (online) http://www.obitko.com/tutorials/genetic-algorithms/ [10] Edge recombination operator (online) http://en.wikipedia.org/wiki/Edge_recombination_operator
7 Odkazy [WWW1] Testovací úlohy TSP, universita Heidelberg (online) http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/ALL_tsp.tar. gz
29
30
Použité zkratky ACO – ant colony optimalization ERX – edge recombination crossover GA – genetics algorithm NP – nondeterministic polynomial SA – simulated annealing (simulované ochlazovaní) TSP – travelling salesman problem SAT - boolean satisfiability problem
31
32
Příloha A Obsah CD •
definice_testu – obsahuje xml soubory s definicemi testů
•
diplomova_prace – elektronická verze DP
•
graphs – obrázky grafů
•
heuristic – adresář obsahuje java projekt pro netbeans implementující zadání DP •
dist/heuristic.jar – spustitelný soubor implementace
•
src – zdrojové kódy
•
r_scripts – skripty pro generovaní grafů z naměřených dat
•
tsp_ulohy – instance problému obchodního cestujícího
•
tsp_vysledky – naměřené hodnoty z testů
33
34
Příloha B Parametry pro spouspouštění programu prog_name batch.xml [options] Options: -r=n
n repeat number
-o=str str output file for results
35
