2.1.1 Problém obchodného cestujúceho (TSP)
Majme danú mno¾inu
miest a vzdialenosť
pre v¹etky dvojice miest
.
Potrebujeme zistiť, v akom
poradí má obchodný cestujúci prechádzať mestá tak, aby sa
vrátil do mesta, z ktorého vyrazil a zároveò ka¾dé mesto na
trase nav¹tívil práve jedenkrát. Podmienkou v¹ak je, ¾e
vzdialenosť, ktorú precestoval, je najkrat¹ia mo¾ná. Rie¹enie tohto problému je prípustné, ak sú splnené
nasledujúce obmedzenia :
- obchodný cestujúci prechádza ka¾dým mestom práve
jedenkrát,
- jeho cesta v grafe tvorí cyklus.
Prípustnosť rie¹enia je teda daná nájdením
hamiltonovskej kru¾nice a mieru optimality rie¹enia
popisuje súèet vzdialeností medzi mestami na hamiltonovskej
kru¾nici.
Neurónová sieť, ktorá tento problém rie¹i, musí
vyjadriť pre dané mesto, ktoré mesto mu predchádza a ktoré
mesto za ním nasleduje. Toto je vyjadriteľné v sieti s
neurónmi pri maticovom usporiadaní uvedenom na obr. 2.2
Obrázok 2.2:
Návrh neurónovej siete pre TSP pri
.
Kvôli
prehľadnosti nie sú zakreslené prepojenia neurónov.
Rie¹enie je zobrazené pomocou èiar. Rie¹ením je
postupnosť miest 4-2-1-3, prípadne jej cyklická
premutácia.
 |
Je zrejmé, ¾e usporiadanie v tomto tvare pomáha pri pochopení
rie¹enia, inak je nepodstatné. Vzťah pre energiu siete
je mo¾né upraviť pomocou zavedenia dvoch indexov pre
jeden neurón. Jedná sa len o technickú úpravu vzťahu,
význam zostane nezmenený.
Teraz sformulujeme túto úlohu pomocou novej
sústavy dvojstavových premenných tak, aby hľadanie
prípustného rie¹enia mohlo byť vyjadrené ako
minimalizácia funkcie týchto nových premenných.
Zadefinujme maticu
typu
s prvkami
,
ktoré
nadobúdajú hodnoty
alebo
,
pre
.
vtedy, keď obchodný cestujúci prechádza
mestom
v
-tom kroku. V opaènom prípade
.
V podstate hodnoty
sú ekvivalentom hodnotám
neurónov
.
Prípustnému rie¹eniu pôvodnej úlohy teraz zodpovedá stav
matice, ktorý sa dá popísať nasledovne :
- v ka¾dom riadku je najviac jedna jednièka, tj. pre
x-te mesto platí
,
ak
,
- v ka¾dom ståpci je najviac jedna jednièka, tj. pre
x-ty krok obchodného cestujúceho platí
,
ak
,
- v matici je práve
jednièiek, tj.
,
- súèet vzdialeností medzi mestami je urèený maticou
vzdialeností, prièom celková då¾ka cesty je
Teraz vytvoríme funkcie
a
,
ktoré nadobúdajú minimálne hodnoty pri splnení predchádzajúcich
podmienok. Funkcie sú vytvárané na základe vzťahov
uvedených v týchto podmienkách.
 |
(2.7) |
 |
(2.8) |
 |
(2.9) |
 |
(2.10) |
Vo vzťahoch (2.7) - (2.10) A, B, C a D sú voliteľné parametre.
Tak¾e rie¹enie je optimálne, ak
nadobúda svoje minimum. Na tomto mieste je vhodné pripomenúť si,
ako vyzerá energetická funkcia pre diskrétny model Hopfieldovej siete pri
maticovom oèíslovaní neurónov:
 |
(2.11) |
Prepísaním (2.7),(2.8),(2.9) a (2.10) na tvar energetickej funkcie (2.11)
dosiahneme to, ¾e tvar "na¹ej" funkcie
bude
ekvivalentný tvaru funkcie
,
ktorá sa poèas konvergencie
siete minimalizuje (základná vlastnosť Hopfieldovej siete).
Po tomto prepísaní nám teda bude staèiť
porovnať výsledky s (2.11) a ľahko vypoèítame nastavenie
váh a prahov. Nasledujúce úpravy spoèívajú v zavedení
symbolu Croneckerovo delta, tj.
,
ak
,
inak
,
èo nám umo¾ní doplniť do
niektorých výrazov ďal¹ie sumy.
Z (2.7) vyplýva
 |
(2.12) |
Výraz
je rovný
,
ak
alebo
.
 |
(2.13) |
Tento výraz je vlastne výraz (2.11), kde
 |
(2.14) |
Analogicky z (2.8) dostaneme
 |
(2.15) |
Z (2.9) dostaneme
 |
(2.16) |
Po prenásobení výrazu v zátvorke výrazom
dostaneme
 |
(2.17) |
Preto¾e posledný èlen
nezmení polohu minima
vy¹¹ie uvedenej funkcie
,
zanedbáme ho a dostávame
 |
(2.18) |
Zo (2.10) vyplýva
 |
(2.19) |
prièom platí, ¾e
,
ak
.
Zavedením
Croneckerovho symbolu
a nahradením indexu
indexom
vo výraze pre
dostávame
 |
(2.20) |
,
ak
.
Polo¾íme
v prvej èasti výrazu a
v druhej
èasti a dostaneme
 |
(2.21) |
 |
(2.22) |
 |
(2.23) |
Tak¾e nakoniec pre nastavenie váh prepojení v sieti
medzi neurónmi
a
bude platiť
 |
(2.24) |
 |
(2.25) |
Po odvodení vy¹¹ie uvedených vzťahov mo¾eme
uviesť nasledujúci algoritmus:
ALGORITMUS pre TSP:
Krok 1. Priradenie váh prepojeniam
pre
,
- A,B,C,D sú zvolené parametre siete (sú meniteľné),
Krok 2. Inicializácia
,
pre
,
V tejto formule
je výstup vrcholu ,,ij'' v èase
a
je náhodná premenná, ktorá nadobúda hodnotu 0 alebo 1.
Krok 3. Iterácia pokiaľ sieť neskovergovala
pre
.
Krok konèí, ak sieť skonvergovala, tj. jej stav sa
u¾ nemení. Tu mô¾e dôjsť k zacykleniu siete.
Krok 4. Opakovanie od kroku 2.
Ak do¹lo k zacykleniu siete, je potrebný nový výpoèet
zaèínajúci nastavením nových poèiatoèných
hodnôt siete. Tie¾ je mo¾né zmeniť parametre siete
a nastaviť nové váhy, tj. zaèať krokom 1.