GA-easy and GA-hard constraint satisfaction problems

In this paper we discuss the possibilities of applying genetic algorithms (GA) for solving constraint satisfaction problems (CSP). We point out how the greediness of deterministic classical CSP solving techniques can be counterbalanced by the random mechanisms of GAs. We tested our ideas by running experiments on four different CSPs: N-queens, graph 3-colouring, the traffic lights and the Zebra problem. Three of the problems have proven to be GA-easy, and even for the GA-hard one the performance of the GA could be boosted by techniques familiar in classical methods. Thus GAs are promising tools for solving CSPs. In the discussion, we address the issues of non-solvable CSPs and the generation of all the solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Preview

Similar content being viewed by others

Combinatorial Designs on Constraint Satisfaction Problem (VRP)

Chapter © 2020

Parameterized Complexity of Conflict-Free Matchings and Paths

Article 10 February 2020

Exact solutions to generalized vertex covering problems: a comparison of two models

Article 14 February 2015

References

  1. Adorf, H. M. and Johnston, M. D., A discrete stochastic neural network algorithm for constraint satisfaction problems, In Proc. of the International Joint Conference on Neural Networks, San Diego, CA 1990. Google Scholar
  2. Back, T., Khuri, A., An evolutionary heuristic for the maximum independent set problem, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 531–535. Google Scholar
  3. Brassard, G. and Bratley, P., Algorithmics — Theory and Practice, Prentice Hall, Englewood Cliffs, NJ, 1988. Google Scholar
  4. Cheeseman, P., Kenefsky, B. and Taylor, W. M., Where the really hard problems are, In Proc. of IJCAI-91, 1991, pp 331–337. Google Scholar
  5. Corcoran, A. L. and Wainwright, R. L., LibGA: A User Friendly Workbench for Order-Based Genetic Algorithm Research, In Proc. of Applied Computing: Sates of the Art and Practice-1993, 1993, pp 111–117. Google Scholar
  6. Crawford, K.D., Solving the n-queens problem using genetic algorithms, In Proc. ACM/SIGAPP Symposium on Applied Computing, Kansas City, Missouri, 1992, pp 1039–1047. Google Scholar
  7. Davenport, A., Tsang, E., Wang, C. J. and Zhu, K., GENET: A connnectionist architecture for solving constraint satisfaction problems by iterative improvement, In Proc. of AAAI'94. Google Scholar
  8. Davis, L., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991. Google Scholar
  9. Dechter, R., Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition, Artificial Intelligence 41 1990, pp 273–312. Google Scholar
  10. Dozier, G., Bowen, J., Bahler, D., Solving small and large scale constraint satisfaction problems using a heuristic-based microgenetic agorithm, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 306–311. Google Scholar
  11. Dozier, G., Bowen, J., Bahler, D., Constraint processing using heuristic microgenetic algorithms, In Proc. of the ECAI'94 Workshop on Applied Genetic and Other Evolutionary Algorithms, Amsterdam, 1994. Google Scholar
  12. Eiben, A. E., Raué, P-E. and Ruttkay, Zs., Heuristic Genetic Algorithms for Constrained Problems, Part I: Principles, Technical Report IR-337, Dep. of Maths. and Comp. Sci., Free University Amsterdam, 1993. Google Scholar
  13. Eiben, A. E., Raué, P-E. and Ruttkay, Zs., Solving constraint satisfaction problems using genetic algorithms, In Proc. of the IEEE World Conf. on Comp. Intelligence, Orlando, 1994, pp 542–547. Google Scholar
  14. Eiben, A. E., Raué, P-E. and Ruttkay, Zs., Genetic algorithms with multi-parent reproduction, To appear in Proc. of the 3rd Parallel Problem Solving from Nature, LNCS Series, Springer-Verlag, 1994. Google Scholar
  15. Eiben, A. E., Raué, P-E. and Ruttkay, Zs., Repairing, adding constraints and learning as a means of improving GA performance on CSPs, In Proc. of the BENELEARN-94, Rotterdam, 1994. Google Scholar
  16. Forrest, S. and Mitchell, M., What makes a problem hard for a GA?, to appear in Machine Learning 1994. Google Scholar
  17. Fox, B. R. and McMahon, M.B., Genetic operators for sequencing problems, In Proc. of Foundations of Genetic Algorithms-90, Morgan Kaufman, 1991, pp 284–300. Google Scholar
  18. Freuder, E. C., A sufficient condition for backtrack-free search, Journal of the ACM 29, 1 1982. pp 24–32. Google Scholar
  19. Freuder, E. C., A sufficient condition for backtrack-bounded search, Journal of the ACM 32, 4 1985. pp 775–761. Google Scholar
  20. Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989. Google Scholar
  21. Hao, J., Dorne, R., A new population-based method for satisfiability problems, In Proc. of ECAI'94, Amsterdam 1994, pp 135–139. Google Scholar
  22. Haralick, R. M., and Elliot, G. L., Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence 14 1980, pp 263–313. Google Scholar
  23. Holland, J.H., Adaptation in Natural and Artificial Systems, Ann Arbor: Univ. of Michingan Press, 1992. Google Scholar
  24. Hower, W. and Jaboci, S., Parallel distributed constraint satisfaction, In Proc. of the Second International Workshop on Parallel Processing for Artificial Intelligence, IJCAI-93, Chambery, 1993, pp 65–68. Google Scholar
  25. Huang, W., Kao, C., Horng, J., A genetic algorithm approach for set covering problems, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 569–574. Google Scholar
  26. Johnson, D. S., Aragon, C. R., McGeoch, L. A. and Schevon, C., Optimization by simulated annealing: an experimental evaluation, Part II, Journal of Operations Research 39, 3 1991, pp 378–406. Google Scholar
  27. Khuri, S., Bäck, T. and Heitkötter, J., An evolutionary approach to combinatorial optimization problems, In Proceedings of CSC'94, Phoenix Arizona, 1994, ACM Press. Google Scholar
  28. Manderick, B. and Inayoshi, H., The weighted graph bi-partitioning problem: an analysis of GA performance, To appear in Proc. of the 3rd Parallel Problem Solving from Nature, Springer-Verlag, 1994. Google Scholar
  29. Mackworth, A.K., Concistency in networks of relations, Artificial Intelligence 8. 1977 pp 99–118. Google Scholar
  30. Meseguer, P., Constraint satisfactionproblems: an overview, AICOM, Vol. 2. no. 1 1989, pp 3–17. Google Scholar
  31. Michalewicz, Z. and Janikow, C. Z., Handling constraints in genetic algorithms, In Proc. of Int. Conference on Genetic Algorithms-91, Morgan Kaufman, 1991. Google Scholar
  32. Michalewicz, Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1994. Google Scholar
  33. Minton, S., Johnston, M. D., Philips, A. and Laird, P., Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems, Artificial Intelligence 58. 1992. pp 161–205. Google Scholar
  34. Mitchell, M., Forrest, S., and Holland, J., The royal road for genetic algorithms: fitness landscapes and GA performance, In Proc. of the First European Conference on Artificial Life, Cambridge, MA, MIT Press, 1991. Google Scholar
  35. Morris, P., On the density of solutions in equilibrium points for the n-queens problem, In Proc. AAAI-92, San Jose, CA 1992, pp 428–433. Google Scholar
  36. Paechter, B., Cumming, S., Luchian, H. and Petriuc, M., Two solutions for the general timetable problem using evolutionary methods, In Proc. of the First IEEE Conference on Evolutionary Computation, Orlando, Fl. 1994, pp 300–305. Google Scholar
  37. Paredis, J., Exploiting constraints as background knowledge for a case-study for scheduling, In Proc. Parallel Problem Solving from Nature, 1992, Elsevier. Google Scholar
  38. Sosic, R., Gu, J., A polynomial time algorithm for the n-queens problem, SIGART 1 (3), 1990, pp 7–11. Google Scholar
  39. Starkweather, T., Mc Daniel, S., Mathias, K., Whitley, D. and Whitley, C., A comparison of genetic sequenceing operators, In Proc. of Int. Conference on Genetic Algorithms-91, 1991, pp 69–76. Google Scholar
  40. Tsang, E. P. K. and Warwick, T., Applying genetic algorithms to constraint satisfaction optimization problems, In Proc. of ECAI-90, 1990, pp 649–654. Google Scholar
  41. Yamada, T. and Nakano, R., A genetic algorithm applicable to large-scale job-shop problems, In Proc. Parallel Problem Solving from Nature, 1992, Elsevier, pp 281–290. Google Scholar

Author information

Authors and Affiliations

  1. Dept. of Mathematics and Computer Science, Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081, HV Amsterdam, The Netherlands Ágoston Eiben, Paul-Erik Raué & Zsófia Ruttkay
  1. Ágoston Eiben