A genetic programming hyper-heuristic for the multidimensional knapsack problem
Article publication date: 3 November 2014
Hyper-heuristics are a class of high-level search techniques which operate on a search space of heuristics rather than directly on a search space of solutions. The purpose of this paper is to investigate the suitability of using genetic programming as a hyper-heuristic methodology to generate constructive heuristics to solve the multidimensional 0-1 knapsack problem
Early hyper-heuristics focused on selecting and applying a low-level heuristic at each stage of a search. Recent trends in hyper-heuristic research have led to a number of approaches being developed to automatically generate new heuristics from a set of heuristic components. A population of heuristics to rank knapsack items are trained on a subset of test problems and then applied to unseen instances.
The results over a set of standard benchmarks show that genetic programming can be used to generate constructive heuristics which yield human-competitive results.
In this work the authors show that genetic programming is suitable as a method to generate reusable constructive heuristics for the multidimensional 0-1 knapsack problem. This is classified as a hyper-heuristic approach as it operates on a search space of heuristics rather than a search space of solutions. To our knowledge, this is the first time in the literature a GP hyper-heuristic has been used to solve the multidimensional 0-1 knapsack problem. The results suggest that using GP to evolve ranking mechanisms merits further future research effort.
An earlier version of this article was presented at the 11th IEEE Conference on Cybernetic Intelligent Systems (CIS 2012) in Limerick, Ireland, in August 2012.
Drake, J.H., Hyde, M., Ibrahim, K. and Ozcan, E. (2014), "A genetic programming hyper-heuristic for the multidimensional knapsack problem", Kybernetes, Vol. 43 No. 9/10, pp. 1500-1511. https://doi.org/10.1108/K-09-2013-0201
Emerald Group Publishing Limited
Copyright © 2014, Emerald Group Publishing Limited