img095

95

Rozdział 7. Sieć Hop field a

możliwych!), a ponadto nowsze prace Van den Bouta i Millera [Bout88] proponują wybór efektywniejszej sieci i lepszego alagorytmu poszukiwania punktu równowagi.

Równocześnie zalety „neuronowego” rozwiązania są bezsporne — pracując współbieżnie neurony sieci mogą rozwiązać postawiony probierń w krótkim czasie mimo jego niewielo mianowej złożoności. Co więcej — wzrost wymiaru problemu będzie przy takiej realizacji wymagał rozbudowy sieci, ale nie będzie powodował wydłużenia czasu obliczeń¹, co jest perspektywą bardzo zachęcającą z punktu widzenia licznych zastosowań.

Kluczem do sukcesu przy stosowaniu sieci neuronowej w problemie TSP jest odnalezienie odpowiedniej reprezentacji danych. W opisanym przez Tanka rozwiązaniu problemu każde miasto reprezentowane jest za pomocą wiersza zawierającego n neuronów. W takim wierszu dokładnie jeden neuron powinien przyjmować wartość ,,1”, a wszystkie pozostałe mają sygnały wyjściowe odpowiadające wartości „0”. Pozycja (od 1 do «), na której występuje neuron sygnalizujący „1” odpowiada kolejności, w jakiej to właśnie miasto ma być odwiedzone przez wędrownego sprzedawcę. Tak więc jedynka na pierwszej pozycji oznacza miasto, które komiwojażer powinien odwiedzić jako pierwsze, jedynka na drugiej pozycji sygnalizuje drugie w kolejności odwiedzane miasto itd. Oczywiście z opisu tego wynika, że liczba wierszy musi odpowiadać liczbie rozważanych miast (czyli musi wynosić n), zatem łączna liczba potrzebnych neuronów wynosi n¹.

Każdy neuron w tej sieci musi być indeksowany dwoma wskaźnikami. Pierwszy z nich dotyczy numeru miasta, a drugi kolejności, w jakiej to miasto powinno być odwiedzane. Tak więc w tej sieci sygnał y_T{ oznaczać będzie sygnał wyjściowy z neuronu wchodzącego w skład wiersza odpowiadającego miastu numer x, przy czym neuron ten odpowiada i-tej pozycji w tym wierszu, czyli y_r,i — 1 oznacza, że x-te miasto należy odwiedzić w i-tej kolejności. Opisując funkcję „energii” minimalizowanej przez rozważaną sieć trzeba brać pod uwagę cztery jej składniki:

^Ei = ^A/¹ J2 YU2 V”

*    i    i*]

& = b/2    »-i

i    x    tyLr

Ei    =

x i

e<    = opEEE^ Vn (lfc.ł+1 +    1)

x    _:7tx    i

Składniki te mają następującą interpretację. E] ma zerową wartość wtedy i tylko wtedy, jeśli w każdym wierszu jest najwyżej jedna jedynka. Składnik ten można więc traktować jako „karę” za niedotrzymanie jednego z podstawowych warunków zadania — że każcie miasto ma mieć jednoznacznie określoną kolejność odwiedzin przez komiwojażera. Składnik E2 ma zerową wartość wtedy i tylko wtedy, gdy w każdej kolumnie (oznaczającej konkretny etap podróży) będzie najwyżej jedna jedynka. Jest to więc „kara” za naruszenie warunku jednoznacznego określenia, kiedy jakie miasto należy odwiedzić. Składnik £3 jest zerem wtedy i tylko wtedy, gdy w macierzy będzie dokładnie n jedynek. Wreszcie składnik E4

1

Oczywiścicw większej sieci na ogól dłużej będzie trwało dochodzenie do stanu równowagi, przeto w jakimś stopniu złożoność problemu będzie wpływała na wydłużenie czasu obliczeń — jednak oczywiście w stopniu nieporównanie mniejszym, niż ma to miejsce w typowych, szeregowych komputerach.