An Improved Adaptive Hybrid Ant Colony System Algorithm for the Traveling Salesman Problem

摘要：

This paper presents an improved hybrid Ant Colony System (ACS) algorithm based on the MAX-MIN ACS algorithm and the 3-opt local search strategy. We used local search solutions to initialize the pheromone trail matrix at the early stage for accelerating the convergence speed; and applied Metropolis acceptance criterion at later stages for avoiding local best solutions. The algorithm self-adaptively adjusts the pheromone trail information and selects candidates among the k-Nearest Neighbors so that it can be applied to compute large scale inputs. Both theoretical analysis and the TSPLIB experiments have shown that the algorithm provides performance improvements over the standard ACS algorithms on solving the Traveling Salesman Problem.

关键词： MAX-MIN Ant Colony System 3-opt Local Search Self-adaptive Adjustment k-Nearest Neighbor Candidate Set Traveling Salesman Problem

作者: Xingyu Chen Huiyun Quan Wei Xiao

作者单位: the College of Mathematics and Computer Science, Hunan Normal University, Changsha, Hunan, 410081 China

会议类型: 国际会议

会议名称: The Second International Symposium on Intelligence Computation and Applications(ISICA 2007)(第二届智能计算及其应用国际会议)

会议地点: 武汉

会议语种:英文

在线出版日期: 2007-09-21（万方平台首次上网日期，不代表论文的发表时间）