Evolving Bin Packing Heuristics with Genetic Programming

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

  author =       "E. K. Burke and M. R. Hyde and G. Kendall",
  title =        "Evolving Bin Packing Heuristics with Genetic
  booktitle =    "Parallel Problem Solving from Nature - PPSN IX",
  year =         "2006",
  editor =       "Thomas Philip Runarsson and Hans-Georg Beyer and 
                 Edmund Burke and Juan J. Merelo-Guervos and 
                 L. Darrell Whitley and Xin Yao",
  volume =       "4193",
  pages =        "860--869",
  series =       "LNCS",
  address =      "Reykjavik, Iceland",
  publisher_address = "Berlin",
  month =        "9-13 " # sep,
  publisher =    "Springer-Verlag",
  ISBN =         "3-540-38990-3",
  keywords =     "genetic algorithms, genetic programming",
  URL =          "http://www.cs.nott.ac.uk/~mvh/ppsn2006.pdf",
  DOI =          "doi:10.1007/11844297_87",
  size =         "10 pages",
  abstract =     "The bin-packing problem is a well known NP-Hard
                 optimisation problem, and, over the years, many
                 heuristics have been developed to generate good quality
                 solutions. This paper outlines a genetic programming
                 system which evolves a heuristic that decides whether
                 to put a piece in a bin when presented with the sum of
                 the pieces already in the bin and the size of the piece
                 that is about to be packed. This heuristic operates in
                 a fixed framework that iterates through the open bins,
                 applying the heuristic to each one, before deciding
                 which bin to use. The best evolved programs emulate the
                 functionality of the human designed first-fit
                 heuristic. Thus, the contribution of this paper is to
                 demonstrate that genetic programming can be employed to
                 automatically evolve bin packing heuristics which are
                 the same as high quality heuristics which have been
                 designed by humans.",
  notes =        "PPSN-IX",

Genetic Programming entries for Edmund Burke Matthew R Hyde Graham Kendall