Skip to main content

Research Repository

Advanced Search

A genetic programming hyper-heuristic for the multidimensional knapsack problem

Drake, John H.; Hyde, Matthew; Khaled, Ibrahim; Özcan, Ender

Authors

John H. Drake John.Drake@nottingham.edu.cn

Matthew Hyde

Ibrahim Khaled



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. © Emerald Group Publishing Limited.

Citation

Drake, J. H., Hyde, M., Khaled, I., & Özcan, E. (2014). A genetic programming hyper-heuristic for the multidimensional knapsack problem. Kybernetes, 43(9/10), doi:10.1108/K-09-2013-0201

Journal Article Type Article
Publication Date Mar 11, 2014
Deposit Date Mar 10, 2016
Publicly Available Date Mar 10, 2016
Journal Kybernetes
Print ISSN 0368-492X
Electronic ISSN 0368-492X
Publisher Emerald
Peer Reviewed Peer Reviewed
Volume 43
Issue 9/10
DOI https://doi.org/10.1108/K-09-2013-0201
Keywords Artificial intelligence, genetic programming, heuristic generation, hyper-heuristics, multidimensional knapsack problem
Public URL http://eprints.nottingham.ac.uk/id/eprint/32174
Publisher URL http://www.emeraldinsight.com/doi/full/10.1108/K-09-2013-0201
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

cis2012_GP_MKP.pdf (77 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations