Automated Design of Metaheuristics Using Reinforcement Learning Within a Novel General Search Framework
提出一个通用搜索框架，统一描述多种元启发式算法，并基于该框架开发两种强化学习方法，自动设计出能智能选择算法组件的新算法，在带时间窗的车辆路径问题上验证了有效性。
Metaheuristic algorithms have been investigated intensively to address highly complex combinatorial optimization problems. However, most metaheuristic algorithms have been designed manually by researchers of different expertise without a consistent framework. This article proposes a general search framework (GSF) to formulate in a unified way a range of different metaheuristics. With generic algorithmic components, including selection heuristics and evolution operators, the unified GSF aims to serve as the basis of analyzing algorithmic components for automated algorithm design. With the established new GSF, two reinforcement learning (RL)-based methods, deep <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Q$ </tex-math></inline-formula> -network based and proximal policy optimization-based methods, have been developed to automatically design a new general population-based algorithm. The proposed RL-based methods are able to intelligently select and combine appropriate algorithmic components during different stages of the optimization process. The effectiveness and generalization of the proposed RL-based methods are validated comprehensively across different benchmark instances of the capacitated vehicle routing problem with time windows. This study contributes to making a key step toward automated algorithm design with a general framework supporting fundamental analysis by effective machine learning.