Overview: Using both Tabu Search and Genetic Algorithm (GA) techniques, solve the traveling sales man problem (TSP) (find a Hamiltonian circuit) for a given list of nodes and positions (graph). Compare and contrast your results with those from Lab 3.
Code Requirements:
• Always use Node 1 as your start/finish point of TSP
• Read node list in from a text file which uses same format as the positions.txt file from Lab 2
o NodeID x, y, z → 1,1.23,3.45,4.112 → int,float,float,float
o You can derive your own list of nodes and positions
o Code will be tested against a private list of nodes/positions. Code will only be tested up to the number of nodes
identified in writeup as total nodes able to analyze.
• Return optimal (shortest) path for given list of nodes
• Start with a list of 4 nodes and increase to the maximum number that is feasible with your computer for both Tabu and GA
algorithms
• When coding GA, you must identify and test multiple techniques for:
o Selection o Mutation o Crossover
• When coding Tabu, you must identify and test multiple techniques for:
o Neighborhood identification
o Tabu List size
• Design your code to be reusable for new algorithms, incorporating the file loader and output system into a single interface.
Utilize patterns (or modified patterns) to make informed decisions on how to architect your project. How your code was designed will hold a substantial weight on overall project grade. Specifically, in this lab you will need to consider how you design an interface for GA and Tabu to test the multiple techniques and configurations required.
Report Requirements:
• Plot timing with excel for each algorithm in a single graph. X axis should be number of nodes in graph, Y axis should be total timing.
o Also provide a table to summarize data in graph
o This should include results from Lab 3 for comparision
• Provide a summary of results obtained and be sure to explain time complexity for each algorithm
o Provide a graph that shows a comparison of timing captured on code execution vs the asymptotic timing determined for given algorithm
• Explain and document your design decision. Should include write up that explains architecture decisions and how you designed for functionality and extensibility as well as a UML diagram.
• Exaplain and discuss in detail how you’re the variations of GA and Tabu caused changes in the outcomes, and be sure to
explain why those modification/changes caused the output obtained.
Submit inside of your class git repo.
CSE 3353 Fundamentals of Algorithms Page 2 of 2
