img094

94

7.8. Rozwiązywanie problemu komiwojażera

Jak wiadomo działanie sieci polega na minimalizowaniu funkcji „energii”. Efekt tego działania w rozważanej sieci łatwo sobie wyobrazić. Pierwszy składnik przytoczonego wzoru może być traktowany jako suma kwadratów błędów popełnianych przez sieć (rozbieżność między wartością X, a wartością binarnego kodu formowanego przez sygnały j/*)). Drugi składnik natomiast osiąga małe wartości przy przyjmujących wartości binarne (0 lub 1), natomiast przy innych f/M wartość tego składnika wzrasta stanowiąc „karę” za niewłaściwe wartości wyjść sieci. W sumie minimalizacja wskazanej funkcji energii doprowadzi do tego, że na wyjściach sieci pojawią się sygnały yW zbliżone do wartości binarnych kodujące (zgodnie z zasadami arytmetyki dwójkowej) wartość wejściowego sygnału X. Jak wynika z porówanania przytoczonego wyżej wzoru określającego funkcję „energii” w rozważanej sieci z wcześniej opisanym wzorem ogólnym — współczynniki wagowe ustalone w rozważanej sieci wyrazić można wzorami:

ujU) =

u#> = 2^j

Udana budowa i efektywna eksploatacja opisanej sieci (Tank86] potwierdziły, że sieci Hopfielda mogą być użyte do realizacji konkretnych zadań przetwarzania informacji — chociaż oczywiście przetwornik A/C można zbudować znacznie prościej bez korzystania z sieci.

7.8 Rozwiązywanie problemu komiwojażera

Podobny charakter — efektownego zastosowania sieci do rozwiązania zadania możliwego do rozwiązania także innymi metodami, przyniosła słynna praca Van den Bouta i Millera [Bout88], pokazująca zastosowanie sieci Hopfielda do rozwiązania klasycznego problemu optymalizacyjnego — tak zwanego „problemu komiwojażera”, oznaczanego zwykle jako TSP (Traveling Salesman Problem). Problem ten polega na ustaleniu optymalnej trasy objazdu n miast przez wędrownego sprzedawcę, który musi być we wszystkich miastach przynajmniej raz i chce oczywiście wydać jak najmniej na same podróże. Jako dane przy rowiązywaniu problemu podane są odległości r/,j pomiędzy wszystkimi miastami, a koszt podróży sprzedawcy równy jest długości sumarycznej przebytej przez niego drogi.

Problem ten —jak udowodnili Garley i Johnson w 1979 roku — należy do zadań NP-zupelnych, czyli czas jego rozwiązywania rośnie wykładniczo przy wzroście liczby rozważanych miast n. Istotnie, przy « miastach możliwe jest zbudowanie D = n!/(2n) rozróżnialnych tras. Nawet przy niewielkich wartościach n jest bardzo dużo ewentualności do rozważenia i zbadania (np. dla n = 60 D = 69,34155 10^7rt) licznych zadań optymalizacji konibinatorycz-nej i dlatego metody rozwiązywania problemu komiwojażera są w centrum uwagi badaczy zajmujących się metodami optymalizacji i teorią badań operacyjnych. Istnieje uzasadnione przypuszczenie, że metody zastosowane do rozwiązywania problemu komiwojażera mogą niemal natychmiast znaleźć zastosowanie przy rozwiązywaniu innych problemów kombina-torycznych. Opisana niżej technika rozwiązywania tego problemu z wykorzystaniem sieci neuronowej typu Hopfielda nie jest wolna od wad — w szczególności przy jego rozwiązywaniu sieć łatwo ulega „wciąganiu” przez lokalne minima, co prowadzi do rozwiązań suboptymal-nych. Jednak zdarza się to stosunkowo rzadko (w pracach Tanka [Tank85] referowane są eksperymenty, podczas których sieć rozwiązująca problem TSP dla 10 miast w 16 przypadkach na 20 podejmowanych prób znalazła optymalną marszrutę (wybraną spośród 181 440