×

Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches. (English) Zbl 0944.90007

Summary: Unlike its cousin, the Euclidean Traveling Salesman Problem (TSP), to the best of our knowledge, there has been no documented all-neural solution to the Euclidean Hamiltonian Path Problem (HPP). The reason for this is the fact that the heuristics which map the cities onto the neurons “lose their credibility” because the underlying cyclic property of the order of the neurons used in the TSP is lost in the HPP. In this paper we present three neural solutions to the HPP. The first of these, \(\text{GSOM}_-\text{HPP}\), is a generalization of Kohonen’s self-organizing map (SOM) as modified by B. Angéniol et al. [Neural Networks 1, 289-293 (1988)]. The second and third methods use the recently-introduced self-organizing neural network, the Kohonen Network Incorporating Explicit Statistics (KNIES).
The primary difference between KNIES and Kohonen’s SOM is the fact that unlike SOM, every iteration in the training phase includes two distinct modules – the attracting module and the dispersing module. As a result of SOM and the dispersing module introduced in KNIES the neurons individually find their places both statistically and topologically, and also collectively maintain their mean to be the mean of the data points which they represent.
The new philosophy, which has previously [B. J. Oommen et al. Proceedings of WIRN/VIETRI-98, the Tenth Italian Workshop on Neural Nets, Vietri Sul Mare, Italy, May 1998. p. 273-282)] been used to effectively solve the Euclidean TSP, is now extended to solve the Euclidean HPP. These algorithms which are the first all-neural solutions to the HPP, have also been rigorously tested. Experimental results for problems obtained by modifying selected instances from the traveling salesman problem library (TSPLIB) [G. Reinelt. ORSA J. Comput. 3, 376-384 (1991; Zbl 0775.90293)] for the HPP indicate that they are both accurate and efficient. Apart from the computational results presented, the paper also contains a systematic strategy by which the quality of any HPP algorithm can be quantified.

MSC:

90B10 Deterministic network models in operations research
90C27 Combinatorial optimization

Citations:

Zbl 0775.90293

Software:

TSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Reinelt, G., TSPLIB - a traveling salesman problem library, ORSA Journal on Computing, 3, 376-384 (1991) · Zbl 0775.90293
[2] Papadimitriou CH, The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science. 1978; 4:237-44.; Papadimitriou CH, The Euclidean traveling salesman problem is NP-complete. Theoretical Computer Science. 1978; 4:237-44.
[3] Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, editors. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985.; Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, editors. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985.
[4] Reinelt G. The traveling salesman. Computational solutions for TSP applications. Berlin: Springer, 1994.; Reinelt G. The traveling salesman. Computational solutions for TSP applications. Berlin: Springer, 1994. · Zbl 0825.90720
[5] Lin, S.; Kernighan, B., An effective heuristic algorithm for the traveling salesman problem, Operations Research, 21, 498-516 (1973) · Zbl 0256.90038
[6] Cichocki A, Unbehauen R. Neural Networks for Optimization and Signal Processing. Chichester: Wiley, 1993.; Cichocki A, Unbehauen R. Neural Networks for Optimization and Signal Processing. Chichester: Wiley, 1993. · Zbl 0824.68101
[7] Johnson DS, McGeoch LA. The traveling salesman problem: a case study. In: Aarts E, Lenstra JK, Local search in combinatorial optimization. Chichester: Wiley, 1997.; Johnson DS, McGeoch LA. The traveling salesman problem: a case study. In: Aarts E, Lenstra JK, Local search in combinatorial optimization. Chichester: Wiley, 1997.
[8] Potvin, J.-. Y., The traveling salesman problem: a neural network perspective, ORSA Journal on Computing, 5, 328-348 (1993) · Zbl 0789.90086
[9] Oommen BJ, Aras N, Altinel K. Solving the travelling salesman problem using the Kohonen network incorporating explicit statistics. Preliminary version found in Proceedings of WIRN/VIETRI-98, the Tenth Italian Workshop on Neural Nets, Vietri Sul Mare, Italy, May 1998. p. 273-82. The complete paper is to appear in Neural Networks; Oommen BJ, Aras N, Altinel K. Solving the travelling salesman problem using the Kohonen network incorporating explicit statistics. Preliminary version found in Proceedings of WIRN/VIETRI-98, the Tenth Italian Workshop on Neural Nets, Vietri Sul Mare, Italy, May 1998. p. 273-82. The complete paper is to appear in Neural Networks
[10] Ascheuer N. Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. Technical Report No. TR 96-3, ZIB, Berlin, Germany, 1996.; Ascheuer N. Hamiltonian path problems in the on-line optimization of flexible manufacturing systems. Technical Report No. TR 96-3, ZIB, Berlin, Germany, 1996. · Zbl 0859.90080
[11] Waterman MS. Introduction to computational biology. Cambridge: Chapman & Hall, 1995.; Waterman MS. Introduction to computational biology. Cambridge: Chapman & Hall, 1995.
[12] Jeffries, C.; Niznik, T., Easing the Conscience of the guilty net, Computers and Operations Research, 21, 961-968 (1994) · Zbl 0815.90132
[13] Angéniol, B.; Vaubois, C.; Le Texier, J. Y., Self-organizing feature maps and the traveling salesman problem, Neural Networks, 1, 289-293 (1988)
[14] Hopfield, J. J.; Tank, D. W., Neural computation of decisions in optimization problems, Biological Cybernetics, 52, 141-152 (1985) · Zbl 0572.68041
[15] Aiyer, S. V.B.; Niranjan, M.; Fallside, F., A theoretical investigation into the performance of the Hopfield model, IEEE Transactions on Neural Networks, 1, 2, 204-215 (1990)
[16] Durbin, R.; Willshaw, D., An analogue approach to the traveling salesman problem using an elastic net method, Nature, 326, 689-691 (1987)
[17] Simic, P. D., Statistical mechanics as the underlying theory of elastic and neural optimization, Network, 1, 363-374 (1990)
[18] Vakhutinsky, A. I.; Golden, B. L., A hierarchical strategy for solving traveling salesman problem using elastic nets, Journal of Heuristics, 2, 67-76 (1995) · Zbl 0857.90132
[19] Gray, D. H., Vector Quantization, IEEE ASSP Magazine, 1, 4-29 (1984)
[20] Kohonen, T., The self-organizing map, Proceedings of IEEE, 78, 74-90 (1990)
[21] Kohonen T, Self-organizing maps. Berlin: Springer, 1995.; Kohonen T, Self-organizing maps. Berlin: Springer, 1995. · Zbl 0866.68085
[22] Linde Y, Buzo A, Gray RM. An Algorithm for Vector Quantization, IEEE Trans. Communication 1980; COM-28, 61-71.; Linde Y, Buzo A, Gray RM. An Algorithm for Vector Quantization, IEEE Trans. Communication 1980; COM-28, 61-71.
[23] Makhoul, J.; Roucos, S.; Gish, H., Vector quantization in speech coding, Proceedings of IEEE, 73, 1551-1588 (1985)
[24] Duda RO, Hart PE. Pattern classification and scene analysis. Chichester: Wiley, 1973.; Duda RO, Hart PE. Pattern classification and scene analysis. Chichester: Wiley, 1973. · Zbl 0277.68056
[25] Fukunaga K. Introduction to statistical pattern recognition, 2nd ed., San Diego: Academic Press, 1990.; Fukunaga K. Introduction to statistical pattern recognition, 2nd ed., San Diego: Academic Press, 1990. · Zbl 0711.62052
[26] Wong, Y., A comparative study of the Kohonen self-organizing map and the elastic net, Computational Learning Theory and Natural Learning Systems, 2, 401-413 (1996)
[27] Ritter, H. J., Asymptotic level density for a class of vector quantization processes, IEEE Transaction on Neural Networks, 2, 173-175 (1991)
[28] Zador, P. L., Asymptotic quantization of error of continuous signals and the quantization dimension, IEEE Transaction on Information Theory, 28, 139-149 (1982) · Zbl 0476.94008
[29] Kohonen T, Makisara K, Saramaki T. Phonotic maps – insightful representation of phonological features for speech recognition. Proceedings of Seventh International Conference on Pattern Recognition, 1984. p. 182-5.; Kohonen T, Makisara K, Saramaki T. Phonotic maps – insightful representation of phonological features for speech recognition. Proceedings of Seventh International Conference on Pattern Recognition, 1984. p. 182-5.
[30] Kohonen T, Torkkola K, Shozokai M, Kangas J, Venta O. Microprocessor implementation of a large vocabulary speech recognizer and phonetic typewriter for Finnish and Japanese. Proceedings of European Conference of Speech Technology, 1987. p. 377-80.; Kohonen T, Torkkola K, Shozokai M, Kangas J, Venta O. Microprocessor implementation of a large vocabulary speech recognizer and phonetic typewriter for Finnish and Japanese. Proceedings of European Conference of Speech Technology, 1987. p. 377-80.
[31] Kohonen, T., The neural phonotic typewriter, Computer, 21, 11-22 (1988)
[32] Samarabandu JK, Jakubowicz OE. Principles of sequential feature maps in multi-level problems. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC II-683-II-686, 1990.; Samarabandu JK, Jakubowicz OE. Principles of sequential feature maps in multi-level problems. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC II-683-II-686, 1990.
[33] Orlando GA, Mann R, Haykin S. Radar classification of sea-ice using traditional and neural classifiers. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC, 1990. p. II-263-II-266.; Orlando GA, Mann R, Haykin S. Radar classification of sea-ice using traditional and neural classifiers. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC, 1990. p. II-263-II-266.
[34] Neumann EK, Wheeler DA, Burnside AS, Bernstein AS, Hall JC. A technique for the classification and analysis of insect courtship song. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC, 1990. p. II-257-II-262.; Neumann EK, Wheeler DA, Burnside AS, Bernstein AS, Hall JC. A technique for the classification and analysis of insect courtship song. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC, 1990. p. II-257-II-262.
[35] Marks KM, Goser KF. Analysis of VLSI process data based on self-organizing feature maps. Proceedings of Nuero-Nimes’88, 1988. p. 337-47.; Marks KM, Goser KF. Analysis of VLSI process data based on self-organizing feature maps. Proceedings of Nuero-Nimes’88, 1988. p. 337-47.
[36] Tryba, V.; Marks, K. M.; Rütcker, U.; Goser, K., Selbst-organizierende Karten Als Lernende Klassifizierende Speicher, IFG Fachbericht, 102, 407-419 (1988)
[37] Hemani A, Postula A. Scheduling by self organization. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC, 1990. p. II-543-II-548.; Hemani A, Postula A. Scheduling by self organization. Proceedings of International Joint Conference on Neural Networks, IJCNN-90-WASH-DC, 1990. p. II-543-II-548.
[38] Graf DH, Lalonde WR. A neural controller for collision-free movement of general robot manipulators. Proceedings of IEEE International Conference on Neural Networks, 1988. p. 177-84.; Graf DH, Lalonde WR. A neural controller for collision-free movement of general robot manipulators. Proceedings of IEEE International Conference on Neural Networks, 1988. p. 177-84.
[39] Graf DH, Lalonde WR. Neuroplanners for hand/eye coordination. Proceedings of International Joint Conference on Neural Networks, 1989. p. II-543-II-548.; Graf DH, Lalonde WR. Neuroplanners for hand/eye coordination. Proceedings of International Joint Conference on Neural Networks, 1989. p. II-543-II-548.
[40] Martinetz, J.; Ritter, H. J.; Schulten, K. J., Three-dimensional neural net for learning visuomotor coordination of a robot arm, IEEE Transactions on Neural Networks, 1, 131-136 (1990)
[41] Ritter, H. J.; Martinetz, J.; Schulten, K. J., Topology conserving maps learning visuomotor coordination, Neural Network, 2, 159-168 (1989)
[42] Ritter HJ, Schulten KJ. Topology conserving mapping for learning motor tasks. Proceedings of Neural Networks for Computing, AIP Conference, 1986. p. 376-80.; Ritter HJ, Schulten KJ. Topology conserving mapping for learning motor tasks. Proceedings of Neural Networks for Computing, AIP Conference, 1986. p. 376-80.
[43] Ritter HJ, Schulten KJ. Extending Kohonen’s self-organizing mapping to learn ballistic movements. NATO; Ritter HJ, Schulten KJ. Extending Kohonen’s self-organizing mapping to learn ballistic movements. NATO
[44] Fort JC. Solving a combinatorial problem via self-organizing process: an application of the Kohonen algorithm to the traveling salesman problem. Biological Cybernetics 59:33-40.; Fort JC. Solving a combinatorial problem via self-organizing process: an application of the Kohonen algorithm to the traveling salesman problem. Biological Cybernetics 59:33-40. · Zbl 0641.92020
[45] Hueter GJ. Solution of the traveling salesman problem with an adaptive ring. Proceedings of the IEEE International Conference on Neural Networks, San Diego, CA, 1988. p. I-85-92.; Hueter GJ. Solution of the traveling salesman problem with an adaptive ring. Proceedings of the IEEE International Conference on Neural Networks, San Diego, CA, 1988. p. I-85-92.
[46] Ritter HJ, Schulten KJ. Kohonen’s self-organizing maps: exploring their computational capabilities. Proceedings of the International Joint Conference on Neural Networks, 1988. p. 2455-60.; Ritter HJ, Schulten KJ. Kohonen’s self-organizing maps: exploring their computational capabilities. Proceedings of the International Joint Conference on Neural Networks, 1988. p. 2455-60.
[47] Burke, L. I.; Damany, P., The guilty net for the traveling salesman problem, Computers & Operations Research, 19, 255-265 (1992) · Zbl 0757.90081
[48] Burke, L. I., Neural methods for the traveling salesman problem: insights from operations research, Neural Networks, 7, 681-690 (1994) · Zbl 0820.90111
[49] Burke, L. I., Conscientious’ neural nets for tour construction in the traveling salesman problem: the vigilant net, Computers & Operations Research, 23, 121-129 (1996) · Zbl 0868.90129
[50] Budinich, M., A self-organizing neural network for the traveling salesman problem that is competitive with simulated annealing, Neural Computation, 8, 416-424 (1996)
[51] Budinich M, Rosario B. A neural network for the traveling salesman problem with a well behaved energy function In: Ellacott SW, Mason JC, Anderson IJ, editors. Mathematics of Neural Networks, Models, Algorithms and Applications. Boston: Kluwer Academic Publishers, 1997.; Budinich M, Rosario B. A neural network for the traveling salesman problem with a well behaved energy function In: Ellacott SW, Mason JC, Anderson IJ, editors. Mathematics of Neural Networks, Models, Algorithms and Applications. Boston: Kluwer Academic Publishers, 1997.
[52] Ascheuer N. Private communication. 1998.; Ascheuer N. Private communication. 1998.
[53] Fisher, R.; Tippet, L., Limiting forms of the frequency distribution of the largest or smallest number of a sample, Proceedings of Cambridge Philosophical Society, 24, 180-191 (1928) · JFM 54.0560.05
[54] Derigs, U., Using confidence limits for the global optimum in combinatorial optimization, Operations Research, 33, 1024-1049 (1985) · Zbl 0587.90070
[55] Golden B, Alt FB. Interval estimation of a global optimum for large combinatorial problems. Naval Research Logistics Quarterly 1979;26:69-77.; Golden B, Alt FB. Interval estimation of a global optimum for large combinatorial problems. Naval Research Logistics Quarterly 1979;26:69-77. · Zbl 0397.90100
[56] Golden B, Stewart WR. Empirical analysis of heuristics. In: Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, editors. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985.; Golden B, Stewart WR. Empirical analysis of heuristics. In: Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB, editors. The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985.
[57] Los, M.; Lardinois, C., Combinatorial programming, statistical optimization and the optimal transportation network problem, Transactions Research, 16B, 89-124 (1982)
[58] Zanakis, S. H., Extended pattern search with transformation for the three-parameter Weibull MLE problem, Management Science, 25, 1149-1161 (1979) · Zbl 0474.62091
[59] Cooke, P., Statistical inference for bounds of random variables, Biometrika, 66, 367-374 (1979) · Zbl 0406.62011
[60] Dannenbring, D., Estimating optimal solutions for large combinatorial problems, Management Science, 23, 1273-1283 (1977) · Zbl 0377.90051
[61] Zanakis, S. H., A simulation study of some simple estimators of the three-parameter Weibull distribution, Journal of Statistical Computation and Simulation, 9, 101-106 (1979) · Zbl 0416.62025
[62] Hertz J, Krogh A, Palmer RG. Introduction to the theory of neural computation. A Lecture Notes Volume in the Santa Fe Institute Studies in the Sciences of Complexity. Reading, MA: Addison-Wesley, 1991.; Hertz J, Krogh A, Palmer RG. Introduction to the theory of neural computation. A Lecture Notes Volume in the Santa Fe Institute Studies in the Sciences of Complexity. Reading, MA: Addison-Wesley, 1991.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.