TY - GEN
T1 - Applying ACO to Large Scale TSP Instances
AU - Chitty, Darren M
PY - 2018/1/1
Y1 - 2018/1/1
N2 - Ant Colony Optimisation (ACO) is a well known metaheuristic that has proven successful at solving Travelling Salesman Problems (TSP). However, ACO suffers from two issues; the first is that the technique has significant memory requirements for storing pheromone levels on edges between cities and second, the iterative probabilistic nature of choosing which city to visit next at every step is computationally expensive. This restricts ACO from solving larger TSP instances. This paper will present a methodology for deploying ACO on larger TSP instances by removing the high memory requirements, exploiting parallel CPU hardware and introducing a significant efficiency saving measure. The approach results in greater accuracy and speed. This enables the proposed ACO approach to tackle TSP instances of up to 200K cities within reasonable timescales using a single CPU. Speedups of as much as 1200 fold are achieved by the technique.
AB - Ant Colony Optimisation (ACO) is a well known metaheuristic that has proven successful at solving Travelling Salesman Problems (TSP). However, ACO suffers from two issues; the first is that the technique has significant memory requirements for storing pheromone levels on edges between cities and second, the iterative probabilistic nature of choosing which city to visit next at every step is computationally expensive. This restricts ACO from solving larger TSP instances. This paper will present a methodology for deploying ACO on larger TSP instances by removing the high memory requirements, exploiting parallel CPU hardware and introducing a significant efficiency saving measure. The approach results in greater accuracy and speed. This enables the proposed ACO approach to tackle TSP instances of up to 200K cities within reasonable timescales using a single CPU. Speedups of as much as 1200 fold are achieved by the technique.
KW - Ant Colony Optimisation
KW - High performance computing
KW - Travelling Salesman Problem
UR - https://www.scopus.com/pages/publications/85029572859
U2 - 10.1007/978-3-319-66939-7_9
DO - 10.1007/978-3-319-66939-7_9
M3 - Conference Contribution (Conference Proceeding)
AN - SCOPUS:85029572859
SN - 9783319669380
T3 - Advances in Intelligent Systems and Computing
SP - 104
EP - 118
BT - Advances in Computational Intelligence Systems - Contributions Presented at the 17th UK Workshop on Computational Intelligence
PB - Springer Verlag
T2 - 17th UK Workshop on Computational Intelligence, UKCI 2017
Y2 - 6 September 2017 through 8 September 2017
ER -