Incorporating Inference into Evolutionary Algorithms for Max-CSP

  • Madalina Ionita
  • Cornelius Croitoru
  • Mihaela Breaban
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4030)


This paper presents a simple way of combining inference with stochastic search for solving constraint satisfaction problems. The approach makes use of an evolutionary algorithm for search assisted by an inference algorithm, the variable elimination procedure. The hybrid algorithm obtained is adapted in such way that a balance between exploitation and exploration is preserved. The results are presented for the Max-CSP optimization task.


Genetic Algorithm Evolutionary Algorithm Constraint Satisfaction Constraint Satisfaction Problem Inference Algorithm 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Dechter, R.: Constraint Processing. Morgan Kaufmann Publishers, San Francisco (2003)Google Scholar
  2. 2.
    Michalewicz, Z.: A survey of constraint handling techniques in evolutionary computation methods. In: Proceedings of the 4th Anual Conference on Evolutionary Programming, pp. 135–155 (1995)Google Scholar
  3. 3.
    Dozier, G., Bowen, J., Bahler, D.: Solving small and large constraint satisfaction problems using a heuristic-based microgenetic algorithm. In: Proceedings of the 1st IEEE Conference on Evolutionary Computation, pp. 306–311 (1994)Google Scholar
  4. 4.
    Paredis, J.: Coevolutionary constraint satisfaction. In: Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, vol. 866, pp. 46–55 (1994)Google Scholar
  5. 5.
    Eiben, A.E., Ruttkay, Z.: Self-adaptivity for constraint satisfaction: Learning penalty functions. In: Proceedings of the 3rd IEEE Conference on Evolutionary Computation, pp. 258–261 (1996)Google Scholar
  6. 6.
    Craenen, B.G.W., Eiben, A.E., van Hemert, J.I.: Comparing Evolutionary Algorithms on Binary Constraint Satisfaction Problems. IEEE Transactions on Evolutionary Computation 7(5), 424–444 (2003)CrossRefGoogle Scholar
  7. 7.
    Eiben, A.E., Raue, P.-E., Ruttkay, Z.: Solving constraint satisfaction problems using genetic algorithms. In: Proceedings of the 1st IEEE Conference on Evolutionary Computation, pp. 542–547 (1994)Google Scholar
  8. 8.
    Marchiori, E., Steenbeek, A.: A Genetic Local Search Algorithm for Random Binary Constraint Satisfaction Problems. In: Proceedings of the 14th Annual Symposium on Applied Computing, pp. 458–462 (2000)Google Scholar
  9. 9.
    Kask, K., Dechter, R.: New Search Heuristics for Max-CSP. Principles and Practice of Constraint Programming, 262-277 (2000)Google Scholar
  10. 10.
    Dechter, R.: Bucket elimination: A unifying framework for reasoning. Artificial Intelligence 113, 41–85 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    Dechter, R., Rish, I.: Mini-buckets: A general scheme for bounded inference. Journal of the ACM 50(2), 107–153 (2003)CrossRefMathSciNetGoogle Scholar
  12. 12.
    Michalewicz, Z.: Genetic Algorithms + Data structures = Evolution programs, 3rd edn. Springer, Berlin (1996)zbMATHGoogle Scholar
  13. 13.
    Hinterding, R., Michalewicz, Z., Eiben, A.E.: Adaptation in evolutionary computation: a survey. In: Proceedings of the 4th IEEE Conference on Evolutionary Computation, pp. 65–69 (1997)Google Scholar
  14. 14.
    Morris, P.: The breakout method for escaping from local minima. Proceedings of the 11th National Conference on Artificial In- telligence, AAAI (1993) 40-45Google Scholar
  15. 15.
    Smith, B.: Phase transition and the mushy region in constraint satisfaction. In: Proceedings of the 11th ECAI, pp. 100–104 (1994)Google Scholar
  16. 16.
    Larossa, J., Meseguer, P.: Partial Lazy Forward Checking for MAX-CSP. In: Proceedings of the 13th European Conference on Artificial Intelligence, pp. 229–233 (1998)Google Scholar
  17. 17.
    Achlioptas, D., Kirousis, L.M., Kranakis, E., Krizanc, D., Molloy, M.S.O., Stamatiou, Y.C.: Random constraint satisfaction: A more accurate picture. Constraints 4(6), 329–344 (2001)CrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Madalina Ionita
    • 1
  • Cornelius Croitoru
    • 1
  • Mihaela Breaban
    • 1
  1. 1.“Al.I.Cuza” University of IasiRomania

Personalised recommendations