Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches

Unlike its cousin, the Euclidean Traveling Salesman Problem (TSP), to the b est of our knowledge, there has been no documented all-neural solution to t he Euclidean Hamiltonian Path Problem (HPP). The reason for this is the fac t that the heuristics which map the cities onto the neurons "lose their cre dibility" because the underlying cyclic property of the order of the neuron s used in the TSP is lost in the HPP. In this paper we present three neural solutions to the HPP. The first of these, GSOM_HPP, is a generalization of Kohonen's self-organizing map (SOM) as modified by Angeniol et al. (Neural Networks 1988;1:289-93). The second and third methods use the recently-int roduced self-organizing neural network, the Kohonen Network Incorporating E xplicit Statistics (KNIES) (Oommen et al., Proceedings of WIRN/VIETRI-98, t he Tenth Italian Workshop on Neural Nets, Vietri Sul Mare, Italy, May 1998. p. 273-282). The primary difference between KNIES and Kohonen's SOM is the fact that unlike SOM, every iteration in the training phase includes two d istinct modules - the attracting module and the dispersing module. As a res ult of SOM and the dispersing module introduced in KNIES the neurons indivi dually find their places both statistically and topologically, and also col lectively maintain their mean to be the mean of the data points which they represent. The new philosophy, which has previously (Oommen et al. Proceedi ngs of WIRN/VIETRI-98, the Tenth Italian Workshop on Neural Nets, Vietri Su l Mare, Italy, May 1998. p. 273-282) been used to effectively solve the Euc lidean Traveling Salesman Problem (TSP), is now extended to solve the Eucli dean Hamiltonian Path (HPP). These algorithms which are the first all-neura l solutions to the HPP, have also been rigorously tested. Experimental resu lts for problems obtained by modifying selected instances from the travelin g salesman problem library (TSPLIB) (Reinett. ORSA Journal on Computing 199 1;3:376-84) 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 quanti fied. Scope and purpose Over the past two decades an enormous amount of work has been done in desig ning neural networks (NNs) which utilize a variety of learning principles. There are many works in the literature that are noteworthy in the context, we list only a few like CS,621, which describe the various families of NNs, and how their learning compares to underlying biological learning models. In this paper we concentrate our attention on Kohonen's Self-Organizing Map (SOM) [21]. The SOM has een used in solving certain optimization problems such as the Euclidean Traveling Salesman Problem [3,4] which has been one o f the oldest "hard nuts" of Operations Research and Mathematical Programmin g. Any algorithm devised to solve the TSP tries to answer the following que stion: Given a set of N cities and distances for each pair of cities what i s the shortest tour that visits each city exactly once? The beauty of the SOM is the fact that the individual neurons adaptively te nd to learn the properties of the underlying distribution of the space in w hich they operate. Additionally, they also tend to learn their places topol ogically. This feature is particularly important for problems which involve two and three-dimensional physical spaces, and is indeed, the principal mo tivation for the SOM being used in solving the TSP [7,8]. More recently, we have added to this collection of methods a scheme which uses the recently introduced self-organizing neural network, the Kohonen Network Incorporatin g Explicit Statistics (KNIES) [9]. The primary difference between KNIES and the SOM is that, in KNIES, the neurons not only individually find their pl aces statistically and topologically, but also collectively maintain their mean to be the mean of the data points which they represent. The Euclidean Hamiltonian Path Problem (HPP) is closely related to the TSP: Given a set {X-i:1 less than or equal to i less than or equal to N} of cit ies with starting and terminal cities X-s and X-t, respectively, and distan ces for each pair of cities, what is the shortest path that starts at X-s, terminates at X-t, respectively, and visits each city exactly once? There a re only a few independent solutions to the HPP; indeed most solutions utili ze the underlying solution to the TSP. In this paper we try to solve the HP P without resorting to an underlying TSP solution method, and adapt our new NN methods, KNIES. Our new neural algorithms are the first all-neural solu tions to the HPP to our knowledge, and experimental results indicate that t hey are accurate and efficient. (C) 2000 Elsevier Science Ltd. All rights r eserved.