Comparing evolutionary algorithms on binary constraint satisfaction problems
Authors:
- 14 October 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 7 (5) , 424-444
Abstract
Constraint handling is not straightforward in evolutionary algorithms (EAs) since the usual search operators, mutation and recombination, are 'blind' to constraints. Nevertheless, the issue is highly relevant, for many challenging problems involve constraints. Over the last decade, numerous EAs for solving constraint satisfaction problems (CSP) have been introduced and studied on various problems. The diversity of approaches and the variety of problems used to study the resulting algorithms prevents a fair and accurate comparison of these algorithms. This paper aligns related work by presenting a concise overview and an extensive performance comparison of all these EAs on a systematically generated test suite of random binary CSPs. The random problem instance generator is based on a theoretical model that fixes deficiencies of models and respective generators that have been formerly used in the evolutionary computing field.Keywords
This publication has 39 references indexed in Scilit:
- Evolutionary Algorithms for the Satisfiability ProblemEvolutionary Computation, 2002
- Test-case generator for nonlinear continuous parameter optimization techniquesIEEE Transactions on Evolutionary Computation, 2000
- Solving constraint satisfaction problems using hybrid evolutionary searchIEEE Transactions on Evolutionary Computation, 1998
- Adaptive penalties for evolutionary graph coloring1998
- Modelling exceptionally hard constraint satisfaction problems1997
- GENOCOPCommunications of the ACM, 1996
- Locating the phase transition in binary constraint satisfaction problemsArtificial Intelligence, 1996
- An empirical study of phase transitions in binary constraint satisfaction problemsArtificial Intelligence, 1996
- Coevolutionary ComputationArtificial Life, 1995
- Exploiting the deep structure of constraint problemsArtificial Intelligence, 1994