CSSE 453: Programming Assignment One
SI Solutions to the TSP Problem
The purpose of this exercise is to experiment with different ant based
swarm intelligence (SI) solutions to the traveling salesperson problem
(TSP). To this effect, design and implement software that solves the
traveling salesperson problem, using ants. In particular, I would like
you to experiment with different strategies when it comes to the
complexity of the agents, the complexity of the stigmery, and possibly
the complexity of the colony of the agents, in the sense that not all
agents have the same behavior.
Please work on this project in pairs.
Software Specifications
- Find a closed tour.
- The output of your software should contain information on:
- The number of cities in the problem instance.
- The length of the best tour found.
- An ordered list of the cities along the best path found.
- Anything else you deem useful.
- You may implement your software in any programming language you
choose.
- I will provide some files containing arbitrary generated problem
instances of the TSP. In addition to generating your own test-data, I
would like you to run your program on the test-data that I provide.
Report Specifications
- Write a report in which you show and discuss your experiments.
- I imagine the report to contain two to three pages of
single-spaced text as well as some charts and tables summarizing your
experiments and findings.
- For the larger problem instances, I am interested in the computing
resources you used (time, data-structure used, space)
Test data
I modified the software so that the distance is in the interval [1,
100]. I also modified it so that the city IDs start at 0.
The test data is of following format: CityA CityB Distance