Automatic parameter configuration for an elite solution hyper-heuristic applied to the Multidimensional Knapsack Problem

摘要

Hyper-heuristics are methods for problem solving that decouple the search mechanisms from the domain features, providing a reusable approach across different problems. Even when they make a difference regarding metaheuristics under this perspective, proposals in literature commonly expose parameters for controlling their behavior such as metaheuristics does. Several internal mechanisms for automatically adapt those parameters can be implemented, but they require extra design effort and their validation no necessarily is generalizable to multiple domains. Such effort is prohibitive for their practical application on decision-support systems. Rather than implementing internal adapting mechanisms, the exploration of automatic parameter configuration through external tools is performed in this work. A new hyper-heuristic implementation based on a elite set of solutions was implemented and automatically configured with SMAC (Sequential Model-Based Algorithm Configuration), a state-of-art tool for automatic parameter configuration. Experiments with and without automated configuration are performed over the Multidimensional Knapsack Problem (MKP). Comparative results demonstrate the effectiveness of the tool for improving the algorithm performance. Additionally, results provided insights that configurations applied over subsets of instances could provide better improvements in the algorithm performance.