Automated Design of Metaheuristics Using Reinforcement Learning Within a Novel General Search Framework

作     者：Yi, Wenjie Qu, Rong Jiao, Licheng Niu, Ben 

作者机构：Univ Nottingham Sch Comp Sci Computat Optimisat & Learning Lab Nottingham NG8 1BB England Xidian Univ Sch Artificial Intelligence Key Lab Intelligent Percept & Image Understanding Minist Educ Xian 710071 Peoples R China Shenzhen Univ Coll Management Shenzhen 518060 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION》 (IEEE Trans Evol Comput)

年 卷 期：2023年第27卷第4期

页      面：1072-1084页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：School of Computer Science  University of Nottingham  U.K 

主　　题：Automated algorithm design general search framework metaheuristic reinforcement learning vehicle routing problem 

摘      要：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.