Algorithm selection using deep learning without feature extraction

Alissa, Mohamad; Sim, Kevin; Hart, Emma

Abstract

We propose a novel technique for algorithm-selection which adopts a deep-learning approach, specifically a Recurrent-Neural Network with Long-Short-Term-Memory (RNN-LSTM). In contrast to the majority of work in algorithm-selection, the approach does not need any features to be extracted from the data but instead relies on the temporal data sequence as input. A large case-study in the domain of 1-d bin packing is undertaken in which instances can be solved by one of four heuristics. We first evolve a large set of new problem instances that each have a clear "best solver" in terms of the heuristics considered. An RNN-LSTM is trained directly using the sequence data describing each instance to predict the best performing heuristic. Experiments conducted on small and large problem instances with item sizes generated from two different probability distributions are shown to achieve between 7% to 11% improvement over the single best solver (SBS) (i.e. the single heuristic that achieves the best performance over the instance set) and 0% to 2% lower than the virtual best solver (VBS), i.e the perfect mapping.

Citation

Alissa, M., Sim, K., & Hart, E. (2019, July). Algorithm selection using deep learning without feature extraction. Presented at Genetic and Evolutionary Computing Conference (GECCO) 2019, Prague, Czech Republic

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Genetic and Evolutionary Computing Conference (GECCO) 2019
• Start Date: Jul 13, 2019
• End Date: Jul 17, 2019
• Acceptance Date: Mar 21, 2019
• Publication Date: Jul 13, 2019
• Deposit Date: Apr 16, 2019
• Publicly Available Date: Jul 13, 2019
• Publisher: Association for Computing Machinery (ACM)
• Pages: 198-206
• Book Title: GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion
• ISBN: 978-1-4503-6748-6
• DOI: https://doi.org/10.1145/3321707.3321845
• Keywords: Deep Learning, Recurrent Neural Network, Algorithm Selection
• Public URL: http://researchrepository.napier.ac.uk/Output/1732820
• Contract Date: Apr 16, 2019