A genetic programming hyper-heuristic for the multidimensional knapsack problem
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 genera...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Emerald Group Publishing Ltd.
2014
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/32174/ |
| _version_ | 1848794349615185920 |
|---|---|
| author | Drake, John H. Hyde, Matthew Khaled, Ibrahim Özcan, Ender |
| author_facet | Drake, John H. Hyde, Matthew Khaled, Ibrahim Özcan, Ender |
| author_sort | Drake, John H. |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:14:47Z |
| format | Article |
| id | nottingham-32174 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:14:47Z |
| publishDate | 2014 |
| publisher | Emerald Group Publishing Ltd. |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-321742020-05-04T16:44:59Z https://eprints.nottingham.ac.uk/32174/ A genetic programming hyper-heuristic for the multidimensional knapsack problem Drake, John H. Hyde, Matthew Khaled, Ibrahim Özcan, Ender 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. Emerald Group Publishing Ltd. 2014-03-11 Article PeerReviewed Drake, John H., Hyde, Matthew, Khaled, Ibrahim and Özcan, Ender (2014) A genetic programming hyper-heuristic for the multidimensional knapsack problem. Kybernetes, 43 (9/10). pp. 1500-1511. ISSN 0368-492X Artificial intelligence genetic programming heuristic generation hyper-heuristics multidimensional knapsack problem http://www.emeraldinsight.com/doi/full/10.1108/K-09-2013-0201 doi:10.1108/K-09-2013-0201 doi:10.1108/K-09-2013-0201 |
| spellingShingle | Artificial intelligence genetic programming heuristic generation hyper-heuristics multidimensional knapsack problem Drake, John H. Hyde, Matthew Khaled, Ibrahim Özcan, Ender A genetic programming hyper-heuristic for the multidimensional knapsack problem |
| title | A genetic programming hyper-heuristic for the multidimensional knapsack problem |
| title_full | A genetic programming hyper-heuristic for the multidimensional knapsack problem |
| title_fullStr | A genetic programming hyper-heuristic for the multidimensional knapsack problem |
| title_full_unstemmed | A genetic programming hyper-heuristic for the multidimensional knapsack problem |
| title_short | A genetic programming hyper-heuristic for the multidimensional knapsack problem |
| title_sort | genetic programming hyper-heuristic for the multidimensional knapsack problem |
| topic | Artificial intelligence genetic programming heuristic generation hyper-heuristics multidimensional knapsack problem |
| url | https://eprints.nottingham.ac.uk/32174/ https://eprints.nottingham.ac.uk/32174/ https://eprints.nottingham.ac.uk/32174/ |