Machine-learning-based hyper-heuristics for solving the Knapsack Problem Academic Article in Scopus uri icon

abstract

  • Combinatorial optimization problems are challenging, mainly due to the exponential growth in the search space concerning the number of input variables. In this regard, many approximated methods, such as heuristics, have been proposed in the literature to produce good-quality solutions at low resource consumption. Of course, this rationale implies a severe trade-off because `cheap¿ methods can unlikely obtain optimum solutions. A hyper-heuristic is a more intelligent approach that aims to combine the strengths of individual heuristics by choosing which one to apply according to some features that allow for the comparison of instances. If two instances are alike, it is likely that one heuristic that performed well on one also performs well on the other, which is similar. Although many approaches to producing hyper-heuristics are available in the literature, we focus on those powered by machine learning in this work. Specifically, we formulate our hyper-heuristics as classifiers, where the inputs are the features that characterize the instances, and the output is the heuristic we must apply, given such characterization. In this context, we evaluate the performance of five machine learning models on various sets of instances with particular features. Such features allow us to test generality and scalability issues related to hyper-heuristics implemented with machine learning models. Besides, we also included another hyper-heuristic approach taken from the literature into the analysis to validate our proposal. Our results confirm the potential of our approach and the benefits derived from choosing the right heuristic for particular instances. © 2025 Elsevier B.V.

publication date

  • January 1, 2025