A GA-based method to produce generalized hyper-heuristics for the 2D-regular cutting stock 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 a GA-based method that produces general hyper-heuristics that solve two-dimensional cutting stock problems. The GA uses a variable-length representation, which evolves combinations of condition-action rules producing hyper-heuristics after going through a learning process which includes training and testing phases. Such hyper-heuristics, when tested with a large set of benchmark problems, produce outstanding results (optimal and near-optimal) for most of the cases. The testbed is composed of problems used in other similar studies in the literature. Some additional instances of the testbed were randomly generated.

REFERENCES

• 1: 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
• 2: J. E. Beasley. Beasley operations research library. Collection of problems for 2D packing and cutting, 2003.
• 3: J. O. Berkey and P. Y. Wang. Two-dimensional finite bin packing algorithms. Journal of Operational Research Society, 38:423--429, 1987.
• 4: 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.
• 5: 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.
• 6: H. Dyckhoff. A topology of cuting and packing problems. European Journal of Operation Research, 44:145--159, 1990.
• 7: Lawrence J. Fogel, Intelligence through simulated evolution: forty years of evolutionary programming, John Wiley & Sons, Inc., New York, NY, 1999
• 8: 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
• 9: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 10: D. Goldberg, B. Korb, and K. Deb. Messy genetic algorithms: Motivation, analysis and first results. Complex Systems, pages 93--130, 1989.
• 11: B. L. Golden. Approaches to the cutting stock problem. AIIE Transactions, 8:256--274, 1976.
• 12: A. I. Hinxman. The trim-loss and assortment problems: A survey. EJOR, 5:8--18, 1980.
• 13: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 14: 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.
• 15: S. Jakobs. On genetic algorithms for the packing of polygons. European Journal of Operations Research, 88:165--181, 1966.
• 16: L. V. Kantorovich. Mathematical methods of organizing and planning production. Management Science, 6:366--422, 1960.
• 17: 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.
• 18: S. Martello and D. Vigo. Exact solution of the two-dimensional finite bin packing problem. Dipartimento di Elettronica, Informatica e Sistematica, 1998.
• 19: I. Rechenberg. Evolutionstrategie: Optimierung technischer systeme nach prinzipien dier biolischen evolution. Frommann-Holzboog, Stuttgart, 1973.
• 20: P. Ross, J. M. 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. Proceedings of GECCO 2003, pages 1295--1306, 2003.
• 21: 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
• 22: Hans-Paul Schwefel, Numerical Optimization of Computer Models, John Wiley & Sons, Inc., New York, NY, 1981
• 23: 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]
• 24: H. Terashima-Marín, A. Morán-Saavedra, and P. Ross. Forming hyper-heuristics with GA s when solving 2D-regular cutting stock problems. Proceedings of the Congress on Evolutionary Computation, pages 1104--1110, 2005.
• 25: R. A. Wilson and F. C. Keil. The MIT Encyclopedia of the Cognitive Science. MIT Press, Cambridge, Massachussets, 1999.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
cutting stock, evolutionary computation, hyper-heuristics, optimization