Automated algorithm design using proximal policy optimisation with identified features

Yi, Wenjie; Qu, Rong; Jiao, Licheng

Abstract

Automated algorithm design is attracting considerable recent research attention in solving complex combinatorial optimisation problems, due to that most metaheuristics may be particularly effective at certain problems or certain instances of the same problem but perform poorly at others. Within a general algorithm design framework, this study investigates reinforcement learning on the automated design of metaheuristic algorithms. Two groups of features, namely search-dependent and instance-dependent features, are firstly identified to represent the search space of algorithm design to support effective reinforcement learning on the new task of algorithm design. With these key features, a state-of-the-art reinforcement learning technique, namely proximal policy optimisation, is employed to automatically combine the basic algorithmic components within the general framework to develop effective metaheuristics. Patterns of the best designed algorithm, in particular the utilisation and transition of algorithmic components, are investigated. Experimental results on the capacitated vehicle routing problem with time windows benchmark dataset demonstrate the effectiveness of the identified features in assisting automated algorithm design with the proposed reinforcement learning model.

Citation

Yi, W., Qu, R., & Jiao, L. (2023). Automated algorithm design using proximal policy optimisation with identified features. Expert Systems with Applications, 216, Article 119461. https://doi.org/10.1016/j.eswa.2022.119461

• Journal Article Type: Article
• Acceptance Date: Dec 22, 2022
• Online Publication Date: Dec 28, 2022
• Publication Date: Apr 15, 2023
• Deposit Date: Jan 10, 2023
• Publicly Available Date: Dec 29, 2023
• Journal: Expert Systems with Applications
• Print ISSN: 0957-4174
• Publisher: Elsevier BV
• Peer Reviewed: Peer Reviewed
• Volume: 216
• Article Number: 119461
• DOI: https://doi.org/10.1016/j.eswa.2022.119461
• Keywords: Artificial Intelligence; Computer Science Applications; General Engineering
• Public URL: https://nottingham-repository.worktribe.com/output/15436671
• Publisher URL: https://www.sciencedirect.com/science/article/abs/pii/S0957417422024800?via%3Dihub