%0 Conference Paper %1 Poli:2007:cec %A Poli, Riccardo %A Woodward, John %A Burke, Edmund K. %B 2007 IEEE Congress on Evolutionary Computation %C Singapore %D 2007 %E Srinivasan, Dipti %E Wang, Lipo %I IEEE Press %K algorithms, genetic programming %P 3500--3507 %T A Histogram-Matching Approach to the Evolution of Bin-Packing Strategies %X We present a novel algorithm for the one-dimension offline bin packing problem with discrete item sizes based on the notion of matching the item-size histogram with the bin-gap histogram. The approach is controlled by a constructive heuristic function which decides how to prioritise items in order to minimise the difference between histograms. We evolve such a function using a form of linear register-based genetic programming system. We test our evolved heuristics and compare them with hand-designed ones, including the well known best fit decreasing heuristic. The evolved heuristics are human-competitive, generally being able to outperform high performance human-designed heuristics. %@ 1-4244-1340-0

@inproceedings{Poli:2007:cec, abstract = {We present a novel algorithm for the one-dimension offline bin packing problem with discrete item sizes based on the notion of matching the item-size histogram with the bin-gap histogram. The approach is controlled by a constructive heuristic function which decides how to prioritise items in order to minimise the difference between histograms. We evolve such a function using a form of linear register-based genetic programming system. We test our evolved heuristics and compare them with hand-designed ones, including the well known best fit decreasing heuristic. The evolved heuristics are human-competitive, generally being able to outperform high performance human-designed heuristics.}, added-at = {2008-06-19T17:35:00.000+0200}, address = {Singapore}, author = {Poli, Riccardo and Woodward, John and Burke, Edmund K.}, biburl = {https://www.bibsonomy.org/bibtex/238ce56c24b3bd65f28b2c87e5ef2ef27/brazovayeye}, booktitle = {2007 IEEE Congress on Evolutionary Computation}, editor = {Srinivasan, Dipti and Wang, Lipo}, file = {1597.pdf}, interhash = {be7f7d2992982bf7e7f0800385cda8a1}, intrahash = {38ce56c24b3bd65f28b2c87e5ef2ef27}, isbn = {1-4244-1340-0}, keywords = {algorithms, genetic programming}, month = {25-28 September}, notes = {CEC 2007 - A joint meeting of the IEEE, the EPS, and the IET. IEEE Catalog Number: 07TH8963C}, organization = {IEEE Computational Intelligence Society}, pages = {3500--3507}, publisher = {IEEE Press}, timestamp = {2008-06-19T17:49:49.000+0200}, title = {A Histogram-Matching Approach to the Evolution of Bin-Packing Strategies}, year = 2007 }