• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Wang Yuan, Chen Ming, Xing Lining, Wu Yahui, Ma Wubin, Zhao Hong. Deep Intelligent Ant Colony Optimization for Solving Travelling Salesman Problem[J]. Journal of Computer Research and Development, 2021, 58(8): 1586-1598. DOI: 10.7544/issn1000-1239.2021.20210320
Citation: Wang Yuan, Chen Ming, Xing Lining, Wu Yahui, Ma Wubin, Zhao Hong. Deep Intelligent Ant Colony Optimization for Solving Travelling Salesman Problem[J]. Journal of Computer Research and Development, 2021, 58(8): 1586-1598. DOI: 10.7544/issn1000-1239.2021.20210320

Deep Intelligent Ant Colony Optimization for Solving Travelling Salesman Problem

Funds: This work was supported by the National Natural Science Foundation of China (61773120) and the Foundation for the Author of National Excellent Doctoral Dissertation of China (2014-92).
More Information
  • Published Date: July 31, 2021
  • Heuristic algorithms are important methods for solving combinatorial optimization problems since heuristic algorithms can find feasible solutions with reasonable computational consumption. Heuristic design of combinatorial optimization problem is an important research field of combinatorial optimization society. However, designing heuristic algorithms need lots of special domain knowledge and years of trial-and-error, and algorithm performance of manually designed heuristics normally have no guarantee on different problem scenarios. On the other hand, deep learning approaches have the ability of designing heuristics automatically, but they lack the ability of searching in solution space. To overcome these disadvantages, in this article, we propose a hybrid meta-heuristic algorithm framework which is a combination of deep reinforcement learning method and ant colony optimization. In this algorithm, ant colony optimization is benefited from heuristic information learned by deep reinforcement learning method. And the solution searching ability of deep reinforcement learning method is also improved since the ant colony optimization is implemented. To test the algorithm performance, instances with different problem scales selected from TSPLIB are tested. Comparison algorithms include ant based heuristics and reinforcement learning methods. Experimental results show that the deep reinforcement learning method significantly improves both the algorithm proficiency and convergence performance of ant colony optimization algorithm.
  • Related Articles

    [1]Dong Xueshi, Dong Wenyong, Cai Yongle. Hybrid Algorithm for Colored Bottleneck Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2018, 55(11): 2372-2385. DOI: 10.7544/issn1000-1239.2018.20180009
    [2]Dong Xueshi, Dong Wenyong, Wang Yufeng. Hybrid Algorithms for Multi-Objective Balanced Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2017, 54(8): 1751-1762. DOI: 10.7544/issn1000-1239.2017.20170347
    [3]Feng Xiang, Ma Meiyi, and Yu Huiqun. Lake-Energy Optimization Algorithm for Travelling Salesman Problem[J]. Journal of Computer Research and Development, 2013, 50(9): 2015-2027.
    [4]Wang Gang and Luo Zhigang. A Polynomial Time Approximation Scheme for the Traveling Salesman Problem in Curved Surfaces[J]. Journal of Computer Research and Development, 2013, 50(3): 657-665.
    [5]Li Ziqiang, Tian Zhuojun, Wang Yishou, Yue Benxian. A Fast Heuristic Parallel Ant Colony Algorithm for Circles Packing Problem with the Equilibrium Constraints[J]. Journal of Computer Research and Development, 2012, 49(9): 1899-1909.
    [6]Ji Junzhong, Huang Zhen, Liu Chunnian, and Dai Qiguo. An Ant Colony Algorithm Based on Multiple-Grain Representation for the Traveling Salesman Problems[J]. Journal of Computer Research and Development, 2010, 47(3): 434-444.
    [7]Ji Junzhong, Huang Zhen, and Liu Chunnian. A Fast Ant Colony Optimization Algorithm for Traveling Salesman Problems[J]. Journal of Computer Research and Development, 2009, 46(6): 968-978.
    [8]Chen Mao, Huang Wenqi. A Heuristic Algorithm for the Unequal Circle Packing Problem[J]. Journal of Computer Research and Development, 2007, 44(12): 2092-2097.
    [9]Jiang He, Zhang Xianchao, Che Haoyang, Chen Guoliang. A Multi-Commodity Flow Linear Programming with Polynomial Constraints for Black and White Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2007, 44(10): 1796-1800.
    [10]Zhao Weizhong, Feng Haodi, and Zhu Daming. Improvement and Implementation of a Polynomial Time Approximation Scheme for Euclidean Traveling Salesman Problem[J]. Journal of Computer Research and Development, 2007, 44(10): 1790-1795.
  • Cited by

    Periodical cited type(27)

    1. 章政,夏小云,陈泽丰,向毅. 融合强化学习的分阶段策略求解旅行背包问题. 计算机工程与科学. 2025(01): 140-149 .
    2. 韩润华. 动态虚拟多任务智能水滴算法求解TSP问题. 电脑知识与技术. 2025(06): 15-21 .
    3. 唐存花,汤可宗. 求旅行商问题的幂律变换优化蚁群算法. 软件导刊. 2024(02): 74-83 .
    4. 韩希君,郑勇,孙国思. 基于改进果蝇算法的车架焊接机器人避障路径规划. 焊接技术. 2024(03): 90-94 .
    5. 褚宏悦,易军凯. 无人机安全路径规划的混沌粒子群优化研究. 控制工程. 2024(06): 1027-1034 .
    6. 李娟,金志雄. 基于轻量化Transformer的农作物检测机器人路径规划. 中国农机化学报. 2024(09): 227-233 .
    7. 江新姿,安晓丽,高尚. 基于MTSP问题的公共图书馆智慧配送服务. 计算机与现代化. 2024(09): 52-55+60 .
    8. 禹博文,游晓明,刘升. 基于空间聚焦机制的混沌随机蚁群算法. 智能计算机与应用. 2024(09): 1-9 .
    9. 邱鹤庆. 基于贪婪算法和ACO的无人机测绘路径规划算法. 智能城市. 2024(10): 59-61 .
    10. 刘宇,赵辉. 蚁群算法下焊接机器人焊缝表面图像裂纹检测. 计算机仿真. 2024(11): 215-219 .
    11. 董黎明,程美英. 求解多式联运问题的异构多任务优化蚁群算法. 计算机仿真. 2024(12): 189-196 .
    12. 杨笑笑,柯琳,陈智斌. 深度强化学习求解车辆路径问题的研究综述. 计算机工程与应用. 2023(05): 1-13 .
    13. 郭城成,田立勤,武文星. 蚁群算法在求解旅行商问题中的应用综述. 计算机系统应用. 2023(03): 1-14 .
    14. 凌畅,吴富强,陈晓峰. 基于蚁群算法的机头结构二级布局优化方法. 航空计算技术. 2023(02): 55-59 .
    15. 刘静,杨雪,陈伟,陈巍. 无缆自治水下机器人运动控制参数整定方法. 计算机仿真. 2023(03): 421-425 .
    16. 郭洪升,李忠伟,罗偲,任旭虎. 基于混合人工蜂群算法和A~*算法的求解旅行商问题算法. 科学技术与工程. 2023(11): 4718-4724 .
    17. 付豪. 融合改进A*和蚁群算法的多目标路径规划. 信息技术与信息化. 2023(09): 39-42 .
    18. 孙茂荣,赵泽阳. 基于遗传算法的管板爬行机器人检修路径规划. 制造业自动化. 2023(11): 117-121 .
    19. 杨笑笑,陈智斌. 深度混合型邻域搜索模型求解CVRP问题. 南京大学学报(自然科学). 2023(06): 1023-1033 .
    20. 徐江,程美英. 面向路径规划问题的虚拟多任务共生生物搜索算法. 计算机应用研究. 2023(12): 3599-3605+3613 .
    21. 段丽妮,阚龙营. 基于蚁群算法的多车型物流车辆调度研究. 物流科技. 2022(04): 14-17 .
    22. 陈嘉珣,闫国玉,张捷. 基于改进蚁群算法的警用装备管理平台的设计. 工业控制计算机. 2022(04): 144-146 .
    23. 张硕航,郭改枝. 多旅行商模型及其应用研究综述. 计算机科学与探索. 2022(07): 1516-1528 .
    24. 孙晗,周全,杨志军. 应用TSP的纤维检测装置扫描路径优化. 西安工程大学学报. 2022(04): 26-33 .
    25. 汤超龙,赵永强,刘芯羽. 基于蚁群算法的二维多层亚波长光栅结构设计. 红外与毫米波学报. 2022(04): 756-761 .
    26. 姚拓中. 基于粒子群优化和改进蚁群算法的电力供应链博弈分析. 浙江电力. 2022(09): 80-85 .
    27. 汪帅,郑红,卢楠,李晖,彭检贵,董雅雯. 林草智慧巡护管理系统设计与应用. 林业资源管理. 2022(06): 145-150 .

    Other cited types(28)

Catalog

    Article views (848) PDF downloads (567) Cited by(55)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return