Comparing two models to generate hyper-heuristics for the 2d-regular bin-packing problem

ABSTRACT

The idea behind hyper-heuristics is to discover some combination of straightforward heuristics to solve a wide range of problems. To be worthwhile, such combination should outperform the single heuristics. This paper presents two Evolutionary-Computation-based Models to producehyper-heuristics that solve two-dimensional bin-packing problems. The first model uses an XCS-type Learning Classifier System which learns a solution procedure when solving individual problems. The second model is based on a GA that uses a variable-length representation, which evolves combinations of condition-action rules producing hyper-heuristics after going through alearning process which includes training and testing phases.Both approaches, when tested and compared using a large set ofbenchmark problems, perform better than the combinations ofsingle heuristics. The testbed is composed of problems used inother similar studies in the literature. Some additional instances of the testbed were randomly generated.

REFERENCES

• 1: H. Terashima-Marín Tecnológico de Monterrey, Monterrey, N. L., Mexico
• 2: C. J. Farias-Zárate Tecnológico de Monterrey, Monterrey, N. L. , Mexico
• 3: P. Ross Napier University, Edinburgh, United Kingdom
• 4: M. Valenzuela-Rendón Tecnolégico de Monterrey, Monterrey, N. L., Mexico
• 5: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 6: J. E. Beasley. Beasley operations research library. Collection of problems for 2D packing and cutting, 2003.
• 7: J. O. Berkey and PY. Wang. Two-dimensional finite bin packing algorithms. Journal of Operational Research Society, 38:423--429, 1987.
• 8: E. Burke, E. Hart, G. Kendall, J. Newall, P. Ross, and S. Schulenburg. Hyper-heuristics: An emerging direction in modern research technolology. In Handbook of Metaheuristics, pages 457--474. Kluwer Academic Publishers, 2003.
• 9: C. H. Cheng, B. R. Fiering, and T. C. Chang. The cutting stock problem. a survey. International Journal of Production Economics, 36:291--305, 1994.
• 10: H. Dyckhoff. A topology of cutting and packing problems. European Journal of Operation Research, 44:145--159, 1990.
• 11: D. B. Fogel, L. A. Owens, and M. Walsh. Artificial Intelligence through Simulated Evolution. Wiley, New York, 1966.
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 14: D. Goldberg, B. Korb, and K. Deb. Messy genetic algorithms: Motivation, analysis and first results. Complex Systems, pages pp. 93--130, 1989.
• 15: B. L. Golden. Approaches to the cutting stock problem. AIIE Transactions, 8:256--274, 1976.
• 16: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 17: E. Hopper and B. C. Turton. An empirical study of meta-heuristics applied to 2D rectangular bin packing. Studia Informatica Universalis, pages 77--106, 2001.
• 18: S. Jakobs. On genetic algorithms for the packing of polygons. European Journal of Operations Research, 88:165--181, 1966.
• 19: L. V. Kantorovich. Mathematical methods of organizing and planning production. Management Science, 6:366--422, 1960.
• 20: D. Liu and H. Teng. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangle. European Journal of Operations Research, 112:413--419, 1999.
• 21: S. Martello and D. Vigo. Exact solution of the two-dimensional finite bin packing problem. Dipartimento di Elettronica, Informatica e Sistematica, 1998.
• 22: I. Rechenberg. Evolutionstrategie: Optimierung technischer systeme nach prinzipien dier biolischen evolution. Frommann-Holzboog, Stuttgart, 1973.
• 23: Peter Ross , Sonia Schulenburg , Javier G. Marín-Blázquez , Emma Hart, Hyper-heuristics: Learning To Combine Simple Heuristics In Bin-packing Problems, Proceedings of the Genetic and Evolutionary Computation Conference, p.942-948, July 09-13, 2002
• 24: Hans-Paul Schwefel, Numerical Optimization of Computer Models, John Wiley & Sons, Inc., New York, NY, 1981
• 25: H. Terashima-Marín , C. J. Farías Zárate , P. Ross , M. Valenzuela-Rendón, A GA-based method to produce generalized hyper-heuristics for the 2D-regular cutting stock problem, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144102]
• 26: H. Terashima-Marín , E. J. Flores-Álvarez , P. Ross, Hyper-heuristics and classifier systems for solving 2D-regular cutting stock problems, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068115]
• 27: R. A. Wilson and F. C. Keil. The MIT Encyclopedia of the Cognitive Science. MIT Press, Cambridge, Massachussets, 1999.
• 28: S. W. Wilson. Generalization in the XCS classifier system. Evolutionary Computation}, 1998.
• 29: G. Wäscher, H. Haussner, and H. Schumann. An improved typology of cutting and packing problems. European Journal of Operation Research, 171, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
cutting and packing problems, evolutionary computation, hyper-heuristics, optimization