Project 5: TSP ‐ GA with Wisdom of Artificial Crowds

                                                                                                                        CECS‐545
Project 5: TSP ‐ GA with Wisdom of Artificial Crowds
• Learning objectives. At the completion of this project, you should be able to:
o Implement a hybrid algorithm for solving TSP which combines Genetic Algorithm
with a Wisdom of Crowds approach.
o Be able to evaluate a novel algorithm for solving an NP-Complete problem.
• Problem
o Read: “Wisdom of the Crowds in Traveling Salesman Problems” by Sheng Kung
Michael Yi, Mark Steyvers, Michael D. Lee and Matthew J. Dry.
o Modify you GA from Programming Assignment 4 to utilize the Wisdom of Crowds
o Test data will be supplied, but also generate your own test cases
• Hints
o Take a certain percentage (experimentally determine what percentage) of the fittest
individuals in the population of solutions (let’s call them experts) to the TSP and
combine their solutions to produce a better solution.
o Regardless of which approach you take to combine opinions of the experts make
sure your final solution visits all nodes and does not visit any node multiple times
(except the starting node).
o If you detect that the resulting solution does not satisfy requirements of a TSP
solution use a greedy algorithm of your choice to get it into the proper form.
• Deliverables
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 representation of the solutions for this project and
incorporate snapshots in your report.
o Project report (5-6 pages).
• The following should be included in your report:
o Describe in detail the algorithm you used to aggregate opinions. Did you have to
alter the combined solution to make it a valid TSP solution?
o On average how well did the Wisdom of Crowds approach perform compared to
the standard unenhanced GA?
o Comparison charts for GA vs. (GA & WOC) on same problems in terms of
performance, speed, optimality of discovered solutions, etc.
o Does the size of the problem make a difference? What is the largest you tested?
o Report results of your experiments with multiple graphs, tables and figures. Look
at: “A Hybrid Heuristic for the Traveling Salesman Problem” (included with the
assignment) for some ideas on how to present results of your experiments.