Evolving bin packing heuristics with genetic programming

Citation

Burke E, Hyde M & Kendall G (2006) Evolving bin packing heuristics with genetic programming. In: Runarsson T, Beyer H, Burke E, Merelo-Guervos J, Whitley L & Yao X (eds.) Parallel Problem Solving from Nature - PPSN IX: 9th International Conference, Reykjavik, Iceland, September 9-13, 2006, Proceedings. Lecture Notes in Computer Science, 4193. 9th International Conference of Parallel Problem Solving from Nature - PPSN IX, Reykjavik, Iceland, 09.09.2006-13.09.2006. Berlin Heidelberg: Springer, pp. 860-869. http://link.springer.com/chapter/10.1007%2F11844297_87; https://doi.org/10.1007/11844297_87

Abstract
The bin-packing problem is a well known NP-Hard optimisation problem, and, over the years, many heuristics have been developed to generate good quality solutions. This paper outlines a genetic programming system which evolves a heuristic that decides whether to put a piece in a bin when presented with the sum of the pieces already in the bin and the size of the piece that is about to be packed. This heuristic operates in a fixed framework that iterates through the open bins, applying the heuristic to each one, before deciding which bin to use. The best evolved programs emulate the functionality of the human designed ‘first-fit' heuristic. Thus, the contribution of this paper is to demonstrate that genetic programming can be employed to automatically evolve bin packing heuristics which are the same as high quality heuristics which have been designed by humans.