A Histogram-Matching Approach to the Evolution of
Bin-Packing Strategies
R. Poli, J. Woodward, und E. Burke. 2007 IEEE Congress on Evolutionary Computation, Seite 3500--3507. Singapore, IEEE Computational Intelligence Society, IEEE Press, (25-28 September 2007)
Zusammenfassung
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.
%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
}