Title: Traveling Salesman Problem via Hopfield-Tank Neural Network
Author: David J. Stein, Esq.
Version: 1.0
Written: Fall, 2004


Abstract: The traveling salesman problem is a simple problem: given a 2D graph of cities, what is the shortest circuit - the shortest route that visits each city exactly once? The triviality of this task is deceptive: it is, in fact, NP-complete: while many algorithms can produce a very good route, no known method exists of finding the shortest route without some measure of brute-force trial-and-error computation.

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:

You may select any values you wish in order to experiment with the results of this type of neural network. Also, you may assign a name to the network, as well as save the network as an XML data file or load a previously saved network.

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.