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

An adaptive ACO algorithm based on PR for solving traveling salesman problem

以著名的旅行商问题为研究对象,研究了基于线路重连(PR)算法的自适应蚁群算法(ACO)的应用。根据蚁群算法构解过程中的选择策略与信息素更新机制,提出了自适应的蚁群优化方法,即通过阈值接收算法(TA)中的阈值控制参数改变蚁群的确定选择与随机选择机会,从而控制了搜索方向。采用这种自适应的蚁群优化算法,避免蚁群算法陷入局部最优,使对解空间的更好地进行搜索。同时,在蚁群优化算法(ACO)中,嵌入路径重连算法(PR)来改进解的质量。实验结果证明了基于线路重连算法(PR)的自适应蚁群算法(ACO)在求解该问题时的有效性。

To solve the famous traveling salesman problem,the application of adaptive ant colony algorithmbased on path-relinking algorithm was studied in this paper. According to the process of selection strategy andinformation pheromone updating mechanism of the ant colony algorithm,the adaptive ant colony optimizationmethod was presented,i.e. the selection and random choice of ant colony were determined and the search dirctionwas controlled by optimum of the threshold parameters of the threshold algorithm. This adaptive ant colonyoptimization algorithm is used to search the solution space more effectively,which can effectively avoidfrom falling into local optimum. At the same time,in the ACO,path-relinking procedure is embedded into itto improve the solutions. The experimental results show that the adaptive ACO is very efficient and competitiveto solve the traveling salesman problem in terms of solution quality.