Problém obchodního cestujícího

1. ÚKOL

Navrhněte a implementujte algoritmus řešící problém obchodního cestujícího. Funkčnost algoritmu ověřte na sadě dodaných testovacích příkladů ve všech třech variantách. Testovací příklady jsou ohodnocené neorientované grafy zadané uzlovou maticí. Ohodnocení jedné hrany (koincidence uzel-uzel) je reprezentováno jedním znakem v matici. Ohodnocení hrany je určeno pořadím znaků '1'-'9', 'A'-'Z', '0' znamená, že hrana mezi uzly neexistuje. Hodnota hrany se spočítá podle kódu:

        if (matice[i][j] == '0')
                hrana neexistuje
        else if ((matice[i][j] >= '1') && (matice[i][j] <= '9'))
                hodnota je (matice[i][j] - '0')
        else if ((matice[i][j] >= 'A') && (matice[i][j] <= 'Z'))
                hodnota je (matice[i][j] - 'A' + 10)
Neexistující hrany zpracujte třemi způsoby: hrany existují a mají hodnotu 10, hrany existují a mají hodnotu 10000, hrany neexistují.

2. ÚVOD

Po dohodě se zúčastněnými jsme realizovali řešení pomocí Hopfieldovy neuronové sítě. Nejedná se o běžný způsob, uvidíme však jeho podobnost s metodami probíranými na přednáškách. Jako výsledek je zde zpřístupněn demonstrační applet napsaný v programovacím jazyce Java. Dále jsou zde uvedeny výsledky experimentu s nastavením sítě.

3. TEORETICKÝ ROZBOR

3.1 PROBLÉM OBCHODNÍHO CESTUJÍCÍHO

Známý problém obchodního cestujícího můžeme popsat takto:

Na mapě je zvoleno N měst a jejich vzájemná vzdálenost pro každou z dvojic. Problémem obchodního cestujícího je určit takové pořadí návštěv jednotlivých měst, aby každé město bylo navštíveno právě jednou, výsledná délka (cena, jízdné, ...) byla nejkratší a cestující se vrátil zpět do města, kde cestu začal.

Náš problém náleží do kategorie NP-úplných problémů, pro které je typická výpočetní náročnost. Např. pro náš případ vždy existuje nějaké ideální řešení (případně více, ale se stejným výsledkem), které můžeme lehce najít tak, že prostě spočítáme délku všech možných cest a vybereme tu nejkratší. Již pro malá N je ale počet vysoký a roste exponenciálně. Proto se budeme snažit najít postup jiný, který nám sice se stoprocentní jistotou neumí říci, že zvolená trasa je skutečně nejkratší, ale od ideálního výsledku se výsledek jím předkládaný liší jen málo. Toto tzv. supotimální řešení je často dostačující.

Podle dostupné literatury jsme se rozhodli řešit náš problém pomocí Hopfieldovy sítě. Učící fáze je poněkud netradiční, matice vah se nastavuje podle zadání úlohy (nikoliv libovolně, jak je to běžné). Vybavování je již klasické, probíhá po krocích až do ustáleného stavu. V jednotlivých iteracích se řeší obyčejné diferenciální rovnice prvního řádu. Podrobnější teoretický rozbor je obsažen v následující části (viz. 3.2).

3.2 HOPFIELDOVA SÍŤ

3.2.1 ZÁKLADNÍ MODEL

Nejlépe osvětlí topologii sítě následující obrázek (n je počet neuronů sítě):

.
Obrázek 1

V Hopfieldově síti je každý neuron spojen s každým, všechny neurony jsou zároveň vstupní i výstupní. Míra vzájemné spojenosti dvou neuronů i a j je vyjádřena vahou wij. Žádný neuron však není spojen sám se sebou, váha wii je nulová. Výstup neuronů sítě bude binární, tedy čísla 0 a 1.

3.2.2 PROCES UČENÍ

Proces učení je v našem případě odlišný od klasického, síť se vlastně naučí nastavením vah a počátečních stavů neuronů podle smyslu úlohy. Toto nastavení se v experimentech (viz. 6) ukázalo jako klíčové při úspěchu sítě.

3.2.3 PROCES VYBAVOVÁNÍ

Proces vybavování zde založíme na minimalizaci energetické funkce, jejíž obecný tvar je:

,
(1)

kde i, j = 1, ... ,n, n je počet neuronů sítě a prahovou funkci neuronu zvolíme nulovou - zastupuje jí tzv. bias, viz. 4.2. Energetická funkce nám říká, jaké chyby se dopouštíme použitím současných výsledků sítě. Jejich další modifikací energii opět snížíme a přiblížíme se ke správnému výsledku. Protože si vždy vybíráme takovou úpravu, která hodnotu funkce sníží nejvíce, mluvíme o gradientní metodě. Výsledkem je stav, kdy se výstup neuronu již v čase neměmí:

,
(2)

j je přes všechny neurony sítě. Ze znalosti energetické funkce odvodíme nastavení vah, které pak použijeme pro výpočet řešení. Všechna odvození a výsledné vzorce odvodíme v následující kapitole 4.

4. IMPLEMENTACE

4.1 ÚVOD

Máme dáno N měst (N > 2) a funkci d definující vzdálenost měst pro každou dvojici. Použijeme síť s n = N x N neurony, jejichž stavy indexujeme yru (r označuje číslo města a u jeho možné pořadí). Neurony v ní uspořádáme maticově, jak ukazuje tabulka 1.

zastávky
města ? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
Tabulka 1

Řádky tabulky představují města, která chceme navštívit a sloupce určují pořadí zastávek v těchto městech.

Jako přenosovou funkci vybereme sigmoidu (podle [1]), yru bude tedy nabývat hodnot nula nebo jedna (rozbor viz. 3.2.1). Výstup jedna (neuron je aktivní, šedé políčko v tabulce) znamená, že město r bude navštíveno v pořadí u, výstup nula znamené že město v takovém pořadí nebude navštíveno.

4.2. ENERGIE SÍTĚ

Poznámka: protože výstupy sítě jsou v dalším kroku jejími vstupy, budeme místo xi psát yi.

Abychom dostali při řešení kýžený výsledek, budeme minimalizovat energetickou funkci sítě (v síti vždy proběhne taková změna, která energetickou funkci zminimalizuje). Tato funkce, v podstatě stejná jako ve výrazu 1, musí však splňovat některé podmínky plynoucí z podstaty úlohy. Ne každé pořadí návštěv měst tak problém řeší. Ke správnému řešení zavedeme následující:

Výsledná funkce energie sítě, jejíž minimalizací získáme řešení, je součtem uvedených výrazů:

(7)

Výraz ještě můžeme upravit do tvaru

,
(8)

kde ?rs je Kroneckerovo delta, tj. ?rs = 1, jestliže r = s, a ?rs = 0 jinak. Jeho porovnání s výrazem 1 nám umožní stanovit váhy, které pomohou k minimalizaci funkce E.

(9a)
(9b)
(9c)

Váha wj0 představuje bias j-tého neuronu. Vývoj stavu sítě nám celkově zachytí následující soustava diferenciálních rovnic:

(10a)

kde ?j je vhodná časová konstanta, ? je sigmoioda. Můžeme též zapsat velmi podobnou rovnici pro vývoj vnitřních potenciálů ?j:

(10b)

Podle stavu příslušných neuronů (viz. 4.1) sestavíme pořadí navštívených měst.

5. IMPLEMENTACE

Pro implementaci jsme si vybrali jazyk Java z jednoho důvodu: můžeme vytvořit iteraktivní program na stránkách internetu a zpřístupnit tak program mnoha lidem. Proto má programi interaktvní část, kde si můžeme města na mapě určit myší a sledovat výsledek na obrazovce. V takovém případě ovšem nelze definovat, zda cesta mezi městy vede nebo nevede a proto se vše řeší, jako kdyby cesty existovaly všechny. Můžeme si to představit jako cestování letadlem.

Návod k obsluze je uveden spolu s appletem na následující stránce:

Demonstrační applet

Applet použivá knihovnu Swing, k jeho spuštění budete potřebovat Java Plug-in verze 1.1.2 a vyšší. Zdrojový kód je přístupný jako balíček ZIP obsahující JAVA soubory a dávky pro překlad v operačním systému Windows, dokumentace je ve formě JAVADOC.

6. MĚŘENÍ

Hned na začátek musíme napsat, že se nám nepodařilo otestovat všechny dodané soubory. Implementace pole neuronů, ale především jejich vah je v paměti velmi náročná a s použitím jazyka Java ještě vyšší. Nejmenší reálný typ float má délku 32 bitů, úpravami původního algoritmu na použití celočíselného byte se sice podařilo hodně uspořit, ale protože v řešení ovlivňuje pomocí vah každý neuron každý (neuronů je dvojnásobně než měst), jedná se o rozsáhlá pole. Mohli jsme tak otestovat jedině příklady s počtem měst menším než zhruba 100. Zde tedy musíme konstatovat, že takto naprogramovaná metoda se hodí pouze pro malé počty měst. Po zvážení všech možností se nám náskýtá možnost jen snížit její rozměr na polovinu (je symetrická), ani to však náš problém neřeší.

K řešení jsme si tedy vybrali jiná testovací data, vygenerovaná pomocí programu hcp. Počet měst se pohybuje do 50, instance jsou k dispozici ke stažení. Výsledky shrnují tabulky 1, 2, 3.

Při implementaci se ukázala důležitost zvolení váhových konstant A, B, C a D. Použítá metoda řešení není ideální - je silně závislá právě na těchto parametrech. Nastavením jedné a vyzdvihnutím jiné jednoduše poškodíme smysl celé úlohy - cestující se objeví najednou v několika městech, bude konat nesmyslně dlouhé cesty, atd. Literatura je v tomto směru skoupá, doporučuje testování. Nejlepší by bylo tyto konstanty řídit podle velikosti a typu úlohy. Jak ale, to by bylo předmětem dlouhého testování. Po několika testech jsme určili: A = B = 2.1, C = 1 a D = 1.3, aneb je kladen na důraz dodržení správnosti zadání, až poté na délku nalezené cesty (konstanty jsou brány jako poměr k etalonu, nejméně významné konstantě C).

Další experimenty byly provedeny s nastavením počáteční hodnoty lambda (při srovnání s klasickými metodami se jedná vlastně o teplotu, která se v průběhu výpočtu mění). Ta ovlivňuje kvalitu řešení: rozhoduje, zda a jak bude výstup neuronu aktivní. Hodnota 110 se ukazuje i po testech jako dobrá. Graf ukazuje nelineární funkci vzhledem k různým lamda:


Graf 1.

Neméně důležitá je i konstanta time - ta určuje, jak rychle se bude lambda měnit v závislosti na počtu kroků (v klasických metodách se jedná o žíhání - s většícím se počtem kroků dostává lambda nižší hodnoty a pomáhá tak proti uváznutí v lokálním minimu). Pro přiliš rychlé změny dostáváme špatné výsledky (řešení vyskakuje i z velkých minim), pro pomalé změny strávíme s řešením spostu času (a výsledky často v lokálních minimech uváznou). Úkolem je najít kompromis, my jsme zvolili hodnotu 7000:


Graf 2.

Počet měst Nejlepší cesta Počet kroků
37 špatný výsledek 70593
24 202 67728
46 175 62527
33 254 64778
45 198 76210
23 354 64650

Tabulka 1. Výsledky měření, varianta 1 - hrana má cenu 10.

Počet měst Nejlepší cesta Počet kroků
37 špatný výsledek 55030
24 182 54612
46 196 55000
33 254 54884
45 špatný výsledek 54835
23 342 54736

Tabulka 2. Výsledky měření, varianta 2 - hrana má cenu 10000.

Počet měst Nejlepší cesta Počet kroků
37 294 55078
24 172 44391
46 173 55074
33 202 64711
45 205 64665
23 302 96215

Tabulka 3. Výsledky měření, varianta 3 - hrana neexistuje.

7. ZÁVĚR

Podařilo se nám demonstrovat použití neuronové sítě Hopfieldova typu pro řešení optimalizačního problému obchodního cestujícího pomocí programovací jazyka Java. Z několika experimentů s počátečním nastavením sítě se nejlepší ukázaly hodnoty uvedené v části 6. Museli jsme se ovšem omezit na jiná než testovací data, důvody shrnuje stejná část. Při testech jsme pozorovali delší dobu řešení pro počet měst větší než 15. Podle literatury existují modifikace použitého algoritmu, které takovou nevýhodou netrpí, jejich implementace je však již náročnější.

8. LITERATURA

[1] J. Šíma, R. Neruda: Teoretické otázky neuronových sítí, stránky 79-93, Vydavatelství MFF UK, 1996
[2] M. Šnorek, M. Jiřina: Neuronové sítě a neuropočítače, Vydavatelství ČVUT, 1996
[3] P. Herout: Učebnice jazyka Java, Kopp, 2000
[4] M. Brát: http://cs.felk.cvut.cz/~bratm/vyuka/nan.html
[5] http://www.is-frankfurt.de/cosa/tsp/tsp.html
[6] http://www.informatik.uni-heidelberg.de/groups/comopt/index.html
[7] http://www.yajima.kuis.kyoto-u.ac.jp/staffs/sengoku/java/TSP/