Automated design of search algorithms: Learning on algorithmic components
Published in Expert Systems with Applications, 2021
Recommended citation: Meng, W., & Qu, R. (2021). Automated design of search algorithms: Learning on algorithmic components. Expert Systems with Applications, 185, 115493. https://doi.org/10.1016/j.eswa.2021.115493
Highlights
- A framework for automated design of local search algorithms.
- Various local search algorithms are modelled within the framework.
- The vehicle routing problems are used as the domain problem.
- Performance of elementary algorithmic components is analysed.
- Two learning models based on reinforcement learning and Markov chain are compared.
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.
Recommended citation:
@article{meng2021automated, title={Automated design of search algorithms: Learning on algorithmic components}, author={Meng, Weiyao and Qu, Rong}, journal={Expert Systems with Applications}, volume={185}, pages={115493}, year={2021}, publisher={Elsevier} }