Skip to main content

Research Repository

Advanced Search

Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches

Alissa, Mohamad; Sim, Kevin; Hart, Emma

Authors

Mohamad Alissa



Abstract

We propose a novel technique for algorithm-selection, applicable to optimisation domains in which there is implicit sequential information encapsulated in the data, e.g., in online bin-packing. Specifically we train two types of recurrent neural networks to predict a packing heuristic in online bin-packing, selecting from four well-known heuristics. As input, the RNN methods only use the sequence of item-sizes. This contrasts to typical approaches to algorithm-selection which require a model to be trained using domain-specific instance features that need to be first derived from the input data. The RNN approaches are shown to be capable of achieving within 5% of the oracle performance on between 80.88 and 97.63% of the instances, depending on the dataset. They are also shown to outperform classical machine learning models trained using derived features. Finally, we hypothesise that the proposed methods perform well when the instances exhibit some implicit structure that results in discriminatory performance with respect to a set of heuristics. We test this hypothesis by generating fourteen new datasets with increasing levels of structure, and show that there is a critical threshold of structure required before algorithm-selection delivers benefit.

Journal Article Type Article
Acceptance Date Oct 25, 2022
Online Publication Date Jan 9, 2023
Publication Date 2023-02
Deposit Date Jan 4, 2023
Publicly Available Date Jan 4, 2023
Journal Journal of Heuristics
Print ISSN 1381-1231
Electronic ISSN 1572-9397
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 29
Issue 1
Pages 1-38
DOI https://doi.org/10.1007/s10732-022-09505-4
Keywords Deep learning, Machine learning, Recurrent neural network, Algorithm selection, Bin-packing problem, Feature-free approach
Public URL http://researchrepository.napier.ac.uk/Output/2957895

Files







You might also like



Downloadable Citations