Parallel Multicolony ACO Algorithm with Exchange of Solutions

The availability of parallel architectures at low cost, e.g. clusters of PCs connected through fast local networks like Gigabit Ethernet, has widened the interest for the parallelization of algorithms [1]. There are two reasons for parallelizing a metaheuristic if one is interested in performance: (i) given a fixed time to search, the aim is to increase the quality of the solutions found in that time; (ii) given a fixed solution quality, the aim is to reduce the time needed to find a solution not worse than that quality. We use the Traveling Salesman Problem (TSP), an N P-hard problem, as a case study for testing the impact on the final solution quality reached, given a fixed run time, of the exchange of solutions among multiple colonies on different interconnection topologies. To solve the TSP we use MAX − MIN Ant System (MMAS) [5], currently one of the best-performing ant colony optimization (ACO) algorithms [3]. Our implementation of MMAS is based on the publicly available ACOTSP cod