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 $Q$ -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.