Solving binary constraint satisfaction problems using evolutionary algorithms with an adaptive fitness function

1. Th. Bäck, A.E. Eiben, and M.E. Vink. A superior evolutionary algorithm for 3-SAT. In D. Waagen N. Saravanan and A.E. Eiben, editors, Proceedings of the 7th Annual Conference on Evolutionary Programming, Lecture Notes in Computer Science. Springer, 1998. in press.

   Google Scholar 

2. J. Bowen and G. Dozier. Solving constraint satisfaction problems using a genetic/systematic search hybride that realizes when to quit. In Eshelman [11], pages 122–129.

   Google Scholar 

3. P. Cheeseman, B. Kanefsky, and W.M. Taylor. Where the really hard problems are. In Proceedings of the 12th International Conference on Artificial Intelligence, pages 331–337. Morgan Kaufmann, 1991.

   Google Scholar 

4. G. Dozier, J. Bowen, and D. Bahler. Solving small and large constraint satisfaction problems using a heuristic-based microgenetic algorithms. In IEEE [12], pages 306–311.

   Google Scholar 

5. G. Dozier, J. Bowen, and D. Bahler. Solving randomly generated constraint satisfaction problems using a micro-evolutionary hybrid that evolves a population of hill-climbers. In Proceedings of the 2nd IEEE Conference on Evolutionary Computation, pages 614–619. IEEE Press, 1995.

   Google Scholar 

6. A.E. Eiben, P.-E. Raué, and Zs. Ruttkay. Constrained problems. In L. Chambers, editor, Practical Handbook of Genetic Algorithms, pages 307–365. CRC Press, 1995.

   Google Scholar 

7. A.E. Eiben and Zs. Ruttkay. Self-adaptivity for constraint satisfaction: Learning penalty functions. In Proceedings of the 3rd IEEE Conference on Evolutionary Computation, pages 258–261. IEEE Press, 1996.

   Google Scholar 

8. A.E. Eiben and Zs. Ruttkay. Constraint satisfaction problems. In Th. Bäck, D. Fogel, and M. Michalewicz, editors, Handbook of Evolutionary Algorithms, pages C5.7:1–C5.7:8. IOP Publishing Ltd. and Oxford University Press, 1997.

   Google Scholar 

9. A.E. Eiben and J.K. van der Hauw. Adaptive penalties for evolutionary graphcoloring. In J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, and D. Snyers, editors, Artificial Evolution'97, number 1363 in LNCS, pages 95–106. Springer, Berlin, 1997.

   Google Scholar 

10. A.E. Eiben, J.K. van der Hauw, and J.I. van Hemert. Graph coloring with adaptive evolutionary algorithms. Journal of Heuristics, 4:25–46, 1998.

    Article  MATH  Google Scholar 

11. L.J. Eshelman, editor. Proceedings of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann, 1995.

    Google Scholar 

12. Proceedings of the 1st IEEE Conference on Evolutionary Computation. IEEE Press, 1994.

    Google Scholar 

13. Proceedings of the 4th IEEE Conference on Evolutionary Computation. IEEE Press, 1997.

    Google Scholar 

14. E. Marchiori. Combining constraint processing and genetic algorithms for constraint satisfaction problems. In Th. Bäck, editor, Proceedings of the 7th International Conference on Genetic Algorithms, pages 330–337. Morgan Kaufmann, 1997.

    Google Scholar 

15. Z. Michalewicz and M. Michalewicz. Pro-life versus pro-choice strategies in evolutionary computation techniques. In Palaniswami M., Attikiouzel Y., Marks R.J., Fogel D., and Fukuda T., editors, Computational Intelligence: A Dynamic System Perspective, pages 137–151. IEEE Press, 1995.

    Google Scholar 

16. P. Morris. The breakout method for escaping from local minima. In Proceedings of the 11th National Conference on Artificial Intelligence, AAAI-93, pages 40–45. AAAI Press/The MIT Press, 1993.

    Google Scholar 

17. J. Paredis. Co-evolutionary constraint satisfaction. In Y. Davidor, H.-P. Schwefel, and R. Männer, editors, Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, number 866 in Lecture Notes in Computer Science, pages 46–56. Springer-Verlag, 1994.

    Google Scholar 

18. J. Paredis. Co-evolutionary computation. Artificial Life, 2(4):355–375, 1995.

    Article  Google Scholar 

19. J. Paredis. Coevolving cellular automata: Be aware of the red queen. In Thomas Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA97), San Francisco, CA, 1997. Morgan Kaufmann.

    Google Scholar 

20. P. Prosser. An empirical study of phase transitions in binary constraint satisfaction problems. Artificial Intelligence, 81:81–109, 1996.

    Article  MathSciNet  Google Scholar 

21. M.C. Riff-Rojas. Using the knowledge of the constraint network to design an evolutionary algorithm that solves CSP. In IEEE [13], pages 279–284.

    Google Scholar 

22. M.C. Riff-Rojas. Evolutionary search guided by the constraint network to solve CSP. In IEEE [13], pages 337–348.

    Google Scholar 

23. B.M. Smith. Phase transition and the mushy region in constraint satisfaction problems. In A. G. Cohn, editor, Proceedings of the 11th European Conference on Artificial Intelligence, pages 100–104. Wiley, 1994.

    Google Scholar 

24. E. Tsang. Foundation of Constraint Satisfaction. Academic Press, 1993.

    Google Scholar 

25. D. Whitley. The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In J. David Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms (ICGA '89), pages 116–123, San Mateo, California, 1989. Morgan Kaufmann Publishers, Inc.

    Google Scholar 

26. C.P. Williams and T. Hogg. Exploiting the deep structure of constraint problems. Artificial Intelligence, 70:73–117, 1994.

    Article  MATH  Google Scholar 

Download references