Je dáno m měst. Některá města jsou propojena silnicemi o známé délce. Úkolem obchodního cestujícího je navštívit postupně všechna města právě jednou. Nalezněte takovou túru (permutaci měst), aby celková délka cesty byla minimální.
Rozhodl jsem se řešit problém pomocí genetického algoritmu. U genetického algoritmu je ovšem mnoho parametrů, na jejichž volbě závisí činnost algoritmu. Já jsem použil následující:
Chromozom obsahuje právě m genů, přičemž každý obsahuje číslo města, která jsou navštívena právě v pořadí daném chromozomem. (Tento způsob se obvykle nazývá permutační kódování.) V každém okamžiku obsahuje chromozom platnou permutaci, ve které je index každého města právě jednou. (Na toto omezení je třeba myslet při návrhu operátorů, viz dále.)
Chromozom je dále ohodnocen celkovou délkou jím reprezentované túry. Toto ohodnocení není používáno jako takové, ale je před tím transformováno fitness funkcí (nakonec jsem používal funkci 1/x, viz dále), protože se tím zjednoduší operace výběru. Hledán je chromozom s maximální hodnotou fitness, tzn. minimální délkou cesty. (Poznámka: Na grafech bude ukazována délka cesty, nikoliv fitness, protože to je evidentně mnohem intuitivnější.)
Jelikož řešené grafy nejsou úplné, je třeba zvážit, jak přistupovat k chromozomu, který obsahuje neexistující hranu. Já jsem se rozhodl takové chromozomy neřešit nijak speciálně, brát je jako platná řešení. Pouze tím, že neexistující hrany jsou ohodnoceny řádově vyšším ohodnocením než existující, je zajištěno, že se algoritmus pokusí hledat cestu vedoucí pouze přes existující hrany.
Genetický algoritmus funguje tak, že vylepšuje existující řešení. Ke spuštění algoritmu tedy potřebujeme nějaké počáteční řešení. Původně jsem zkoušel algoritmus spustit na náhodné řešení. To ovšem nefungovalo. Vygenerované náhodné řešení bylo velice špatné, neboť obsahovalo ohromné množství neexistujících hran a algoritmus jen velice pomalu tyto hrany odstraňoval.
Proto jsem posléze implementoval (mírně upravenou) Possovu heuristiku, která je schopna na mnoha grafech nalézt nějakou Hamiltonovskou kružnici. Navíc tato heuristika používá na několika místech náhodnou volbu, čímž umožňuje nalézt více různých Hamiltonovských kružnic. Na počátku je tedy vygenerován požadovaný počet túr a je použit jako počáteční generace chromozomů.
Otázkou je, jak velká má populace být. Je zřejmé, že větší populace pokryje větší část prostoru úlohy, ovšem zase se pomaleji zpracovává. Několik velikostí populace jsem vyzkoušel a z následujícího grafu je vidět, že větší populace má opravdu konverguje v méně generacích. Ovšem vzhledem k tomu, že za stejnou dobu se zvládne vypočítat mnohem více generací při menší populaci, má z hlediska času lepší konvergenci menší populace. Proto jsem při řešení používal spíše menší populaci (cca 100 – 200 chromozomů).
Problém nastává, pokud Possova heuristika není schopna nalézt žádnou Hamiltonovskou kružnici. Já to řeším opět tak, že použiji i takovou túru, která prochází přes neexistující hrany, ovšem algoritmus má s takovými grafy stejné potíže jako v případě již zmíněné náhodně generované počáteční populace.
Tvorba následující generace (hlavní krok genetického algoritmu) sestává z několika kroků:
Nejprve je do následující generace přeneseno několik chromozomů s nejlepším ohodnocením. Tím je zaručeno, že se nejkvalitnější dosud nalezené řešení neztratí. Počet takto přenášených chromozomů je nastavitelný. Experimentoval jsem s hodnotou tohoto parametru, ovšem jak je vidět z následujícího grafu, nemá na konvergenci žádný zásadnější vliv (samozřejmě pokud neuvažujeme případné extrémní hodnoty).
Zbytek nové generace je poté vytvořen křížením. To probíhá tak, že se vždy vyberou dva rodiče, na které je pak aplikován operátor křížení, a výsledný chromozom je poté zařazen do nové generace.
Z rodičů je jeden vybrán podle své fitness (pravděpodobnost výběru chromozomu k je f(k)/Σf(i)). Druhý rodič je vybrán zcela náhodně. Na tomto grafu je vidět, že případná volba druhého rodiče podle fitness nemá příliš vliv na výsledky.
Jako operátor křížení jsem zkoušel použít jednak jednoduché dvoubodové křížení, jednak tzv. greedy crossover, který je o něco složitější, ovšem využije více informací z rodičů. Jak je vidět na následujícím grafu, má operátor greedy crossover jen o málo lepší výsledky než jednodušší dvoubodové křížení, ovšem jelikož je o hodně pomalejší, rozhodl jsem se ho nepoužívat.
Jak již bylo zmíněno, je třeba při práci s chromozomy pamatovat na požadavek, aby každý chromozom obsahoval platnou permutaci. Proto nelze použít „tradiční“ dvoubodové křížení, při kterém se pouze zamění příslušné části rodičů, protože tím by se některá města mohla v chromozomu objevit vícekrát na úkor jiných. Proto použitý operátor pracuje tak, že z jednoho z rodičů převezme příslušnou část mezi dvěma náhodně zvolenými body, ovšem zbytek doplní z druhého rodiče (přičemž zachovává pořadí) tak, aby výsledkem byla platná permutace.
Operátor greedy crossover pracuje následujícím způsobem: Nejprve náhodně zvolí počáteční město. Poté se podívá, jaká města následují po tomto městě v obou rodičích. Z nich vybere to město, které má z počátečního města menší vzdálenost. Pokud již bylo použito, použije se druhé; pokud bylo i to použito, vybere se zcela náhodně libovolné dosud nepoužité město. Toto se opakuje až do zaplnění chromozomu všemi městy.
Na chromozomy získané křížením (tzn. nikoliv chromozomy přenesené jako elitní, ty jsou zachovány beze změn) je poté aplikována mutace. Každý z chromozomů má šanci pms, že na něj bude aplikována mutace záměnou a šanci pmi, že na něj bude aplikována mutace inverzí (a je tedy možné, že budou na jeden chromozom aplikovány obě mutace).
Mutace záměnou funguje tak, že dvě náhodně vybraná města jsou navzájem vyměněna. (Např. z permutace ABCDEF může být záměnou měst B a E vytvořena permutace AECDBF.)
Mutace inverzí provede otočení náhodně zvoleného úseku permutace měst. (Např. z permutace ABCDEF může být inverzí mezi B a E vytvořena permutace AEDCBF.)
Na následujících grafech je vidět význam obou pravděpodobností. Je zřejmé, že operátor inverze je účinnější a až do pravděpodobnosti zhruba 30 % je vidět výrazný vzestup rychlosti konvergence. Oproti tomu je operátor záměny prakticky neúčinný. Proto jsem používal hodnoty pmi = 30 %, pms = 5 %.
Hlavní cyklus programu neustále generuje nové generace a sleduje hodnotu nejlepšího chromozomu v populaci. Pokud po jistou dobu (typicky několik stovek generací) nedochází ke zlepšení, program o něco zvýší pravděpodobnosti mutací (pokud se znovu „rozjede“ nové zlepšování, pravděpodobnosti se po chvíli vrátí na původní hodnoty). Pokud se toto několikrát neúspěšně opakuje a stále nedochází k žádnému zlepšení, program se ukončí.
Čas od času se namísto nejhoršího chromozomu vloží nově vygenerovaný „speciální“ chromozom, čímž se snažím zavádět nové vlastnosti. (Slovem „speciální“ myslím např. cestu vyrobenou tak, že se z náhodně zvoleného města vybere náhodně libovolná existující hrana, kterou se posléze pokračuje, atd.)
Při všech úpravách chromozomů se kontroluje, zda již stejný chromozom v populaci není. Pokud ano, je vygenerován nový, příp. stávající zmutován, čímž se zabraňuje situaci, kdy by populaci tvořilo několik málo řešení s vysokým ohodnocením.
Nejprve výsledky pro grafy tak, jak byly zadány:
Graf | Počet uzlů | Délka túry | Čas výpočtu | Generací |
A | 2187 | 23045 + 100 | ||
B | 625 | 3838 | 4:06 | 52405 |
C | 2187 | 17320 + 224 | ||
D | 200 | 578 | 2:31 | 8919 |
E | 256 | 925 | 4:51 | 15588 |
F | 2187 | 13623 + 184 | ||
G | 1296 | 4749 + 170 | ||
H | 236 | 1293 + 1 | ||
I | 2187 | 12392 + 281 | ||
J | 2048 | 20051 + 26 | ||
K | 1296 | 5430 + 125 | ||
TESTIK | 81 | 129 | 2:51 | 5434 |
Pokud se ve sloupci Délka túry nachází kurzivou vytištěný výraz A + B, pak to značí, že nebylo nalezeno žádné platné řešení, nejlepší nalezené řešení mělo délku A, ale navíc B neexistujících hran. To jsou právě grafy, u kterých Possova heuristika nedokázala najít jedinou Hamiltonovskou kružnici.
V další tabulce je vidět, jak se situace změní, pokud z grafů vyrobíme úplný graf tím, že místo neexistujících hran vložíme hrany o délce 100.
Graf | Počet uzlů | Délka túry | Čas výpočtu | Generací |
A | 2187 | 23717 | 1:29 | 960 |
B | 625 | 2591 | 3:08 | 10977 |
C | 2187 | 33359 | 0:38 | 157 |
D | 200 | 578 | 2:31 | 8919 |
E | 256 | 271 | 1:24 | 190 |
F | 2187 | 31388 | 1:49 | 1792 |
G | 1296 | 19627 | 1:49 | 896 |
H | 236 | 364 | 0:38 | 32 |
I | 2187 | 33563 | 0:40 | 234 |
J | 2048 | 22300 | 1:34 | 1792 |
K | 1296 | 16997 | 1:03 | 256 |
TESTIK | 81 | 129 | 2:51 | 5434 |
A nakonec výsledky pro grafy, ve kterých jsou místo původně neexistujících hran vložíme hrany o délce 10. V tomto případě již také nemá smysl inicializovat populaci pomocí Possovy heuristiky, neboť každá permutace měst nyní označuje platnou túru a túry vedoucí přes původně existující hrany nejsou o nic výhodnější než libovolné jiné. Proto je populace inicializována náhodně.
Graf | Počet uzlů | Délka túry | Čas výpočtu | Generací |
A | 2187 | 14540 | 3:11 | 3392 |
B | 625 | 1650 | 1:06 | 2048 |
C | 2187 | 15106 | 1:04 | 896 |
D | 200 | 507 | 0:20 | 11044 |
E | 256 | 265 | 1:31 | 0 |
F | 2187 | 14970 | 1:45 | 1792 |
G | 1296 | 5940 | 2:05 | 5888 |
H | 236 | 254 | 1:31 | 1984 |
I | 2187 | 14945 | 0:54 | 676 |
J | 2048 | 19468 | 0:44 | 576 |
K | 1296 | 5839 | 0:46 | 1024 |
TESTIK | 81 | 129 | 2:51 | 5434 |
V první tabulce je vidět, že rozlehlé řídké grafy mému programu vůbec nevyhovují. Jakmile totiž není známo jediné platné řešení, genetický algoritmus nemá na čem stavět a není schopen řešení vylepšit.
Stejný problém, ovšem z druhé strany, se objevuje v druhých dvou tabulkách. Pokud je totiž graf původně velice řídký, má po vložení nových hran velké množství stejně oceněných hran. Výsledkem je, že algoritmus najde v nultém kroku nějakou Hamiltonovskou kružnici a následně se tato kružnice už prakticky nezlepšuje, protože by program musel najít těch několik málo hran s jiným ohodnocením (což jsou tytéž hrany, které se mu nedařilo využít v prvním případě). Tento problém je zvláště dobře vidět na tom, jak málo vylepšení se v případě upravených grafů použije. Výsledky uvedené v tabulce byly typicky dosaženy během několika málo úprav původního řešení (obvykle do cca 5 úprav). To je velký rozdíl oproti těm úspěšně řešeným grafům z první části, jejichž řešení bylo i více než 400-krát vylepšeno. (Což vedlo k elegantnímu hyperbolickému tvaru grafu na následujícím obrázku, který znázorňuje vývoj délky nejlepšího nalezeného řešení pro graf B. Naproti tomu vůbec nemá smysl zde ukazovat obdobný graf pro ony řídké grafy, neboť tento „graf“ by obsahoval několik málo bodů, které by tvořily téměř rovnou úsečku u horního okraje grafu.)
Při řešení jsem si všiml, že stojí za to ručně upravovat některé parametry podle toho, jaký graf se zrovna řeší. Rozhodně se nedá říci, že by existovaly ideální parametry (velikost populace, použité křížení, …), které by byly vhodné pro všechny úlohy. U menších grafů jsem proto obvykle zvětšil velikost populace, protože i tak byl program dostatečně rychlý. Pro malé grafy jsem také několikrát vyzkoušel zapnout i výše zmiňovaný operátor greedy crossover. Ovšem jediný graf, na němž jsem zaznamenal nějaký vliv tohoto operátoru, byl TESTIK. Na ostatních bylo jediným efektem zpomalení programu.
Mnou implementovaný genetický algoritmus se poměrně dobře vypořádává s hustšími grafy, ve kterých není problém nalézt několik počátečních řešení, která algoritmus poté vylepšuje. Pokud je ovšem použit na řídký graf, ve kterém použitá Possova heuristika nenalezne žádné počáteční řešení, algoritmus není schopen z neplatných řešení (obsahujících neexistující hrany) využít jejich dobré části a vyrobit platné řešení. Proto na takové grafy není můj program vhodný. Pokud by měl být přesto použit, bylo by nejspíše nutné změnit způsob kódování chromozomů tak, aby umožňoval používat buď neúplné tůry (tzn. túry, které neprochází všemi městy), nebo naopak takové túry, které jedním městem mohou procházet několikrát. To by mohlo vést k tomu, že by algoritmus využil částečné informace z takových chromozomů a nalezl by platné počáteční řešení. Tuto možnost jsem ovšem nezkoumal a je to jen návrh možností.
Program (screenshot) byl řešen v systému Borland Delphi verze 6. Zdrojové texty jsou v ZIP archivu tsp_src.zip (9 782 B).
Veškerá data nasbíraná při pokusech je možnost stáhnout v ZIP archivu tsp_data.zip (156 203 B)
Marek Obitko – Introduction to genetic algorithms with Java applets, WWW
Mařík, Štěpánková, Lažanský a kol. – Umělá inteligence (3), Academia 2001