An Improved Ant Colony Optimization Algorithm Based on Fractional Order Memory for Traveling Salesman Problems

摘要

Ant Colony Optimization (ACO) algorithm has a wide array of applications to solve combinatorial optimization problems, especially Traveling Salesman Problems (TSPs). The major limitations of ACO algorithm are premature convergence, the possibility that trapped in the local optima. In this paper, an improved Ant Colony Optimization algorithm is proposed which uses fractional order difference for pheromone updating and a weighted combined transition probability. The fractional order difference with the characteristic of long-term memory helps the algorithm make full use of the historical information, and the combined transition probability enhances the exploration ability of the algorithm by using the information of a few steps forward. The performance of the proposed algorithm is tested on various data sets from the standard TSP Library compared with the corresponding integer order algorithm and some evolutionary algorithms. According to the empirical results, our algorithm based on fractional order difference overcomes the classic integer order. Furthermore, the results on a number of TSP instances demonstrate that compared with other evolutionary algorithms, the proposed method can obtain the better solutions on most instances with stronger robustness.