img125

125

Rozdział 10. Przykłady konkretnych zastosowań sieci neuronowych

10.2 Rozwiązywanie problemu komiwojażera

10.2.1 Opis problemu i programu symulującego sieć

W opisanych badanich realizowano symulacyjnie sieć opisaną przez Aiyera, Niraujana i Falliside jako modyfikacja koncepcji zaproponowanej przez Hopfielda i Tanka. Zastosowanych w badaniach program opiera się o zmodyfikowany model sieci TSP (por. rozdz. 7). Istnieje w nim możliwość zmiany parametrów A, A\,C, D.i⁶, At (z założenia A = B) oraz wyboru postaci funkcji /. Najczęściej przyjmowano funkcję w postaci

Przy pomocy parametrów Her i AfinAV można określić kryteria stopu dla iterowania sieci TSP. Her określa maksymalną liczbę iteracji. MinAV oznacza wartość, która powinna być większa od bezwzględnej wartości zmiany każdego z wyjść vxi w stanie uznanym za bliski ustalonego. Sprawił; określa okres sprawdzania kryterium stopu. Prohy — przy jej pomocy można podać ile razy jest rozwiązywany ten sam problem, za każdym razem sieć startuje z innego stanu początkowego i generowanego losowo.

W obecnej wersji programu nie ma możliwości ręcznego wprowadznia odległości pomiędzy miastami, problemy podlegające rozwiązywaniu mogą być generowane tylko automatycznie. Rodzaj generowanego problemu określa się przez podanie A^r i stwierdzenie, że problem ma być planarny (miasta leżą na płaszczyźnie, w kwadracie jednostkowym, odległości pomiędzy nimi są długościami łączących je odcinków) lub nieplanarny (dla każdych dwóch miast jest generowana liczba losowa określająca ich odległość). Każdy nowo wygenerowany problem jest najpierw rozwiązywany za pomocą zwykłych {nie neuronowych) algorytmów optymalizacji: heurystyki FITSP i algorytmów zwanych w literaturze 2-oplymalny i 3-optymalny. Następnie po otrzymaniu tych trzech rozwiązań, problem rozwiązywany jest za pomocą sieci TSP. Do podanej niżej statystyki są dołączane tylko rozwiązania tych problemów, dla których uzyskano co najmniej jedno rozwiązanie dopuszczalne siecią TSP. Statystyki są średnią arytmetyczną odpowiednio długości tras i czasów rozwiązywania. Liczona jest także średnia minimalna droga —jest to najkrótsza droga wyznaczona przez sieć TSP lub któryś z algorytmów klasycznych — dla danego problemu.

Celem badań hylo wykazanie podstawowych właściwości rozwiązań problemów optymalizacji uzyskiwanych za pomocą sieci neuronowych: jakości rozwiązania i jego niezawodności, wyrażającej się liczbą rozwiązań dopuszczalnych wśród rozwiązań proponowanych przez sieć. Dla zilustrowania pojawiających się tu problemów przedstawionio dalej i przeanalizowano dwa krańcowe przypadki- Warto dodać, że dla wybrania tych dwóch przypadków w rzeczywistości dokonano kilkuset symulacji rozważanych sieci i zebrano bardzo bogaty mclerial badawczy, którego pełna prezentacja nie jest tu jednak oczywiście możliwa. Pierwszy z opisanych eksperymantów by 1 w istocie powtórzeniem danych literaturowych, drugi stanowił oryginalny wynik uzyskany przez autora i współpracowników.

10.2.2 Wyniki eksperymentów

Przypadek 1. Modelowaną sieć charakteryzują następujące parametry (przyjęte wg. pracy