2. semestrální práce z předmětu 36NAN
Problém obchodního cestujícího

ABSTRACT

This article covering how to solve task which is called Travelling Salesman Problem using Hopfield neural network. As result there is demonstration applet written in Java programming language. There are also results of experiments with network properties.

1. ÚKOL

Navrhněte způsob použití neuronové sítě na úloze obchodního cestujícího a tento způsob otestujte.

2. ÚVOD

Tento článek popisuje způsob, jak řešit úlohu známou jako problém obchodního cestujícího použitím Hopfieldovy sítě. 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. 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. 5) 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ě (viz. 3.2). 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. DEMONSTRACE IMPLEMENTACE

Při implementaci se ukázala důležitost zvolení váhových konstant A, B, C a D. Po několika testech jsme určili: A = B = 2.1, C = 1 a D = 1.3.

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. 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 5. Při testech jsme pozorovali delší dobu řešení pro počet měst větší než 5. Podle literatury existují modifikace použitého algoritmu, které takovou nevýhodou netrpí. Jejich implementace je však již náročnější.

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