ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2021, Vol. 58 ›› Issue (8): 1586-1598.doi: 10.7544/issn1000-1239.2021.20210320

Special Issue: 2021人工智能前沿进展专题

Previous Articles     Next Articles

Deep Intelligent Ant Colony Optimization for Solving Travelling Salesman Problem

Wang Yuan1, Chen Ming1, Xing Lining1, Wu Yahui1, Ma Wubin1, Zhao Hong2   

  1. 1(College of Systems Engineering, National University of Defense Technology, Changsha 410073);2(Hunan Vocational Institute of Safety Technology, Changsha 410151)
  • Online:2021-08-01
  • Supported by: 
    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).

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.

Key words: deep reinforcement learning, ant colony optimization, end-to-end learning, hybrid meta-heuristics, travelling salesman problem

CLC Number: