keyboard_arrow_up
AN IMPROVED ANT COLONY ALGORITHM BASED ON 3-OPT AND CHAOS FOR TRAVELLING SALESMAN PROBLEM

Authors

Qingping Yu ,Xiaoming You and Sheng Liu Shanghai University of Engineering Science, China
Shanghai University of Engineering Science, China

Abstract

This paper presents an improved chaotic ant colony system algorithm (ICACS) for solving combinatorial optimization problems. The existing algorithms still have some imperfections, we use a combination of two different operators to improve the performance of algorithm in this work. First, 3-opt local search is used as a framework for the implementation of the ACS to improve the solution quality; Furthermore, chaos is proposed in the work to modify the method of pheromone update to avoid the algorithm from dropping into local optimum, thereby finding the favorable solutions. From the experimental results, we can conclude that ICACS has much higher quality solutions than the original ACS, and can jump over the region of the local optimum, and escape from the trap of a local optimum successfully and achieve the best solutions. Therefore, it’s better and more effective algorithm for TSP.

Keywords

Ant colony system algorithm, 3-opt, Chaos, Travelling Salesman Problem