Project 4: TSP – Genetic Algorithm

                                                                                                                      CECS‐545
Project 4: TSP – Genetic Algorithm
• 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
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.
Dr. Roman V. Yampolskiy                                                                                                                             CECS‐545
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.