A genetic programming hyper-heuristic approach to automated packing

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

@PhdThesis{Hyde:thesis,
  author =       "Matthew Hyde",
  title =        "A genetic programming hyper-heuristic approach to
                 automated packing",
  school =       "School of Computer Science, University of Nottingham",
  year =         "2010",
  address =      "UK",
  month =        mar,
  keywords =     "genetic algorithms, genetic programming, Electronic
                 computers. Computer science",
  URL =          "http://etheses.nottingham.ac.uk/1625/1/mvh_corrected_thesis.pdf",
  URL =          "http://etheses.nottingham.ac.uk/1625/",
  URL =          "http://ethos.bl.uk/OrderDetails.do?did=28&uin=uk.bl.ethos.523511",
  size =         "226 pages",
  bibsource =    "OAI-PMH server at etheses.nottingham.ac.uk",
  oai =          "oai:etheses.nottingham.ac.uk:1625",
  abstract =     "This thesis presents a programme of research which
                 investigated a genetic programming hyper-heuristic
                 methodology to automate the heuristic design process
                 for one, two and three dimensional packing
                 problems.

                 Traditionally, heuristic search methodologies operate
                 on a space of potential solutions to a problem. In
                 contrast, a hyper-heuristic is a heuristic which
                 searches a space of heuristics, rather than a solution
                 space directly. The majority of hyper-heuristic
                 research papers, so far, have involved selecting a
                 heuristic, or sequence of heuristics, from a set
                 predefined by the practitioner. Less well studied are
                 hyper-heuristics which can create new heuristics, from
                 a set of potential components.

                 This thesis presents a genetic programming
                 hyper-heuristic which makes it possible to
                 automatically generate heuristics for a wide variety of
                 packing problems. The genetic programming algorithm
                 creates heuristics by intelligently combining
                 components. The evolved heuristics are shown to be
                 highly competitive with human created heuristics. The
                 methodology is first applied to one dimensional bin
                 packing, where the evolved heuristics are analysed to
                 determine their quality, specialisation, robustness,
                 and scalability. Importantly, it is shown that these
                 heuristics are able to be reused on unseen problems.
                 The methodology is then applied to the two dimensional
                 packing problem to determine if automatic heuristic
                 generation is possible for this domain. The three
                 dimensional bin packing and knapsack problems are then
                 addressed. It is shown that the genetic programming
                 hyper-heuristic methodology can evolve human
                 competitive heuristics, for the one, two, and three
                 dimensional cases of both of these problems. No change
                 of parameters or code is required between runs. This
                 represents the first packing algorithm in the
                 literature able to claim human competitive results in
                 such a wide variety of packing domains.",
  notes =        "uk.bl.ethos.523511",
}

Genetic Programming entries for Matthew R Hyde

Citations