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

Yi, Wenjie; Qu, Rong; Jiao, Licheng; Niu, Ben

Abstract

Metaheuristic algorithms have been investigated intensively to address highly complex combinatorial optimisation problems. However, most metaheuristic algorithms have been designed manually by researchers of different expertise without a consistent framework to support effective algorithm design. This paper proposes a general search framework to formulate in a unified way a range of different metaheuristics. This framework defines generic algorithmic components, including selection heuristics and evolution operators. The unified general search framework aims to serve as the basis of analysing algorithmic components for automated algorithm design. With the established new general search framework, two reinforcement learning based methods, deep Q-network based and proximal policy optimisation based methods, have been developed to automatically design a new general population-based algorithm. The proposed reinforcement learning based methods are able to intelligently select and combine appropriate algorithmic components during different stages of the optimisation process. The effectiveness and generalization of the proposed reinforcement learning 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 towards automated algorithm design with a general framework supporting fundamental analysis by effective machine learning.

Citation

Yi, W., Qu, R., Jiao, L., & Niu, B. (2023). Automated Design of Metaheuristics Using Reinforcement Learning within a Novel General Search Framework. IEEE Transactions on Evolutionary Computation, 27(4), 1072-1084. https://doi.org/10.1109/TEVC.2022.3197298

• Journal Article Type: Article
• Acceptance Date: Jul 31, 2022
• Online Publication Date: Aug 9, 2022
• Publication Date: 2023-08
• Deposit Date: Aug 15, 2022
• Publicly Available Date: Aug 15, 2022
• Journal: IEEE Transactions on Evolutionary Computation
• Print ISSN: 1089-778X
• Electronic ISSN: 1941-0026
• Publisher: Institute of Electrical and Electronics Engineers
• Peer Reviewed: Peer Reviewed
• Volume: 27
• Issue: 4
• Pages: 1072-1084
• DOI: https://doi.org/10.1109/TEVC.2022.3197298
• Keywords: Computational Theory and Mathematics, Theoretical Computer Science, Software
• Public URL: https://nottingham-repository.worktribe.com/output/9907016
• Publisher URL: https://ieeexplore.ieee.org/document/9852781