COMP572
Neural Networks
Ludovic Hilde
Email: [email protected]
Summer 2008
07/09/08
Assignment 3
A. Copy of your code.
Click on the link below to access the source code of the simulation:
B. Report with:
1. Introduction describing the project and any observations you made
while building and implementing the simulation.
The genetic algorithm is another approach to solving the Traveling Salesman Problem (TSP). It operates on members of a population where each person contains a tour of the visited cities (we could think of it as a DNA string). The algorithm orders people by fitness, which corresponds to the shortest tour length, and creates new people (children) from the existing population (parents). This implementation has two ways for creating children the order method and the distance method.
The cities were placed randomly in the unit square during the first run. However, these positions were recorded and reused between the different runs in order to compare the results for the different mutation rates and recombination methods. In this simulation, the cities were placed as shown below:
For practical purposes the population was limited to 10000.
My implementation did not apply mutations to the upper 1/100 of the population and no mutations were applied when the population was less than 100. In other words, mutations were not applied to the fittest members of the population.
2. Case 1: Order Method
a. total generations (iterations)
I tried out several iteration values for the different mutation rate values (e.g. 10000, 20000, and 40000).
b. drawing of the best tour found
10000
Iterations
20000 Iterations
40000 Iterations
c. plot of the length of the best and worst
tour at each generation (gives the range of fitness values for each
generation).
d. what do you think is the
"best" mutation rate for this problem? Explain.
For 10000 iterations, the best tour was found with a mutation rate of 0.02. However, for 20000 and 40000 iterations, I obtained the best tours using a mutation rate set to 0.04.
In my opinion, the order method does not show a clear cut between the different mutation rates. I cannot tell with certainty which mutation rate is most likely to output the best tour. In all pictures of section b, the tours are random looking (e.g. the next city of a given point is sometime selected on the opposite end of the unit square).
However, from the data, it seems better to use a lower mutation rate for a smaller number of iterations (e.g. <=10000), and a higher one for a larger number of iterations (e.g. >20000).
3. Case 2: Distance Method
a. total generations (iterations)
Same as case 1, I tried out several iteration values for the different mutation rate values (e.g. 10000, 20000, and 40000).
b. drawing of the best tour found
10000
Iterations
20000
Iterations
40000
Iterations
c. plot of the length of the best and worst tour at each generation
(gives the range of fitness values for each generation).
d. what do you think is the
"best" mutation rate for this problem? Explain.
For 10000 iterations, the best tour was found with a mutation rate of 0.0, but the “best looking” tour was found with a mutation rate of 0.02. The little jitter on the left hand side of the screen lengthen the tour, otherwise the solution would have been near optimum.
For 20000 iterations, the best tour was found with a mutation rate of 0.04.
For 40000 iterations, the best tour was found with a mutation rate of 0.06.
The distance method is superior to the order method, some of the tours showed in the pictures look close to optimum solutions. Similarly to the order method, it seems better to use a lower mutation rate for a smaller number of iterations (e.g. <=10000), and a higher one for a larger number of iterations (e.g. >20000).