COSC 461/561
Travelling Salesman Problem
OK folks. You have the data set. Here's what to do: solve the TSP with
the following algorithms. For each algorithm, report the total number
of tours tested, as well as the run time of your program. Also report
the shortest tour given and graph it (please!!)
1) Genetic Algorithm. Choose a population size of 30 and initially,
seed it randomly. Have the algorithm execute for 1,000,000 times and
report the shortest tour every 100,000 steps. Repeat this for a
mutation rate of 0.0 , 0.00001 , 0.001 , and 0.1 .
You should describe in a commnet at the start of your program how
you represent a tour and implement crossover.
2) Uniform Cost. I would try this with 20 cities, then 30, 40, etc (see
3 below)
3) Our "in class" heuristic. That is, only consider tours that don't
cross each other. Implement data structure with uniform cost (branch
and bound) as
above. I would suggest limiting this to the first 20 cities in the data
file; if that runs in a reasonbale time, try 30, 40, etc.
4) Simulated Annealing. Be sure to include your cooling schedule in a
commnet at the start of your program.
5) Greedy algorithm: start at a city, goes to the next closest
unvisited city, etc.
You should have a cover sheet with the results of all methods in
table (calculated length and CPU time).
Due Dates:
Let's have 2) , 3) , and 5) due by Monday
October 28
Let's have 1) and 4) due by Monday December 2 . Make sure to include
results from October 20 in your handin.
What to include in the handin:
1) What did you learn ? Please be explicit and specific!
2) Include actual graphs of tours! For some algorithms (like simulated
annealing) it is VERY instructive to draw the minial tour in real time
(that is, as the algorithm is running)
3) Include tables where you compare the algorithms
PLEASE NOTE: for algorithms 2) and 3) you may not be able to do "large"
instances of the algorithm. Instead, you might try tours with
N=5,6,7,8,....... cities until your program "explodes". Report the
time, number of nodes visited , actual tout and tout length until
the program explodes. Better grades for larger value of N reported.