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. ]]E. K. Burke, M. R. Hyde, G. Kendall, and J. Woodward. Automatic heuristic generation with genetic programming: Evolving a jack-of-all-trades or a master of one. In Proceedings of the 9th ACM Genetic and Evolutionary Computation Conference (GECCO 2007), pages 1559--1565, 2007.
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, and E. Soubeiga. A tabu-search hyper-heuristic for timetabling and rostering. Journal of Heuristics, 9(6):451--470, 2003.
9. ]]E. K. Burke, S. Petrovic, and R. Qu. Case-based heuristic selection for timetabling problems. J. of Scheduling, 9(2):115--132, 2006.
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. ]]J. Egeblad and D. Pisinger. Heuristic approaches for the two- and three-dimensional knapsack packing problem. Computers and Operations Research, 36(4):1026--1049, 2009.
13. ]]M. Eley. Solving container loading problems by block arrangement. European Journal of Operational Research, 141(2):393--409, 2002.
14. ]]A. S. Fukunaga. Automated discovery of composite sat variable-selection heuristics. In Eighteenth national conference on Artificial intelligence, pages 641--648, Menlo Park, CA, USA, 2002.
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. ]]A. S. Fukunaga. Automated discovery of local search heuristics for satisfiability testing. Evolutionary Computation (MIT Press), 16(1):31-1, 2008.
17. ]]C. D. Geiger, R. Uzsoy, and H. Aytug. Rapid modeling and discovery of priority dispatching rules: An autonomous learning approach. Journal of Scheduling, 9(1):7--34, 2006.
18. ]]W. Huang and K. He. A new heuristic algorithm for cuboids packing with no orientation constraints. Computers and Operations Research, In Press, Corrected Proof, Available online 21 September 2007.
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. ]]J. R. Koza. Genetic programming: on the programming of computers by means of natural selection. The MIT Press, Boston, Massachusetts, 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.