Project 4: TSP – Genetic Algorithm A Traveling Salesperson Problem (TSP) is an NP-complete problem. A salesman is given a list of cities and a cost to travel between each pair of cities (or a list of city locations).
• Learning objectives. At the completion of this project, you should be able to:
o Implement a genetic algorithm for an intractable problem.
o Be able to discuss aspects of the GA that control success in finding good solutions.
• Background
o A Traveling Salesperson Problem (TSP) is an NP-complete problem. A salesman is given a list of cities and a cost to travel between each pair of cities (or a list of city locations). The salesman must select a starting city and visit each city exactly one time and return to the starting city. His problem is to find the route (also known as a Hamiltonian Cycle) that will have the lowest cost. (See http://www.tsp.gatech.edu for more info)
• Problem
o You will be expected to implement a GA for a TSP dataset with up to 100 cities
o Data for each problem will be supplied
• Hints
o Analyze the results of two different settings for two different parameters. For example you can use two different types of crossover methods and two different mutation rates. In that case, you need to collect four sets of data:
o
Crossover A | Crossover B | |
Mutation 1 | Dataset 1A | Dataset 1B |
Mutation 2 | Dataset 2A | Dataset 2B |
• For each of the four datasets, you will need to run your code several times to develop performance statistics.
• I use the example of two crossovers and two mutations. You can select any modification of GA so long as you can have (at least) 2 options for each modification. For example you could choose two different sizes of populations. You could choose two different selection methods, etc.
• Don’t forget, if you run your code a 100 times on a large dataset, you will likely wind up with nearly 100 different solutions.
• Deliverable- Genetic Algorithm
o Well-commented source code for your project. You can use any language you like, but I reserve the right to ask you to demo performance of your algorithm on a new dataset.
o Include a GUI with visual (and dynamic) representation of the solutions for this project.
o Project report (3-4 pages).
o Define your crossover and mutation methods. Or else define which ever two GA
elements you chose to investigate. Clearly identify if your methods were your idea or
else the source from which you got the idea.
o Define your stopping criteria.
o Clearly identify your best solution for the solved problem.
o Analyze the effectiveness of the two chosen variations in GA. To do this you will
likely need to run your code several times and provide the min, max, average and
standard deviation of each set.
o Briefly discuss how long a typical run took for each of the datasets.
o Graphically present your improvement curves.
o Critical thinking section
Describe the biggest problem that you had in the implementation and analysis of this project.
Describe the one thing you would change if you did this project again.
Please elaborate on what you learned from using GA. At least one paragraph, please.
Give your overall impressions of GA as problem solving technique.
