- 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",
