An adaptive ant colony algorithm based on common information for solving the Traveling Salesman Problem

Ant colony algorithm has been successfully applied to the Traveling Salesman Problem (TSP). But it has some disadvantages, such as easily plunging into local minimum, slow convergence speed and so on. In order to find the optimal path accurately and rapidly, an improved ant colony algorithm is proposed. The improved algorithm strengthens the consideration of the common information to induce ant colony to the local search and reduce the redundant operations. Moreover, improved algorithm uses adaptively adjusting pheromone decay parameter mechanism to adjust convergence rate and ensure the global search ability. Experiments show that the algorithm has a remarkable quality of convergent precision and the convergent velocity.

I. Introduction

TSP is a famous NP-hard problem. It has been widely applied in PCB layout, VLSI chip design vehicle scheduling and other combinatorial optimization problem [1]. Ant colony is the evolution of intelligent heuristic algorithm based on the study of group behavior of real ants in nature. It is first proposed by Dorigo et al [2], it has been successfully applied to the TSP and other NP-hard combinatorial optimization problem, but the basic ant colony algorithm is prone to maturity and stagnation early. For this defect of the ant colony algorithm, many improved algorithms are proposed, such as Ant-Q combined with Q-Leaming algorithm [3], MMAS algorithm [4], ant colony algorithm based on negative feedback [5]. When some researchers realize that ant colony is organized and every ant has respective division of labor, a polymorphic ant colony algorithm is proposed [6], to some extent, it improves the performance of the ant colony algorithm and also is a development direction to improve the efficiency of ant colony algorithm.