A genetic programming hyper-heuristic for the multidimensional knapsack problem. Issue 9 (28th October 2014)

• Record Type: Journal Article
• Authors: H. Drake, John; Hyde, Matthew; Ibrahim, Khaled; Ozcan, Ender
• Editors: Glanville, Ranulph; Griffiths, David; Baron, Philip
• Is Part Of: Kybernetes. Volume 43:Issue 9/10(2014)
• Page Start: 1500
• Page End: 1511
• Publication Date: 2014-10-28
• Subjects: Artificial intelligence -- Genetic programming -- Heuristic generation -- Hyper-heuristics -- Multidimensional knapsack problem; Cybernetics -- Periodicals; Systems engineering -- Periodicals; 003.505
• DOI: 10.1108/K-09-2013-0201
• Languages: English
• ISSNs: 0368-492X

Abstract

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.