Zastosowanie zmodyfikowanej sieci Hopfielda w problemie komiwojażera

• Autorzy: Zbigniew Nagórny

Warianty tytułu

Application of a Modified Hopfield Network to the Travelling Salesman Problem

• Języki publikacji: PL

Abstrakty

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. (abstrakt oryginalny)

EN

The travelling salesman problem (TSP) is a classical example of a combinatorial optimization problem. The aim of this work is to find Hopfield network modifications, which could be efficiency used for solving the TSP. A novel method of auto-tuning of the network parameters is presented. This method ensures near optimal results for randomly generated instances of the 10-city TSP. The presented network is destined for hardware implementation, which could significantly decrease computation time in comparison with programs executed on sequential computers. (original abstract)

Słowa kluczowe

PL

Teoria podejmowania decyzji; Metoda sztucznych sieci neuronowych; Optymalizacja

EN

Decision making theory; Artificial neural networks method; Optimalization

• Czasopismo: Przegląd Prawno-Ekonomiczny
• Rocznik: 2010
• Numer: nr 13
• Strony: 73--80

Twórcy

autor

Zbigniew Nagórny

Bibliografia

• 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.^6 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 Cybernetics" 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:] Proceedings of the 2nd Conference Tools of Information Technology, Rzeszów 2007, http://www.teleinformatyka.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.