Optymalizacja z wykorzystaniem zmodyfikowanej sieci Hopfielda

• Autorzy: Nagórny Z. , Kos A.

Warianty tytułu

EN

Optimization by using a modified hopfield network

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono oryginalną metodę rozwiązywania problemów optymalizacyjnych z wykorzystaniem zmodyfikowanej sieci neuronowej typu Hopfielda. W klasycznym rozwiązaniu wartości wag połączeń między neuronami w sieci Hopfielda są obliczane przed symulacją i nie ulegają zmianie. W niniejszej pracy zbadano wpływ modyfikacji wartości sygnałów wejściowych neuronów lub wag podczas symulacji sieci, na otrzymywane rozwiązania. Zauważono, że modyfikacja sygnałów wejściowych lub wag umożliwia uzyskanie lepszych rozwiązań. W pracy przedstawiono rezultaty otrzymane zmodyfikowaną siecią dla problemu komiwojażera. Dla problemów o wymiarze równym 10, sieć dla 100% prób generowała optymalne rozwiązanie. Dla większych problemów rozwiązania są lepsze od otrzymanych klasyczną siecią. Przedstawiono wnioski płynące z zastosowania opisanej metody.

EN

The paper presents a novel method for solving optimization problems by using a modified Hopfield network. In a conventional Hopfield network weight values of the net are calculated before simulation and are constant. Our method is a novel method, because the values of input signals or weights are modified during simulation. The method makes use of the Hopfield net with continuous function of neurons according to Eq. (2). The model Hopfield net in electronic components is shown in Figure 1. An energy function of the neural net is described by Eq. (3). Comparing Eq. (3) and Eq. (4), which is a general form of an optimization problem cost function, we get weight and external input signal values. The Hopfield net is implemented in software in this work. A simulating program makes use of Eq. (11) to calculate the input of each neuron in the net. During the simulation the input signals are modified in accordance with Eq. (12). The duration of input signals modifying is defined by a random value nnar. Finally, a number of iterations to achieve a stable state of the net are done. A number of trials are performed for each optimization problem and the best results are chosen. Figure 2 shows the algorithm of the method. In this work, simulations were done for six examples of the travelling salesman problem. A cost function of the travelling salesman problem is described by Eq. (17). This function consists of four components: the total length of the salesman's tour, two terms, which ensure that the salesman's tour is valid and the term, which forces neurons to have the output signal equal zero or one. The method with input signal values modifying during simulation gives better results than the conventional one. Results are performed in Table 1 and 2. For ten-city problems the modified Hopfield net finds the optimal solution with 100% success rate. Some conclusions coming from using this method are presented.

Słowa kluczowe

PL

optymalizacja; sieć neuronowa; sieć Hopfielda; funkcja energii; problem komiwojażera

EN

optimization; neural network; Hopfield net; energy function; travelling salesman problem

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2005
• Tom: Vol. 51, z. 2
• Strony: 255--275
• Opis fizyczny: Bibliogr. 28 poz., tab., wykr., rys.

Twórcy

autor

Nagórny Z.

• Studium Generale Sandomiriense, Wyższa Szkoła Humanistyczno-Przyrodnicza w Sandomierzu, ul. Krakowska 26, 27-600 Sandomierz

autor

Kos A.

• Akademia Górniczo-Hutnicza w Krakowie, Katedra Elektroniki, al. Mickiewicza 30, 30-059 Kraków

Bibliografia

• 1. A. Kos: Modelowanie hybrydowych układów mocy i optymalizacja ich konstrukcji ze względu na rozkład temperatury. Kraków, Wydawnictwa AGH, 1994.
• 2. P. Bratek, A. Kos: Complex optimisation of topology of VLSI circuits with self-organising neural nets. Proc, of the Mixed Design of Integrated Circuits and Systems, Łódź (Poland), June 1996, pp. 78-83.
• 3. H. Mączka, P. Dziurdzia, A. Kos: Neural algorithm for minimisation of total length of connections in VLSI circuits. Proc, of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. II/319-324.
• 4. P. Bratek, А. Коs: Self-organising neural computations for optimisation of IC topography in thermal aspect. Proc, of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. H/627-632.
• 5. M. Gajęcki, A. Kos: A problem of optimization of topography of VLSI circuit. Proc, of the XIXth National Conference on Circuit Theory and Electronic Networks, Kraków-Krynica (Poland), October 1996, pp. 11/307-312.
• 6. J.J. Hopfield, D. W. Tank: “Neural” computation of decisions in optimization problems. Biological Cybernetics 1985, vol. 52, pp. 141-152.
• 7. R. Tadeusiewicz: Sieci neuronowe. Warszawa, Akademicka Oficyna Wydawnicza, 1993.
• 8. J. Mańdziuk: Sieci neuronowe typu Hopfielda. Teoria i przykłady zastosowań. Warszawa, Akademicka Oficyna Wydawnicza EXIT, 2000.
• 9. J. Hertz, A. Krogh, R. G. Palmer: Wstęp do teorii obliczeń neuronowych. Warszawa, WNT, 1995.
• 10. J. A. Freeman, D. M. Skapura: Neural networks: algorithms, applications, and programming techniques. Addison-Wesley Publishing Company, 1991.
• 11. T. Khanna: Foundations of neural networks. Addison-Wesley Publishing Company, 1990.
• 12. J. Żurada, M. Barski, W. Jędruch: Sztuczne sieci neuronowe. Warszawa, Wydawnictwo Naukowe PWN, 1996.
• 13. G. A. Tagliarini, J. F. Christ, E. W. Page: Optimization using neural networks. IEEE Transactions on Computers 1991, vol. 40, no. 12, pp. 1347-1358.
• 14. H. Kwaśnicka: Efficiency of selected meta-heuristics applied to the TSP problem: a simulation study. TASK Quarterly 2003, vol. 7, no. 1, pp. 73-91.
• 15. A. Hemani, A. Postula: Cell placement by self-organisation. Neural Networks 1990, vol. 3, pp. 377-383.
• 16. R. Durbin, D. Willshaw: An analogue approach to the travelling salesman problem using an elastic net method. Nature 1987, vol. 326, pp. 689-691.
• 17. I. Tokuda, T. Nagashima, K. Aihara: Global bifurcation structure of chaotic neural networks and its application to traveling salesman problems. Neural Networks 1997, vol. 10, no. 9, pp. 1673-1690.
• 18. S. Kirkpatrick, C. D. Gelatt, Jr., M. P. Vecchi: Optimization by simulated annealing. Science 1983, vol. 220, no. 4598, pp. 671-680.
• 19. C. I. Park: Predicting the annealing range by computing critical temperature in mean field anne­aling for the traveling salesman problem. Artificial Neural Networks, Proceedings of the 1991 International Conference on Artificial Neural Networks, Amsterdam, North-Holland, 1991, pp. 1019-1024.
• 20. D. E. Van den Bout, T. K. Miller III: Improving the performance of the Hopfield-Tank neural network through normalization and annealing. Biological Cybernetics 1989, vol. 62, pp. 129-139.
• 21. X. Xu, W. T. Tsai: Effective algorithms for the traveling salesman problem. Neural Networks 1991, vol. 4, pp. 193-205.
• 22. G. V. Wilson, G. S. Pawley: On the stability of travelling salesman problem algorithm of Hopfield and Tank. Biological Cybernetics 1988, vol. 58, pp. 63-70.
• 23. S. Z. L i: Improving convergence and solution quality of Hopfield-type neural networks with augmented Lagrange multipliers. IEEE Transactions on Neural Networks 1996, vol. 7, no. 6, pp. 1507-1516.
• 24. B. Kamgar-Parsi, B. Kamgar-Parsi: On problem solving with Hopfield neural ne­tworks. Biological Cybernetics 1990, vol. 62, no. 5, pp. 415-423.
• 25. A. R. Bizzarri: Convergence properties of a modified Hopfield-Tank model. Biological Cybernetics 1991, vol. 64, no. 4, pp. 293-300.
• 26. D. Rutkowska, M. Piliński, L. Rutkowski: Sieci neuronowe, algorytmy genetycz­ne i systemy rozmyte. Warszawa, Wydawnictwo Naukowe PWN, 1997.
• 27. A. Kos, Z. Nagórny: Minimalizacja długości połączeń w układach elektronicznych z wykorzystaniem sieci Hopfielda. Kwartalnik Elektroniki i Telekomunikacji, praca przyjęta do druku 2005, z. 1.
• 28. G. Reinell: Traveling salesman problem library. Internet: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/