A genetic programming hyper-heuristic for the multidimensional knapsack problem

John H Drake (School of Computer Science, University of Nottingham, Nottingham, UK)
Matthew Hyde (School of Computer Science, University of Nottingham, Nottingham, UK)
Khaled Ibrahim (School of Computer Science, University of Nottingham, Nottingham, UK)
Ender Ozcan (School of Computer Science, University of Nottingham, Nottingham, UK)

Kybernetes

ISSN: 0368-492X

Publication date: 3 November 2014

Abstract

Purpose

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

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.

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.

Keywords

Acknowledgements

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.

Citation

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

Publisher

:

Emerald Group Publishing Limited

Copyright © 2014, Emerald Group Publishing Limited

To read the full version of this content please select one of the options below

You may be able to access this content by logging in via Shibboleth, Open Athens or with your Emerald account.
To rent this content from Deepdyve, please click the button.
If you think you should have access to this content, click the button to contact our support team.