From algorithm selection to generation using deep learning

Algorithm selection and generation techniques are two methods that can be used to exploit the performance complementarity of different algorithms when applied to large diverse sets of combinatorial problem instances. As there is no single algorithm that dominates all others on all problem instances, algorithm selection automatically selects an algorithm expected to perform best for each problem instance. Meanwhile, algorithm generation refers to combining different algorithms in a manner that allows the resulting method to improve the efficacy of a pool of algorithms. This thesis examines algorithm selection and generation within a single streaming problem domain, that is Bin-Packing, where novel approaches are proposed and evaluated on large problem sets. This research starts with presenting a novel feature-free approach to select the best performing heuristic by capturing the sequential information implicit in a streaming instance and using this as direct input to two Deep Learning (DL) models, Long-Short-Term Memory (LSTM) or Gated Recurrent Unit (GRU), to learn a mapping from an instance to an algorithm. Results obtained using the proposed approach show that the performance of the feature-free selectors significantly outperforms the performance of both the single best solver and the classical feature-based approach using well-known Machine Learning (ML) classifiers when applied to large sets of diverse problem instances. Next, a more radical approach is proposed: bypass algorithm selection altogether by training encoder-decoder LSTM using solutions obtained from a set of algorithms to directly predict a solution from the instance data behaving as an automatically generated algorithm. Experiments conducted on large datasets using problem batches of varying sizes show that the generated algorithm is able to accurately predict solutions, particularly with small batch sizes. Finally, the thesis develops the proposed encoder-decoder approach by introducing a novel neural approach for generating algorithms, in which a neural network acts as an algorithm by generating decisions. Two architectures are evaluated, an encoder-decoder LSTM and a feed-forward Neural Network (NN), and trained using the decisions output from existing algorithms on a large set of instances. Experiments show that the new generated algorithms are capable of solving a subset of instances better than the well-known bin-packing algorithms, and hence they can significantly improve the overall performance when they are added to a pool of algorithms