The Scalability of Evolved on Line Bin Packing Heuristics

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

@InProceedings{Burke:2007:cec,
  author =       "E. K. Burke and M. R. Hyde and G. Kendall and 
                 J. R. Woodward",
  title =        "The Scalability of Evolved on Line Bin Packing
                 Heuristics",
  booktitle =    "2007 IEEE Congress on Evolutionary Computation",
  year =         "2007",
  editor =       "Dipti Srinivasan and Lipo Wang",
  pages =        "2530--2537",
  address =      "Singapore",
  month =        "25-28 " # sep,
  organization = "IEEE Computational Intelligence Society",
  publisher =    "IEEE Press",
  ISBN =         "1-4244-1340-0",
  file =         "1668.pdf",
  keywords =     "genetic algorithms, genetic programming",
  DOI =          "doi:10.1109/CEC.2007.4424789",
  size =         "8 pages",
  abstract =     "The on line bin packing problem concerns the packing
                 of pieces into the least number of bins possible, as
                 the pieces arrive in a sequential fashion. In previous
                 work, we used genetic programming to evolve heuristics
                 for this problem, which beat the human designed
                 'bestfit' algorithm. Here we examine the performance of
                 the evolved heuristics on larger instances of the
                 problem, which contain many more pieces than the
                 problem instances used in training. In previous work,
                 we concluded that we could confidently apply our
                 heuristics to new instances of the same class of
                 problem. Now we can make the additional claim that we
                 can confidently apply our heuristics to problems of
                 much larger size, not only without deterioration of
                 solution quality, but also within a constant factor of
                 the performance obtained by 'best fit'.

                 Interestingly, our evolved heuristics respond to the
                 number of pieces in a problem instance although they
                 have no explicit access to that information. We also
                 comment on the important point that, when solutions are
                 explicitly constructed for single problem instances,
                 the size of the search space explodes. How- ever, when
                 working in the space of algorithmic heuristics, the
                 distribution of functions represented in the search
                 space reaches some limiting distribution and therefore
                 the combinatorial explosion can be controlled.",
  notes =        "Feb 2013 IEEE Xplore meta data gives wrong author.

                 CEC 2007 - A joint meeting of the IEEE, the EPS, and
                 the IET.

                 IEEE Catalog Number: 07TH8963C",
}

Genetic Programming entries for Edmund Burke Matthew R Hyde Graham Kendall John R Woodward

Citations