Problém obchodního cestujícího

Petr Kadlec

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

Způsob řešení

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

Kódování chromozomu

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.

Počáteční generace

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

Vliv velikosti populace

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

Tvorba následující generace (hlavní krok genetického algoritmu) sestává z několika kroků:

  1. Elitismus
  2. Křížení
  3. Mutace

Elitismus

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

Význam velikosti elity na konvergenci

Křížení

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.

Výsledky operátorů křížení

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.

Mutace

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

Operátor mutace záměnou
Operátor mutace inverzí

Řízení a ukončení výpočtu

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.

Naměřené výsledky

Neexistující = nekonečno

Nejprve výsledky pro grafy tak, jak byly zadány:

GrafPočet uzlůDélka túryČas výpočtuGenerací
A218723045 + 100
B 62538384:0652405
C218717320 + 224
D 2005782:318919
E 2569254:5115588
F218713623 + 184
G12964749 + 170
H 2361293 + 1
I218712392 + 281
J204820051 + 26
K12965430 + 125
TESTIK811292:515434

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.

Neexistující = 100

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.

GrafPočet uzlůDélka túryČas výpočtuGenerací
A2187237171:29960
B 62525913:0810977
C2187333590:38157
D 2005782:318919
E 2562711:24190
F2187313881:491792
G1296196271:49896
H 2363640:3832
I2187335630:40234
J2048223001:341792
K1296169971:03256
TESTIK811292:515434

Neexistující = 10

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

GrafPočet uzlůDélka túryČas výpočtuGenerací
A2187145403:113392
B 62516501:062048
C2187151061:04896
D 2005070:2011044
E 2562651:310
F2187149701:451792
G129659402:055888
H 2362541:311984
I2187149450:54676
J2048194680:44576
K129658390:461024
TESTIK811292:515434

Postřehy z měření

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

Vývoj délky nejlepšího řešení

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.

Závěr

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


Ke stažení

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)

Literatura

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