Conference Paper (published)
Details
Citation
Poli R, Woodward J & Burke E (2007) A histogram-matching approach to the evolution of bin-packing strategies. In: IEEE Congress on Evolutionary Computation, 2007. CEC 2007. A histogram-matching approach to the evolution of bin-packing strategies, Singapore, 25.09.2007-28.09.2007. Red Hook, NJ: IEEE, pp. 3500-3507. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4424926; https://doi.org/10.1109/CEC.2007.4424926
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.
| Status | Published |
|---|---|
| Publication date | 31/12/2007 |
| Publication date online | 30/09/2007 |
| Publisher | IEEE |
| Publisher URL | |
| Place of publication | Red Hook, NJ |
| ISBN | 978-1-4244-1339-3 |
| Conference | A histogram-matching approach to the evolution of bin-packing strategies |
| Conference location | Singapore |
| Dates | – |