A genetic programming hyper-heuristic for the multidimensional knapsack problem

Created by W.Langdon from gp-bibliography.bib Revision:1.3963

@Article{Drake:2014:Kybernetes,
  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://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.",
}

Genetic Programming entries for John H Drake Matthew R Hyde Khaled Ibrahim Ender Ozcan

Citations