Dustin Stevens-Baier
Neural Networks
Assignment#2
Write a report about this implementation, including:
A. An introduction that describes the TSP problem and the general idea for the neural network approach.
Include observations you made after seeing the simulations, including any ideas you have for what made,
or could make, the network better (get shorter tours more consistently in fewer iterations, etc.).
The traveling salesman problem is an NP complete problem, becuase there is no polynomial runtime solution.
The idea behind the problem is to have the traveling salesman must find the shortest route through n-cities.
To evaluate all paths through the cities, it would take N! time which is obviously alot. This is why approximation
algorithms should be used to determine the tour and since we are in a neural networks course we can start there.
The Network as defined by the problem is a N x N matrix where N is the number of cities in the
network. Neurons in the network react via feedback through a weight matrix. The weights
in the matrix are computed to favor cities closer as the next target. The network is driven to a minimal state,
and all the activations in the network move closer to the maximum or minimum activation. The ideal case
is having all the neurons at the minimum activation level except for one neuron in each row and column of the matrix.
In order to obtain this type of solution, the simulation would have to run for a very long time, thus we cut off
the simulation and are able to discard the neurons near the minimal activation and look at the center of all the data
to determine which ambiguously activated neuron should be selected for the tour. After each city is assigned a mass value,
the weights are sorted to determine the direction of the tour.
B. A copy of the code
The source code can be found here
C. Show the specific results for running the network twice
for each case (case1, case2), with the following:
1. City positions.
2. Tour that resulted.
3. Drawing of the tour.
4. Length of the tour.
5. Final activations of the network.
6. Number of iterations for convergence.
7. A plot of the energy as a function of iteration.
Circle Case 1:
1: City Positions link
2: Tour that resulted link
3: Drawing of the tour
4: Length of the tour 1.4861274178821933
5: Final activations of the network link
6: Number of iterations for convergence Iterations 3538 and Threshold .6
7: A plot of the energy as a function of iteration
raw data
Circle Case 2
1: City Positions link
2: Tour that resulted link
3: Drawing of the tour
4: Length of the tour 1.486127417882193
5: Final activations of the network link
6: Number of iterations for convergence Iterations 2799 and Threshold .6
7: A plot of the energy as a function of iteration
raw data
Random Case 1
1: City Positions link
2: Tour that resulted link
3: Drawing of the tour
4: Length of the tour 3.606604811119306
5: Final activations of the networklink
6: Number of iterations for convergence Iterations 2517 and Threshold .6
7: A plot of the energy as a function of iteration
raw data
Random Case 2
1: City Positions link
2: Tour that resulted link
3: Drawing of the tour
4: Length of the tour 4.158771697059068
5: Final activations of the network link
6: Number of iterations for convergence Iterations 1881 and Threshold .6
7: A plot of the energy as a function of iteration
raw data
D. Convergence Issues:
1. What "convergence criteria" did you use? (How did your program know when to stop the simulation run?).
I used the recommended convergence criteria of the Threshold level of 0.8 to start with and then lowered it to get a higher
convergence rate. I also used a maximum number of iterations of 10000 which seemed to be what everyone else did
in past classes so I tried to stay close to this concept. If at least one neuron in a given row of the matrix
achieved the convergence criteria, then that row was considered converged.
2. It is assumed that you did more than a couple of simulation runs.
Approximately what percent of the time did the network converge to an ambiguous state
(no clear winner in each row and column)?
For the uniform case, almost every time the network converged, I had one case where it didn't.
For the random cases both examples if I dropped the threshold to .6 then the convergence rate jumped to 80 percent. However, if I used the
.8 threshold it rarely converged.