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