Cooperative and competitive ACO-PSO hybrid version for Travelling Salesman Problem

Abstract

After the concept of Swarm Intelligence was introduced in late eighties and became known as a distributed solution for complex tasks, a variety of Swarm Intelligence heuristics were initiated. Swarm Intelligence heuristics are often used in solving combinatorial problems such as Travelling Salesman Problem (TSP). Even though there are numerous attempts to solve TSP, yet there is space in improving the solution quality for solving large scale TSP instances. Among Swarm Intelligence algorithms, Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO) algorithms have taken much of the interest of researchers since of their simplicity, effectiveness and efficiency in applications. The objective of this study is to attempt a reduction in delay in convergence while maintaining an acceptable accuracy in solving large scale TSP instances by hybridizing PSO and ACO. In this proposed ACO followed PSO approach, influences of cooperation and competition of swarm populations were adapted and fine tuned to increase the solution quality. The experimental results show an error less than 2.5% when converging to the optimum for TSP instances not more than 3038 nodes. Further the experimental results demonstrate that the attempt of reducing the delay in convergence is successful while maintaining an acceptable solution quality when the proposed approach is used in solving instances of moderate scale Travelling Salesman Problems.