Make your own free website on Tripod.com

NEURAL NETWORK

PROJECT # 2

Traveling Salesman Problem

1.     Introduction:

The Traveling Salesman Problem (TSP) deals with the task of a salesman finding the shortest distance to travel when visiting a number of cities (n cities) passing through the cities just once and returning to the city that the salesman started from.  There are a number of possibilities to solve this problem.  Neural Networks can be applied in order to optimize the problem solving process.  However, these represent varying degrees of success in trying to solve the problem.  One of the problems faced is the network convergence problem as this can sometimes result in ambiguity.  There are cases when the neural activations do not converge to a state that corresponds, unambiguously, to a permutation matrix.  This happens when the activations will only approach the maximum and minimum values (e.g. .98 or .002).  In order to deal with this, it is best to pick a threshold value (e.g. .70 in this assignment) and then check the activations in the array at each iteration for “convergence”.

 

The observations that I noticed after seeing the simulations were that no convergence could be reached. Even when the threshold was lowered (below 0.5) to force convergence before the maximum iteration was reached, this still did not result in convergence. When the maximum number of iterations was increased five-fold (50,000 times) for the 0.6 maximum activation thresholds, still no convergence could be reached.

 

One of the ways to make the network better is to use the “Fuzzy Read Out” method invented by Dr. Wolfe.  The premise of this method is to compute the center of mass of the positive activations in each row and then ordering the cities accordingly.  The center of mass calculation is computed by finding the maximum activation of the adjacent neurons as a base group of two, three or more neurons.  For example, on the same row, but different adjacent columns, neuron “a” activation = 1.2; neuron “b” activation = 1.8; neuron “c” activation = 0.2.  The Fuzzy Read Out activation value = (1.2 + 1.8 + 0.2) / 3 = 1.06.  However, neurons at the border are wrapped around.  So in this case, the smaller the group base, the better it is for the result.

 

2.     Source Code

 

Position.txt

Position of city

TSP_Display.txt

GUI to display result

TSP_Search.txt

Computation of TSP

 


3.     Simulation Results

 

Case 1: City positions are on a circle

 

 

The traveling distance: 1.56

 

Final activations of the network: -0.526 (click here for more details)

 

Number of iterations for convergence: maximum of iterations reached without convergence.

 

Plot of energy as a function of iteration – Energy Graph (click here for more details)

Case 2: City positions randomly generated

 

 

Traveling Distance: 10.82

 

Final activations of the network: -0.0526 (click here for more details)

 

Number of iterations for convergence: maximum of iterations reached without convergence.

 

Plot of energy as a function of iteration – Energy Graph (click here for more details)


4.     Convergence Issues

 

1. The convergence criteria that I used were based on maximum iteration loop.  The program stops when the predefined maximum iteration is reached.

 

2. The simulation was run multiple times however, the result did not reach convergence state so the rate is 99.999%.  I think that there may be an error in my coding but I am unsure where the error is in the program logic.

 

Reference: Previous student’s work and particularly Susan Zabaronick.