A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem

作者：Yan Yuzhe; Sohn Han suk; Reyes German

来源：Applied Soft Computing, 2017, 60: 256-267.

DOI：10.1016/j.asoc.2017.06.049

• Ant Colony Optimization
• Adaptive tour construction
• Adaptive pheromone updating
• Ant System
• Traveling salesman problem

This paper presents a new variant of Ant Colony Optimization (ACO) for the Traveling Salesman Problem (TSP). ACO has been successfully used in many combinatorial optimization problems. However, ACO has a problem in reaching the global optimal solutions for TSPs, and the algorithmic performance of ACO tends to deteriorate significantly as the problem size increases. In the proposed modification, adaptive tour construction and pheromone updating strategies are embedded into the conventional Ant System (AS), to achieve better balance between intensification and diversification in the search process. The performance of the proposed algorithm is tested on randomly generated data and well-known existing data. The computational results indicate the proposed modification is effective and efficient for the TSP and competitive with Ant Colony System (ACS), Max-Min Ant System (MMAS), and Artificial Bee Colony (ABC) Meta-Heuristic.

• 出版日期2017-11