This application is an attempt to solve the Traveling Salesman Problem with a Hopfield-Tank neural network, which is the classic solution. As this application demonstrates, however, the algorithm spectacularly fails to produce perfect, or even good, solutions. Competing algorithms produce much better solutions in much shorter time frames.
Installation Instructions: Nothing unusual - simply run the enclosed executable. Note that the network save and load features rely on some XML schema definition (.XSD) files stored in the Schema Files folder collocated with the executable, so don't alter or rename these files.
Operation Instructions:
First, some detail on this Hopfield-Tank neural network will be useful. The network consists of a set of neurons, each representing a city, connected by a synapse to every other neuron. Each synapse (connecting two neurons or cities) fires with a certain strength, representing the preference of traveling between these two cities in this solution. The network evolves a solution by incrementally adjusting the weights of these neurons, based on some logical rules, until a proper solution is produced. Also, each synapse has a momentum value that defines how quickly (and in which direction) the synapse weight changes in each step.
Solving this problem consists of three steps: create a map, configure the Hopfield-Tank neural network, and apply the network to produce a solution.
Create a map: Simply click in the Map window to produce cities. Left-clicking on a city deletes it, and right-clicking on the city enables the user to move it around the map.
Configure the network parameters: This customized Hopfield-Tank neural network relies on the following parameters:
The network results critically depend on these values. Setting A and B too large (with respect to D) causes the network to pay no attention to the distances, thereby yielding junk results. Setting A and B too small (with respect to D) causes each neuron to be so discouraged by distances to nearby cities that, in fact, the network yields incomplete and invalid solutions.
The extremely delicate nature of this balance, and the nonexistence of an optimal balance, dooms this neural network model to produce terrible results for this problem.
Apply the network to produce a solution: You may use the "Solve (Step)" and "Solve (Full)" buttons to use the Hopfield-Tank neural network to produce a solution. The former carries the network one step toward a solution and displays the results. The latter runs the network continuously until it yields a solution, and then stops and displays the results. A new solution may be generated by clicking "Clear Network" and then clicking the Solve buttons again. Alternately, the last solution may be replayed by clicking "Reset Network" and clicking the solve buttons again.
Comments: As noted above, this application is mostly of interest in observing its poor performance. Although no known method of exists of yielding perfect results without exhaustive computing, this model produces terrible results even compared with competing methods (genetic algorithms, set builder algorithms, etc.)
Application History: This application was written during an artificial intelligence course taught by Professor Toshinori Munakata in Fall, 2004. This application was not written for or submitted as a class assignment, but was created as a study guide in understanding a lecture topic.
Questions/Comments: Please contact David J. Stein, Esq. via email at djs10@po.cwru.edu.
Terms and Conditions of Use: Please see the enclosed "License.html" file for terms and conditions of use of this software package.