Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches
Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches
复制标题
DOI：
10.1007/s10732-022-09505-4
复制
发表时间：
2022-03
影响因子：
2.7
通讯作者：
M. Alissa;Kevin Sim;E. Hart
中科院分区：
文献类型：
--
作者：
M. Alissa;Kevin Sim;E. Hart
我们提出了一种新的算法选择技术，适用于数据中隐含顺序信息的优化领域，例如在线装箱。具体地说，我们训练了两种类型的递归神经网络来预测在线装箱中的装箱启发式，从四个著名的启发式算法中进行选择。作为输入，RNN方法只使用项目大小的序列。这与算法选择的典型方法形成对比，后者要求使用需要首先从输入数据导出的特定领域的实例特征来训练模型。根据数据集的不同，RNN方法能够在80.88%到97.63%的实例上实现5%的Oracle性能。研究还表明，它们的性能优于使用派生特征训练的经典机器学习模型。最后，我们假设，当实例表现出某种隐式结构，导致相对于一组启发式规则的歧视性性能时，所提出的方法执行得很好。我们通过生成14个结构级别不断增加的新数据集来测试这一假设，并表明在算法选择带来好处之前，需要一个关键的结构阈值。
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.