Abstract: This paper presents EHAS, an effective hybrid algorithm combines Max-Min Ant System(MMAS) with Lin-Kernighan local search strategy. EHAS uses 3-opt to initiate the solution and Lin-Kernighan algorithm to build improved solutions. It also imposes Metropolis rulers to adjust solutions, which can speed up convergence, avoid local optimization and solve scalable instances. Theory analysis and experimental result show that EHAS outperforms other hybrid ant colony algorithms due to its ability to find the satisfactory results effectively when applied to the traveling salesman problem.

Key words: max-min ant algorithm, local search optimization, Lin-Kernighan algorithm, Metropolis accept rules, traveling salesman problem

摘要： 目前求解TSP问题效果最好的混合算法是最大最小蚂蚁算法和局部搜索算法，文章通过对几种局部搜索的灵活运用，并结合改进的接受准则接受局部优化解，提出了一种高效的混合蚂蚁算法。算法前期使用3-opt这种简单高效的局部搜索的解初始化信息素矩阵，加快收敛速度，后期采用改进的Lin-Kernighan算法生成局部优化解然后依Metropolis接受准则概率接受，有效地避免陷入局部最优，理论分析和TSPLIB中部分实例仿真结果表明，此算法能比其他改进蚁群算法具有更多优越性。

关键词: 最大最小蚂蚁算法, 局部搜索优化, Lin-Kernighan 算法, Metropolis接受准则, 旅行商问题

CLC Number: 

• TP301.6