Make your own free website on Tripod.com

NEURAL NETWORK

PROJECT # 3

Traveling Salesman Problem

Genetic Algorithm

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.  Algorithms can be applied in order to optimize the problem solving process.  However, these represent varying degrees of success in trying to solve the problem. 

 

The genetic approach is somewhat different from the neural approach.  The genetic representation differs in two ways:

 

  1. It uses complete solutions (exact integer permutations).
  2. It uses multiple solutions in the form of a population which is a set of permutations.

 

The genetic approach uses the iterative method to try and improve the overall fitness of the population.  This is done by adding and subtracting members of the population in order to obtain the best results.  There are two competing features:

 

  1. Directed Search (Exploitation):

The idea of this method is by selecting and using members of the population in order to create children that potentially are more fit than the parent.  The methods used here are controlled by selection and recombination.

This model allows the fitter members of the population to participate in procreation.  The idea is that by allowing the fitter of the population for crossover (recombination), there is hope that the children will get the best traits from the parents.

 

  1. Random Search (Exploration):

This method looks at exploring new and different possibilities.  While exploring the different possibilities, there is a factor of randomness in the search due to the recombination.  The mutation operator and the rate at which it is applied control the method.

This method allows random changes to members of the population.  Changes or mutations are randomly made, which will keep the population diverse.  There is then inclination to explore new and different solutions.

 

 

 

 

 

The observations that I noticed after seeing the simulations were that convergence occurred very quickly, within the first fifty iteration loops. In the experiment the convergence threshold was not used.  The key parameters of this experiment were the method of recombination to generate the child and the mutilation rate appears to be the closer to zero, the faster the convergence.  The convergence occurred way before the maximum iteration was reached.  The “crossover” method appears to yield better results than the “distance” method. 

 

However, it appears that in some occasions, the network did not result in convergence (0.1 percent). 

 

2.     Source Code

 

Position.java

Position of city

TSP_GA_Frame.java

GUI to display result

TSPGenetic.java

Computation of TSP

Graphs

Experiment Results

 

TSP Genetic Algorithm Application :

 


3.                 Simulation Results

 

Case 1: Order method for “recombination”

Testing the algorithm with the mutation rates: 0.00, 0.02, 0.04 and 0.06 it appears that the optimum results was that the lower the mutation rate (e.g. 0.00) the better the results.  In this particular case, the Order_00 converged more quickly than at the higher rate.

 

The “best” mutation rate for this problem is 0.00 (please see the best and worst graphs below).  It appears that when the mutation rate is close to zero, the population converges very quickly, whereas the higher the mutation rate, drastic changes may occur which can prevent convergence.

 

Recombination methods act on the premise that subsequences or parts of fit parents are used to create fitter child.  However, there are some “bad” parts of parents, so if in a random sample, there is a possibility that these traits will be passed onto the child, making them less fit than the parents.  In this case, the less fit children will be systematically purged from the population.  The hope is that there will be more children whom are more fit than the parents.  There is also a hope that there will occasionally be a child that is “the best”, it may take many generations though for this to happen.  There are some recombination techniques that try to minimize the chance of bad parts of parents passing onto the child, though this may require extra calculation to ensure that the better parts of the parents are passed onto the child as opposed to the random parts.  The benefit of this method is that it reduces the population by randomly discarding the “bad” traits.


 

Graph of the Best Tour: The best tour is found with mutation rate = 0.00, length = 5.73 and convergence at: 159

Graph of the Worst Tour: Mutation rates of 0.20, 0.04 and 0.06 never can get to convergence.


Case 2: Distance Method

 

This method looks at calculating the edges in order to come up with the best fit function, in this case the shortest length between two cities.  There can be problems with this method though since this often leads to dead ends because there are no more edges left from parents but there are still cities to visit. 

 

Graph of the Best Tour: The best tour is found with mutation rate = 0.00, length = 5.94 and convergence at: 213

 

Graph of the Worst Tour: Mutation rates of 0.20, 0.04 and 0.06 never can get to convergence.

 

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