基于PR算法的自适应ACO算法求解旅行商问题

摘要

To solve the famous traveling salesman problem,the application of adaptive ant colony algorithm based on path-relinking algorithm was studied in this paper. According to the process of selection strategy and information pheromone updating mechanism of the ant colony algorithm,the adaptive ant colony optimization method was presented,i.e. the selection and random choice of ant colony were determined and the search dirc-tion was controlled by optimum of the threshold parameters of the threshold algorithm. This adaptive ant colo-ny optimization algorithm is used to search the solution space more effectively,which can effectively avoid from falling into local optimum. At the same time,in the ACO,path-relinking procedure is embedded into it to improve the solutions. The experimental results show that the adaptive ACO is very efficient and competi-tive to solve the traveling salesman problem in terms of solution quality.%以著名的旅行商问题为研究对象，研究了基于线路重连（PR）算法的自适应蚁群算法（ACO）的应用。根据蚁群算法构解过程中的选择策略与信息素更新机制，提出了自适应的蚁群优化方法，即通过阈值接收算法（TA）中的阈值控制参数改变蚁群的确定选择与随机选择机会，从而控制了搜索方向。采用这种自适应的蚁群优化算法，避免蚁群算法陷入局部最优，使对解空间的更好地进行搜索。同时，在蚁群优化算法（ACO）中，嵌入路径重连算法（PR）来改进解的质量。实验结果证明了基于线路重连算法（PR）的自适应蚁群算法（ACO）在求解该问题时的有效性。