Hyper-heuristics and classifier systems for solving 2D-regular cutting stock problems

ABSTRACT

This paper presents a method for combining concepts of Hyper-heuristics and Learning Classifier Systems for solving 2D Cutting Stock Problems. 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. In this paper, the Hyper-heuristic is formed using a XCS-type Learning Classifier System which learns a solution procedure when solving individual problems. The XCS evolves a behavior model which determines the possible actions (selection and placement heuristics) for given states of the problem. When tested with a collection of different problems, the method finds very competitive results for most of the cases. The testebed 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: Larry Bull, Applications of Learning Classifier Systems, SpringerVerlag, 2004
• 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: L. Davis. Handbook of Genetic Algorithms. Van Nostrtand Reinhold, New York, 1991.
• 7: H. Dyckhoff. A topology of cuting and packing problems. European Journal of Operation Research, 44:145--159, 1990.
• 8: Agoston E. Eiben , J. E. Smith, Introduction to Evolutionary Computing, SpringerVerlag, 2003
• 9: Lawrence J. Fogel, Intelligence through simulated evolution: forty years of evolutionary programming, John Wiley & Sons, Inc., New York, NY, 1999
• 10: 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
• 11: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 12: B. L. Golden. Approaches to the cutting stock problem. AIIE Transactions, 8:256--274, 1976.
• 13: A. I. Hinxman. The trim-loss and assortment problems: A survey. EJOR, 5:8--18, 1980.
• 14: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 15: 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.
• 16: S. Jakobs. On genetic algorithms for the packing of polygons. European Journal of Operations Research, 88:165--181, 1966.
• 17: L. V. Kantorovich. Mathematical methods of organizing and planning production. Management Science, 6:366--422, 1960.
• 18: 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.
• 19: S. Martello and D. Vigo. Exact solution of the two-dimensional finite bin packing problem. Dipartimento di Elettronica, Informatica e Sistematica, 1998.
• 20: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 21: I. Rechenberg. Evolutionstrategie: Optimierung technischer systeme nach prinzipien dier biolischen evolution. Frommann-Holzboog, Stuttgart, 1973.
• 22: 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
• 23: Hans-Paul Schwefel, Numerical Optimization of Computer Models, John Wiley & Sons, Inc., New York, NY, 1981
• 24: R. A. Wilson and F. C. Keil. The MIT Encyclopedia of the Cognitive Science. MIT Press, Cambridge, Massachussets, 1999.
• 25: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, pages 149--175, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms

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