Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model

ABSTRACT

Novel deterministic heuristics are generated using Single Node Genetic Programming for application to the One Dimensional Bin Packing Problem. First a single deterministic heuristic was evolved that minimised the total number of bins used when applied to a set of 685 training instances. Following this, a set of heuristics were evolved using a form of cooperative co-evolution that collectively minimise the number of bins used across the same set of problems. Results on an unseen test set comprising a further 685 problem instances show that the single evolved heuristic outperforms existing deterministic heuristics described in the literature. The collection of heuristics evolved by cooperative co-evolution outperforms any of the single heuristics, including the newly generated ones.

References

1. E. Burke, M. Hyde, and G. Kendall. Evolving bin packing heuristics with genetic programming. In Parallel Problem Solving from Nature - PPSN IX, volume 4193 of Lecture Notes in Computer Science, pages 860--869. Springer Berlin / Heidelberg, 2006.
2. E. Burke, G. Kendall, J. Newall, E. Hart, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern search technology. In Handbook of Metaheuristics, International Series in Operations Research & Management Science, chapter 16, pages 457--474. Kluwer, 2003.
3. E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu. Hyper-heuristics: A survey of the state of the art. School of Computer Science and Information Technology, University of Nottingham, Computer Science Technical Report No. NOTTCS-TR-SUB-0906241418--2747., 2010.
4. E. K. Burke, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and J. R. Woodward. A classification of hyper-heuristic approaches. In M. Gendreau and J.-Y. Potvin, editors, Handbook of Metaheuristics, volume 146 of International Series in Operations Research & Management Science, pages 449--468. Springer US, 2010.
5. E. K. Burke, M. R. Hyde, G. Kendall, and J. Woodward. Automating the packing heuristic design process with genetic programming. Evol. Comput., 20(1):63--89, Mar. 2012.
6. P. I. Cowling, G. Kendall, and E. Soubeiga. A hyperheuristic approach to scheduling a sales summit. In Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III, PATAT '00, pages 176--190. Springer-Verlag, London, UK, 2000.
7. J. Csirik, D. S. Johnson, C. Kenyon, J. B. Orlin, P. W. Shor, and R. R. Weber. On the sum-of-squares algorithm for bin packing. J. ACM, 53(1):1--65, Jan. 2006.
8. J. Csirik, D. S. Johnson, C. Kenyon, P. W. Shor, and R. R. Weber. A self organizing bin packing heuristic. In Selected papers from the International Workshop on Algorithm Engineering and Experimentation, ALENEX '99, pages 246--265, London, UK, UK, 1999. Springer-Verlag.
9. J. Denzinger and M. Fuchs. High performance atp systems by combining several ai methods. In Proceedings Fifteenth International Joint Conference on Artificial Intelligence (IJCAI 97), pages 102--107. Morgan Kaufmann, 1997.
10. P. A. Djang and P. R. Finch. Solving one dimensional bin packing problems, 1998.
11. E. Falkenauer. A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2:5--30, 1996.
12. H. Fisher and G. L. Thompson. Probabilistic learning combinations of local job-shop scheduling rules. In J. Muth and G. L. Thompson, editors, Industrial Scheduling, pages 225--251. Prentice Hall, Englewood Cliffs, New Jersey, 1963.
13. M. R. Garey and D. S. Johnson. Computers and intractability : a guide to the theory of NP-completeness. A Series of books in the mathematical sciences. W.H. Freeman, San Francisco, 1979.
14. I. P. Gent. Heuristic solution of open bin packing problems. Journal of Heuristics, 3(4):299--304, 1998.
15. D. Jackson. A new, node-focused model for genetic programming. In A. Moraglio, S. Silva, K. Krawiec, P. Machado, and C. Cotta, editors, Genetic Programming, volume 7244 of Lecture Notes in Computer Science, pages 49--60. Springer Berlin Heidelberg, 2012.
16. D. Jackson. Single node genetic programming on problems with side effects. In C. Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, and M. Pavone, editors, Parallel Problem Solving from Nature - PPSN XII, volume 7491 of Lecture Notes in Computer Science, pages 327--336. Springer Berlin Heidelberg, 2012.
17. J. R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992.
18. J. Levine and F. Ducatelle. Ant colony optimization and local search for bin packing and cutting stock problems. The Journal of the Operational Research Society, 55(7):705--716, 2004.
19. M. A. Potter and K. A. De Jong. Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evol. Comput., 8:1--29, 2000.
20. P. Ross, J. Marín-Blázquez, S. Schulenburg, and E. Hart. Learning a procedure that can solve hard bin-packing problems: A new ga-based approach to hyper-heuristics. In E. Cantú-Paz, J. Foster, K. Deb, L. Davis, R. Roy, U.-M. O'Reilly, H.-G. Beyer, R. Standish, G. Kendall, S. Wilson, M. Harman, J. Wegener, D. Dasgupta, M. Potter, A. Schultz, K. Dowsland, N. Jonoska, and J. Miller, editors, Genetic and Evolutionary Computation GECCO 2003, volume 2724 of Lecture Notes in Computer Science, pages 215--215. Springer Berlin / Heidelberg, 2003.
21. P. Ross, S. Schulenburg, J. G. Marín-Blázquez, and E. Hart. Hyper-heuristics: Learning to combine simple heuristics in bin-packing problems. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '02, pages 942--948, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.
22. A. Scholl, R. Klein, and C. Jürgens. Bison: a fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res., 24(7):627--645, 1997.
23. P. Schwerin and G. Wäscher. The bin-packing problem: A problem generator and some numerical experiments with ffd packing and mtp. International Transactions in Operational Research, 4(5--6):377--389, 1997.
24. K. Sim, E. Hart, and B. Paechter. A hyper-heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution. In C. Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, and M. Pavone, editors, Parallel Problem Solving from Nature - PPSN XII, volume 7492 of Lecture Notes in Computer Science, pages 348--357. Springer Berlin Heidelberg, 2012.

Index Terms

• Computing methodologies

  • Machine learning