A histogram-matching approach to the evolution of bin-packing strategies

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.