NEURAL NETWORK
PROJECT # 3
Genetic Algorithm
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:
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:
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.
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).
Position of city 

GUI to display result 

Computation of TSP 

Experiment Results 
TSP Genetic
Algorithm Application :
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.