A neuro-evolutionary approach to produce general hyper-heuristics for the dynamic variable ordering in hard binary constraint satisfaction problems

ABSTRACT

This paper introduces a neuro-evolutionary approach to produce hyper-heuristics for the dynamic variable ordering for hard binary constraint satisfaction problems. The model uses a GA to evolve a population of neural networks architectures and parameters. For every cycle in the GA process, the new networks are trained using backpropagation. When the process is over, the best trained individual in the last population of neural networks represents the general hyper-heuristic.

REFERENCES

• 1: 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]
• 2: 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.
• 3: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 4: H. Terashima-Marín , J. C. Ortiz-Bayliss , P. Ross , M. Valenzuela-Rendón, Hyper-heuristics for the dynamic variable ordering in constraint satisfaction problems, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389206]

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, hyper-heuristics, neuro-evolutionary computation, optimization