A Preliminary Study on Feature-independent Hyper-heuristics for the 0/1 Knapsack Problem

Abstract

Recent years have witnessed an escalating interest for methods that automatically adapt to different types of problems. In this regard, the term hyper-heuristics -heuristics that either select or generate new heuristics- is a relevant concept. Experimental evidence supports the idea that hyper- heuristics can outperform single, isolated, heuristics. However, commonly used hyper-heuristic models require several inputs. One of them is a set of features that accurately characterize the instances, which limits their applicability. Thus, in this work, we analyze how to use a simple evolutionary algorithm to produce feature-independent hyper-heuristics. We compare the performance of such an approach against that of simple heuristics, for the domain of the knapsack problem. Our research focuses on two elements: performance and frequency. In the former, we analyze how the performance of the learning stage varies across different scenarios. In the latter, we examine how frequently heuristics interact within the hyper-heuristic. We show that the proposed hyper-heuristic model solves most of the instances considered in this work. Moreover, it does so more efficiently than isolated heuristics. At the same time, the model offers a straightforward parameter setting and requires little or no problem characterization, which simplifies its use on new problem domains.

Xavier F. C. Sánchez Díaz

PhD candidate in Artificial Intelligence

PhD candidate in Artificial Intelligence at the Department of Computer Science (IDI) of the Norwegian University of Science and Technology