Evolving reusable 3D packing heuristics with genetic programming

Citation

Allen SD, Burke E, Hyde M & Kendall G (2009) Evolving reusable 3D packing heuristics with genetic programming. In: Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference, GECCO-2009. GECCO 2009 Genetic and Evolutionary Computation Conference, Montreal, Canada, 08.07.2009-12.07.2009. New York, NY, USA: ACM, pp. 931-938. http://dl.acm.org/citation.cfm?doid=1569901.1570029; https://doi.org/10.1145/1569901.1570029

Abstract
This paper compares the quality of reusable heuristics designed by genetic programming (GP) to those designed by human programmers. The heuristics are designed for the three dimensional knapsack packing problem. Evolutionary computation has been employed many times to search for good quality solutions to such problems. However, actually designing heuristics with GP for this problem domain has never been investigated before. In contrast, the literature shows that it has taken years of experience by human analysts to design the very effective heuristic methods that currently exist. Hyper-heuristics search a space of heuristics, rather than directly searching a solution space. GP operates as a hyper-heuristic in this paper, because it searches the space of heuristics that can be constructed from a given set of components. We show that GP can design simple, yet effective, stand-alone constructive heuristics. While these heuristics do not represent the best in the literature, the fact that they are designed by evolutionary computation, and are human competitive, provides evidence that further improvements in this GP methodology could yield heuristics superior to those designed by humans.