Automated design of search algorithms: Learning on algorithmic components

Meng, Weiyao; Qu, Rong

Abstract

This paper proposes AutoGCOP, a new general framework for automated design of local search algorithms. In a recently established General Combinatorial Optimisation Problem (GCOP) model, the problem of algorithm design itself is defined as a combinatorial optimisation problem. AutoGCOP defines a general framework to optimise the composition of elementary algorithmic components as decision variables in GCOP. By modelling various well-known local search meta-heuristics within a general framework, AutoGCOP supports automatic design of new novel algorithms which may be highly different from those manually designed in the literature. Within the consistent AutoGCOP framework, various elementary algorithmic components are analysed for solving the benchmark vehicle routing problem with time window constraints and different characteristics. Furthermore, two learning models based on reinforcement learning and Markov chain are investigated to learn and enhance the compositions of algorithmic components towards the automated design of search algorithms. The Markov chain model presents superior performance learning the compositions of algorithmic components during the search, demonstrating its effectiveness designing new algorithms automatically.

Citation

Meng, W., & Qu, R. (2021). Automated design of search algorithms: Learning on algorithmic components. Expert Systems with Applications, 185, Article 115493. https://doi.org/10.1016/j.eswa.2021.115493

• Journal Article Type: Article
• Acceptance Date: Jun 24, 2021
• Online Publication Date: Jul 22, 2021
• Publication Date: Dec 15, 2021
• Deposit Date: Jul 26, 2021
• Publicly Available Date: Jul 23, 2022
• Journal: Expert Systems with Applications
• Print ISSN: 0957-4174
• Electronic ISSN: 0957-4174
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 185
• Article Number: 115493
• DOI: https://doi.org/10.1016/j.eswa.2021.115493
• Keywords: Artificial Intelligence; Computer Science Applications; General Engineering
• Public URL: https://nottingham-repository.worktribe.com/output/5817542
• Publisher URL: https://www.sciencedirect.com/science/article/abs/pii/S0957417421009039?via%3Dihub