- author = "John H. Drake and Matthew Hyde and Khaled Ibrahim and Ender Ozcan",
- title = "A genetic programming hyper-heuristic for the multidimensional knapsack problem",
- journal = "Kybernetes",
- year = "2014",
- volume = "43",
- number = "9/10",
- pages = "1500--1511",
- keywords = "genetic algorithms, genetic programming, Artificial intelligence, Heuristic generation, Hyper-heuristics, Multidimensional knapsack problem",
- ISSN = "0368-492X",
-
URL = "
http://eprints.nottingham.ac.uk/id/eprint/32174",
-
URL = "http://www.emeraldinsight.com/doi/full/10.1108/K-09-2013-0201",
-
DOI = "
doi:10.1108/K-09-2013-0201",
-
abstract = "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
Design/methodology/approach
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.
Findings
The results over a set of standard benchmarks show that genetic programming can be used to generate constructive heuristics which yield human-competitive results.
Originality/value
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",
- notes = "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.",
