• As part of your report, write a technical section about how Simulated Annealing (SA) and Ant Colony Optimisation (ACO) work. Discuss why they are especially useful for problems such as the TSP. Three to five pages worth of good material should suffice. Don’t rip off Wikipedia or some other blog. In this section, you should convince me that you understand the methods. • Note regarding any artifacts you develop: you do not need to implement algorithms yourself. You may use existing libraries (for example, in Python).
• You are required to implement: 1. A simulated annealing algorithm applied to the TSP. 2. Ant colony optimisation applied to the TSP. • You may obtain instances of TSP from TSPLIB over here: http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html • You are required to deal with instances of symmetric the TSP only.
• Evaluate the performance of both the SA and ACO methods using at least four instance sizes (number of cities) of your choice for each method. Choose your sizes wisely so that your evaluation makes sense. Structure your evaluation as follows: Instance name: burma14.tsp SA method: ACO method: Results: … … Instance name: bays29.tsp SA method: ACO method: Results: … … and so on…
• In your report, make sure to discuss your methodology and describe your implementation (e.g. which representation schemes you used and so on).
• Describe some other applications that SA and ACO are suitable for. • Make sure that your report has a good evaluation section for any artifacts you develop. Also, make sure to discuss the suitablity (SA vs ACO) of each method for TSP (e.g. can one method handle larger TSP instances than another?). Statement of completion – MUST be included in your report Item Completed (Yes/No/Partial) SA and ACO technical discussion Artifact 1: TSP with SA Artifact 2: TSP with ACO Application of SA and ACO to other scenarios Experiments and their evaluation Overall conclusion
