An Exploratory Study on Machine-Learning-Based Hyper-heuristics for the Knapsack Problem

Hyper-heuristics have risen as a recurrent method to solve combinatorial optimization problems since they use a set of heuristics selectively according to the problem state. Although many ideas have been developed to produce hyper-heuristics, a recent trend involves treating the heuristic selection problem as a classification one. This allows the introduction of machine learning elements into the hyper-heuristic process. This work explores creating hyper-heuristics using Machine Learning classifiers to solve the Knapsack Problem, a fascinating and well-studied combinatorial problem. We propose two approaches to these hyper-heuristics: a dynamical approach, where the hyper-heuristic may change heuristics throughout the whole solving process, and a static approach, where the hyper-heuristic makes one initial choice of heuristic and no further changes are allowed. Our results confirm that hyper-heuristics powered by machine learning techniques can deal with the Knapsack problem and obtain competent results. Besides, we also observed a clear superiority in the performance of the hyper-heuristics running under the static approach concerning the dynamic counterpart.