Evolving reusable 3d packing heuristics with genetic programming

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.

REFERENCES

• 1: S. Allen, E. K. Burke, and G. Kendall. A new hybrid placement strategy for the three-dimensional strip packing problem. Technical report, University of Nottingham, Dept of Computer Science, 2009.
• 2: E. Bischoff and M. Ratcliff. Issues in the development of approaches to container loading. Omega, 23(4):377--390, 1995.
• 3: A. Bortfeldt and H. Gehring. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 131(1):143--161, 2001.
• 4: E. K. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In F. Glover and G. Kochenberger, editors, Handbook of Meta-Heuristics, pages 457--474. Kluwer, Boston, Massachusetts, 2003.
• 5: E. K. Burke, M. R. Hyde, and G. Kendall. Evolving bin packing heuristics with genetic programming. In LNCS 4193, Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN 2006), pages 860--869, 2006.
• 6: Edmund K. Burke , Matthew R. Hyde , Graham Kendall , John Woodward, Automatic heuristic generation with genetic programming: evolving a jack-of-all-trades or a master of one, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277273]
• 7: E. K. Burke, M. R. Hyde, G. Kendall, and J. Woodward. The scalability of evolved on line bin packing heuristics. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 2530--2537, 2007.
• 8: E. K. Burke , G. Kendall , E. Soubeiga, A Tabu-Search Hyperheuristic for Timetabling and Rostering, Journal of Heuristics, v.9 n.6, p.451-470, December 2003 [doi>10.1023/B:HEUR.0000012446.94732.b6]
• 9: Edmund K. Burke , Sanja Petrovic , Rong Qu, Case-based heuristic selection for timetabling problems, Journal of Scheduling, v.9 n.2, p.115-132, April 2006 [doi>10.1007/s10951-006-6775-y]
• 10: C. K. Chua, V. Narayanan, and J. Loh. Constraint-based spatial representation technique for the container packing problem. Integrated Manufacturing Systems, 9(1):23--33, 1998.
• 11: K. Dowsland, E. Soubeiga, and E. K. Burke. A simulated annealing hyper-heuristic for determining shipper sizes. European Journal of Operational Research, 179(3):759--774, 2007.
• 12: Jens Egeblad , David Pisinger, Heuristic approaches for the two- and three-dimensional knapsack packing problem, Computers and Operations Research, v.36 n.4, p.1026-1049, April, 2009 [doi>10.1016/j.cor.2007.12.004]
• 13: M. Eley. Solving container loading problems by block arrangement. European Journal of Operational Research, 141(2):393--409, 2002.
• 14: Alex Fukunaga, Automated discovery of composite SAT variable-selection heuristics, Eighteenth national conference on Artificial intelligence, p.641-648, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 15: A. S. Fukunaga. Evolving local search heuristics for SAT using genetic programming. In LNCS 3103. Proceedings of the ACM Genetic and Evolutionary Computation Conference (GECCO '04), pages 483--494, Seattle, WA, USA, 2004. Springer-Verlag.
• 16: Alex S. Fukunaga, Automated discovery of local search heuristics for satisfiability testing, Evolutionary Computation, v.16 n.1, p.31-61, Spring 2008 [doi>10.1162/evco.2008.16.1.31]
• 17: Christopher D. Geiger , Reha Uzsoy , Haldun Aytug, Rapid Modeling and Discovery of Priority Dispatching Rules: An Autonomous Learning Approach, Journal of Scheduling, v.9 n.1, p.7-34, February 2006 [doi>10.1007/s10951-006-5591-8]
• 18: Wenqi Huang , Kun He, A new heuristic algorithm for cuboids packing with no orientation constraints, Computers and Operations Research, v.36 n.2, p.425-432, February, 2009 [doi>10.1016/j.cor.2007.09.008]
• 19: N. Ivancic, K. Mathur, and B. Mohanty. An integer-programming based heuristic approach to the three-dimensional packing problem. Journal of Manufacturing and Operations Management, 2:268--298, 1989.
• 20: R. E. Keller and R. Poli. Linear genetic programming of parsimonious metaheuristics. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 4508--4515, Singapore, September 2007.
• 21: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 22: A. Lim, B. Rodrigues, and Y. Wang. A multi-faced buildup algorithm for three-dimensional packing problems. OMEGA International Journal of Management Science, 31(6):471--481, 2003.
• 23: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Vlsi module placement based on rectangle-packing by the sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15(12):1518--1524, 1996.
• 24: B. K. A. Ngoi, M. L. Tay, and E. S. Chua. Applying spatial representation techniques to the container packing problem. International Journal of Production Research, 32(1):111--123, 1994.
• 25: D. Pisinger and J. Egeblad. Heuristic approaches for the two and three dimensional knapsack packing problems. Technical report, No.06-13. University of Copenhagen, Dept of Computer Science, 2006.
• 26: R. Poli. A simple but theoretically-motivated method to control bloat in genetic programming. In Genetic Programming, Proceedings of the 6th European Conference, EuroGP 2003, pages 211--223, Essex, April 2003. Springer-Verlag.
• 27: P. Ross. Hyper-heuristics. In E. K. Burke and G. Kendall, editors, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, pages 529--556. Kluwer, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Design, Performance, Reliability

Keywords:
gp, heuristics, hyper-heuristics, knapsack packing