Zastosowanie zmodyfikowanej sieci Hopfielda w problemie komiwojażera
Zbigniew Nagórny
Katolicki Uniwersytet Lubelski Jana Pawła II , PolskaAbstrakt
Problem komiwojażera jest klasycznym problemem kombinatorycznym. Celem niniejszej pracy jest znalezienie modyfikacji sieci Hopfielda, które umożliwiłyby poprawę skuteczności sieci w przypadku zastosowania sieci do rozwiązania problemu komiwojażera. W pracy przedstawiono oryginalną metodę automatycznego doboru parametrów sieci Hopfielda. Powyższa metoda umożliwia otrzymanie rozwiązań o bardzo dobrej jakości dla losowo wygenerowanych problemów o liczbie miast równej 10, otrzymane rozwiązania są bliskie optymalnemu rozwiązaniu. Sieć Hopfielda przedstawiona w niniejszej pracy jest przeznaczona do sprzętowej realizacji. Zastosowanie sprzętowej realizacji sieci umożliwiłoby znaczne skrócenie czasu obliczeń, w porównaniu do metod wykorzystujących komputery oparte na architekturze von Neumanna.
Słowa kluczowe:
Automatyczny dobór parametrów, NP- trudny, optymalizacja kombinatoryczna, problem komiwojażera, sieć HopfieldaBibliografia
Brandt R.D., Wang Y., Laub A.J., Mitra S.K., Alternative networks for solving the traveling salesman problem and the list-matching problem, [w:] Proceeding of the International Joint Conference on Neural Networks 1988, vol. 2.
Dorigo M., Gambardella L.M., Ant colonies for the travelling salesman problem, “BioSystems” 1997, vol. 43.
Durbin R., Willshaw D., An analogue approach to the travelling salesman problem using an elastic net method, “Nature” 1987, vol. 326.
Hopfield J.J., Tank D.W., “Neural” computation of decisions in optimization problems, “Biological Cy- bernetics” 1985, vol. 52.
Kirkpatrick S., Gelatt C.D., Jr., Vecchi M.P., Optimization by simulated annealing, “Science” 1983, vol. 220.
Kos A., Nagórny Z., Modified Hopfield Neural Network for Travelling Salesman Problem, [w:] Pro- ceedings of the 2nd Conference Tools of Information Technology, Rzeszów 2007, http://www.te- leinformatyka.net.pl/nti/papers/Kos_Nagorny_NTI_2007.pdf (28.10.2010).
Mańdziuk J., Sieci neuronowe typu Hopfielda. Teoria i przykłady zastosowań, AOW EXIT, Warszawa 2000.
Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa 1996.
Michalewicz Z., Fogel D.B., How to solve it: modern heuristics, Springer, Berlin–New York 2004.
Tadeusiewicz R., Sieci neuronowe, AOW, Warszawa 1993.
Wilson G.V., Pawley G.S., On the stability of the travelling salesman problem algorithm of Hopfield and Tank, “Biological Cybernetics” 1988, vol. 58.
Katolicki Uniwersytet Lubelski Jana Pawła II
Licencja
Utwór dostępny jest na licencji Creative Commons Uznanie autorstwa 4.0 Międzynarodowe.
Utwór dostępny jest na licencji Creative Commons Uznanie autorstwa 4.0 Międzynarodowe.
