Use programming tools to development an ACO optimization system for the traveling salesman problem. Particularly, you are asked to implement ACS.
Conduct necessary system requirement analysis before implementing your system: to design your data structured and user interfaces for solving the TSP. You are given a library (.dll) and a set of TSP benchmarks. The lab class will instruct you how to use the library to take advantages of accessing and displaying a TSP benchmark. Your system should have basic yet friendly user interfaces for benchmark selections, ACO parameter settings, and stopping condition settings, etc.
You may follow the assignment structure of the GA solver to implement your ACO system. For example, you can design a GenericACO solver and an ACS system to derive it.
In your project video demo, run the benchmark taiwan50 and att48.
Travelling Salesman Problems:
A travelling salesman need to visit n cities and exactly once for each. The planar Cartesian coordinates of the cities are given and the Euclidean distances between cities can be computed accordingly. A TSP is therefore, to find a sequence of city visiting that has the shortest length (including the distance from the lastly routed city back to the first one).
n : number of cities,
(xi , yi ): Cartesian coordinates of cityi ; i =0,1,L,n−1 di, j : distance from cityi to city j ;
di, j = (xi −xj )2 +(yi −yj )2
n−2
min f (z)=dzn−1,z0 +dzi ,zi+1 , where
i=0
z=z0,z1,L,zn−1,zk 0,1,L,n−1,zk zk
The benchmarks for TSP are in extended file name “tsp”. Sample file:
The optimal solutions to TSP benchmarks are in extended file name “opt.tour”. Note that the node IDs start from 1 to n; you must convert them to 0~n-1. Sample file:
Sample class
