摘要： 为克服传统蚁群系统(ACS)在较大规模问题计算中易陷入局部最优,以及求解精度较低等不足,提出一种新的改进蚁群算法。该算法引入最小1-树中的α-邻近概念,能更好地反映给定边属于最优回路的概率,通过转换邻接矩阵,计算出最优回路的下界,以此提高α 值的精度,并给出适应性探索策略,加入3-opt 领域搜索算子,有效提高优化解的精度。实验结果表明,该算法具有更好的全局寻优能力,与ACS 等算法相比能获得更加优化 的解。

关键词: 蚁群系统, α-邻近, 最小1-树, 下界, 适应性策略, 旅行商问题

Abstract: In order to overcome the disadvantages that traditional Ant Colony System(ACS) is easy to fall into local optimum and low-precision for large-scale problems,this paper presents an improved ant colony optimization algorithm.The algorithm introduces α-nearest in the minimum 1-tree,which better reflects the chances of a given link being a member of an optimal tour. It improves α-nearest precision by transforming the adjacency matrix and computes a lower bound. Besides,it proposes the adaptive exploration strategy and 3-opt local search. Experimental results show that this algorithm has a better global searching ability in finding the best solutions and can obtain better solutions than ACS,etc.

Key words: Ant Colony System ( ACS ), α-nearest, minimum 1-tree, lower bound, adaptation strategy, Travelling Salesman Problem(TSP)

中图分类号: 

• TP18