Hyper-heuristics for the dynamic variable ordering in constraint satisfaction problems

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 for the dynamic variable ordering within Constraint Satisfaction 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 encouraging results for most of the cases. The testebed is composed of problems randomly generated using an algorithm proposed by Prosser.

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: Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
• 3: 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.
• 4: B. G. W. Craenen, A. E. Eiben and J. I. van Hemert. Comparing evolutionary algorithms on binary constraint satisfaction problems. Evolutionary Computation, IEEE Transactions on, 7(5):424--444, 2003.
• 5: Rina Dechter , Itay Meiri, Experimental evaluation of preprocessing algorithms for constraint satisfaction problems, Artificial Intelligence, v.68 n.2, p.211-241, Aug. 1994 [doi>10.1016/0004-3702(94)90068-X]
• 6: Lawrence J. Fogel, Intelligence through simulated evolution: forty years of evolutionary programming, John Wiley & Sons, Inc., New York, NY, 1999
• 7: 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
• 8: I.P. Gent, E. MacIntyre, P. Prosser, B.M. Smith, and T. Walsh. An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem. In Proceedings of CP-96, pages 179--193, 1996.
• 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 pp. 93--130, 1989.
• 11: B. L. Golden. Approaches to the cutting stock problem. AIIE Transactions, 8:256--274, 1976.
• 12: R. M. Haralick and G. L. Elliott. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14:263--313, 1980.
• 13: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 14: Elena Marchiori , Adri Steenbeek, A genetic local search algorithm for random binary constraint satisfaction problems, Proceedings of the 2000 ACM symposium on Applied computing, p.458-462, March 2000, Como, Italy [doi>10.1145/335603.335910]
• 15: Steven Minton , Mark D. Johnston , Andrew B. Philips , Philip Laird, Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence, v.58 n.1-3, p.161-205, Dec. 1992 [doi>10.1016/0004-3702(92)90007-K]
• 16: S. Minton, A. Phillips, and P. Laird. Solving large-scale csp and scheduling problems using a heuristic repair method. In Proceedings of the 8th AAAI Conference, pages 17--24, 1990.
• 17: P. Prosser. Binary constraint satisfaction problems: Some are harder than others. In Proceedings of the European Conference in Artificial Intelligence, pages 95--99, Amsterdam, Holland, 1994.
• 18: I. Rechenberg. Evolutionstrategie: Optimierung technischer systeme nach prinzipien dier biolischen evolution. Frommann-Holzboog, Stuttgart, 1973.
• 19: 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.
• 20: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 21: Hans-Paul Schwefel, Numerical Optimization of Computer Models, John Wiley & Sons, Inc., New York, NY, 1981
• 22: H. Terashima-Marín, R. Calleja-Manzanedo and M. Valenzuela-Rendón. Genetic Algorithms for Dynamic Variable Ordering in Constraint Satisfaction Problems. Advances in Artificial Intelligence Theory, 16: pages 35--44, 2005.
• 23: 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]
• 24: 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
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
constraint satisfaction problems, dynamic variable ordering, evolutionary computation, hyper-heuristics