A histogram-matching approach to the evolution of bin-packing strategies
Riccardo Poli, John Robert Woodward, Edmund K. Burke · 2007
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.