TY  - JOUR
T1  - Comparing Evolutionary Algorithms on Binary Constraint Satisfaction Problems
JF  - IEEE Transactions on Evolutionary Computation
Y1  - 2003
A1  - Craenen, B. G. W.
A1  - Eiben, A. E.
A1  - van Hemert, J. I.
KW  - constraint satisfaction
AB  - Constraint handling is not straightforward in evolutionary algorithms (EA) 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 (EC) field.
VL  - 7
UR  - http://ieeexplore.ieee.org/xpl/abs_free.jsp?isNumber=27734&prod=JNL&arnumber=1237162&arSt=+424&ared=+444&arAuthor=+Craenen%2C+B.G.W.%3B++Eiben%2C+A.E.%3B++van+Hemert%2C+J.I.&arNumber=1237162&a_id0=1237161&a_id1=1237162&a_id2=1237163&a_id3=1237164&a_id4=12
ER  - 

TY  - CHAP
T1  - SAW-ing EAs: adapting the fitness function for solving constrained problems
T2  - New ideas in optimization
Y1  - 1999
A1  - Eiben, A. E.
A1  - van Hemert, J. I.
ED  - D. Corne
ED  - M. Dorigo
ED  - F. Glover
KW  - constraint satisfaction
AB  - In this chapter we describe a problem independent method for treating constrain ts in an evolutionary algorithm. Technically, this method amounts to changing the defini tion of the fitness function during a run of an EA, based on feedback from the search pr ocess. Obviously, redefining the fitness function means redefining the problem to be sol ved. On the short term this deceives the algorithm making the fitness values deteriorate , but as experiments clearly indicate, on the long run it is beneficial. We illustrate t he power of the method on different constraint satisfaction problems and point out other application areas of this technique.
JF  - New ideas in optimization
PB  - McGraw-Hill, London
ER  - 

TY  - CONF
T1  - Extended abstract: Solving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function
T2  - Proceedings of the Xth Netherlands/Belgium Conference on Artificial Intelligence (NAIC'98)
Y1  - 1998
A1  - Eiben, A. E.
A1  - van Hemert, J. I.
A1  - Marchiori, E.
A1  - Steenbeek, A. G.
ED  - la Poutré, J. A.
ED  - van den Herik, J.
KW  - constraint satisfaction
JF  - Proceedings of the Xth Netherlands/Belgium Conference on Artificial Intelligence (NAIC'98)
PB  - BNVKI, Dutch and the Belgian AI Association
N1  - Abstract of \cite{EHMS98}
ER  - 

TY  - JOUR
T1  - Graph Coloring with Adaptive Evolutionary Algorithms
JF  - Journal of Heuristics
Y1  - 1998
A1  - Eiben, A. E.
A1  - van der Hauw, J. K.
A1  - van Hemert, J. I.
KW  - constraint satisfaction
KW  - graph colouring
AB  - This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EA). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution.  This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping GA on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping GA and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.
PB  - Kluwer Academic Publishers
VL  - 4
ER  - 

TY  - CONF
T1  - Solving Binary Constraint Satisfaction Problems using Evolutionary Algorithms with an Adaptive Fitness Function
T2  - Springer Lecture Notes on Computer Science
Y1  - 1998
A1  - Eiben, A. E.
A1  - van Hemert, J. I.
A1  - Marchiori, E.
A1  - Steenbeek, A. G.
ED  - Eiben, A. E.
ED  - Th. B{\"a}ck
ED  - M. Schoenauer
ED  - H.-P. Schwefel
KW  - constraint satisfaction
AB  - This paper presents a comparative study of Evolutionary Algorithms (EAs) for Constraint Satisfaction Problems (CSPs). We focus on EAs where fitness is based on penalization of constraint violations and the penalties are adapted during the execution. Three different EAs based on this approach are implemented. For highly connected constraint networks, the results provide further empirical support to the theoretical prediction of the phase transition in binary CSPs.
JF  - Springer Lecture Notes on Computer Science
PB  - Springer-Verlag, Berlin
ER  -