首页 | 本学科首页   官方微博 | 高级检索  
     

用于求解旅行商问题的深度智慧型蚁群优化算法
引用本文:王原,陈名,邢立宁,吴亚辉,马武彬,赵宏.用于求解旅行商问题的深度智慧型蚁群优化算法[J].计算机研究与发展,2021,58(8):1586-1598.
作者姓名:王原  陈名  邢立宁  吴亚辉  马武彬  赵宏
作者单位:1.1(国防科技大学系统工程学院 长沙 410073);2.2(湖南安全技术职业学院 长沙 410151) (wy1020395067@hotmail.com)
基金项目:国家自然科学基金;高等学校全国优秀博士学位论文作者专项
摘    要:启发式算法是求解组合优化问题求解的重要手段,其主要特征是能够以可接受的计算代价找到足够好的可行解.然而,设计良好的用于求解组合优化问题的启发式算法需要大量的专业领域知识以及大量的试错工作,且人工设计的启发式算法不能够保证在不同问题集上均具有一致性表现.另一方面,深度学习方法能够通过学习自动设计启发式规则,然而深度学习方法通常缺少在解空间内搜索的能力.为克服以上问题,提出了一种基于蚁群优化和深度强化学习的混合启发式算法框架.在该框架中,蚁群算法能够利用深度强化学习提取的启发式信息,而深度强化学习方法的解空间搜索性能也由于蚁群算法的加入而获得提高.采用经典的TSPLIB中的算例对该算法求解旅行商问题的效能进行了计算验证,结果表明采用深度学习方法能够极大地提升蚁群算法的计算表现,并降低其计算代价.

关 键 词:深度强化学习  蚁群优化算法  端到端学习  混合元启发式算法  旅行商问题

Deep Intelligent Ant Colony Optimization for Solving Travelling Salesman Problem
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.
Authors:Wang Yuan  Chen Ming  Xing Lining  Wu Yahui  Ma Wubin  Zhao Hong
Affiliation:1.1(College of Systems Engineering, National University of Defense Technology, Changsha 410073);2.2(Hunan Vocational Institute of Safety Technology, Changsha 410151)
Abstract: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.
Keywords:deep reinforcement learning  ant colony optimization  end-to-end learning  hybrid meta-heuristics  travelling salesman problem
本文献已被 万方数据 等数据库收录!
点击此处可从《计算机研究与发展》浏览原始摘要信息
点击此处可从《计算机研究与发展》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号