计算机应用 ›› 2017, Vol. 37 ›› Issue (6): 1686-1691.DOI: 10.11772/j.issn.1001-9081.2017.06.1686

• 人工智能 • 上一篇    下一篇

求解TSP的改进信息素二次更新与局部优化蚁群算法

许凯波, 鲁海燕, 程毕芸, 黄洋   

  1. 江南大学 理学院, 江苏 无锡 214122
  • 收稿日期:2016-12-06 修回日期:2017-03-01 出版日期:2017-06-10 发布日期:2017-06-14
  • 通讯作者: 鲁海燕
  • 作者简介:许凯波(1992-),男,山西晋城人,硕士研究生,CCF会员,主要研究方向:最优化与控制;鲁海燕(1970-),女,山东淄博人,副教授,博士,主要研究方向:组合最优化、智能算法;程毕芸(1992-),女,安徽马鞍山人,硕士研究生,CCF会员,主要研究方向:最优化与控制;黄洋(1991-),男,河南信阳人,硕士研究生,CCF会员,主要研究方向:最优化与控制。
  • 基金资助:
    国家自然科学基金资助项目(11371174);中央高校基本科研业务费专项资金资助项目(1142050205135260,JUSRP51317B)。

Ant colony optimization algorithm based on improved pheromones double updating and local optimization for solving TSP

XU Kaibo, LU Haiyan, CHENG Biyun, HUANG Yang   

  1. School of Science, Jiangnan University, Wuxi Jiangsu 214122, China
  • Received:2016-12-06 Revised:2017-03-01 Online:2017-06-10 Published:2017-06-14
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (11371174), the Fundamental Research Funds for the Central Universities (1142050205135260, JUSRP51317B).

摘要: 针对蚁群(ACO)算法收敛速度慢、容易陷入局部最优的缺陷,提出了一种改进信息素二次更新局部优化蚁群算法(IPDULACO)。该算法对蚁群搜索到的当前全局最优解中路径贡献度大于给定的路径贡献阈值的子路径信息素进行二次更新,以提高构成潜在最优解的子路径被选择的概率,从而加快算法的收敛。然后,在搜索过程中,当蚁群陷入局部最优时,使用随机插入法对局部最优解中城市的排序进行调整,以增强算法跳出局部最优解的能力。将改进算法应用于若干经典的旅行售货商问题(TSP)进行仿真实验,实验结果表明,对于小规模的TSP,IPDULACO可以在较少的迭代次数内获得已知最优解;对于较大规模的TSP,IPDULACO可以在较少的迭代次数内获得更精确的解。因此,IPDULACO具有更强的搜索全局最优解的能力和更快的收敛速度,可以高效求解TSP。

关键词: 旅行售货商问题, 蚁群算法, 信息素二次更新, 局部优化

Abstract: Concerning the drawbacks of the Ant Colony Optimization (ACO) algorithm such as low convergence rate and being easy to fall into local optimum solutions, an ACO algorithm based on Improved Pheromones Double Updating and Local Optimization (IPDULACO) was proposed. Double updating was performed on the pheromones of subpaths whose path contribution degrees to the current global optimal solution obtained by colony were bigger than the prescribed path contribution threshold. The selected probability of the subpaths which were used to constitute the potential optimal solution was increased and the convergence rate of the proposed algorithm was accelerated. Then, when the ant colony fell into the local optimal solution in the search process, the random insertion method was utilized to change the city sequences of the current local optimal solution in order to enhance the algorithm's ability of jumping out of local optimal solution. The improved algorithm was applied to several classical Traveling Salesman Problem (TSP) instances in the simulation experiments. The experimental results show that, for small-size TSP instances, the IPDULACO can obtain the known optimal solution in less number of iterations. For relatively large-size TSP instances, the IPDULACO can obtain the optimal solution with higher accuracy in less number of iterations. Therefore, the IPDULACO has the stronger ability of searching for the global optimal solution and faster convergence rate, and it can be used for solving TSP effectively.

Key words: Traveling Salesman Problem (TSP), Ant Colony Optimization (ACO) algorithm, pheromones double updating, local optimization

中图分类号: