TY - CHAP T1 - Contraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem T2 - Studies in Computational Intelligence Y1 - 2008 A1 - Juhos, I. A1 - van Hemert, J. I. ED - Cotta, C. ED - van Hemert, J. I. KW - constraint satisfaction KW - evolutionary computation KW - graph colouring JF - Studies in Computational Intelligence PB - Springer ER - TY - JOUR T1 - Evolving combinatorial problem instances that are difficult to solve JF - Evolutionary Computation Y1 - 2006 A1 - van Hemert, J. I. KW - constraint programming KW - constraint satisfaction KW - evolutionary computation KW - problem evolving KW - satisfiability KW - travelling salesman AB - In this paper we demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances, thereby stress-testing the corresponding algorithms used to solve these instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms. VL - 14 UR - http://www.mitpressjournals.org/toc/evco/14/4 ER - TY - CONF T1 - Improving Graph Colouring Algorithms and Heuristics Using a Novel Representation T2 - Springer Lecture Notes on Computer Science Y1 - 2006 A1 - Juhos, I. A1 - van Hemert, J. I. ED - J. Gottlieb ED - G. Raidl KW - constraint satisfaction KW - graph colouring AB - We introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of an algorithm. Moreover, our model provides useful information for guiding heuristics as well as a compact description for algorithms. To verify the potential of the model, we use it in dsatur, in an evolutionary algorithm, and in the same evolutionary algorithm extended with heuristics. An empiricial investigation is performed to show an increase in efficiency on two problem suites , a set of practical problem instances and a set of hard problem instances from the phase transition. JF - Springer Lecture Notes on Computer Science PB - Springer-Verlag ER - TY - CONF T1 - Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO T2 - Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006) Y1 - 2006 A1 - Gruber, M. A1 - van Hemert, J. I. A1 - Raidl, G. R. ED - Maarten Keijzer ED - et al KW - constraint satisfaction KW - evolutionary computation KW - variable neighbourhood search AB - We consider the Bounded Diameter Minimum Spanning Tree problem and describe four neighbourhood searches for it. They are used as local improvement strategies within a variable neighbourhood search (VNS), an evolutionary algorithm (EA) utilising a new encoding of solutions, and an ant colony optimisation (ACO).We compare the performance in terms of effectiveness between these three hybrid methods on a suite f popular benchmark instances, which contains instances too large to solve by current exact methods. Our results show that the EA and the ACO outperform the VNS on almost all used benchmark instances. Furthermore, the ACO yields most of the time better solutions than the EA in long-term runs, whereas the EA dominates when the computation time is strongly restricted. JF - Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006) PB - ACM CY - Seattle, USA VL - 2 ER - TY - CONF T1 - Complexity Transitions in Evolutionary Algorithms: Evaluating the impact of the initial population T2 - Proceedings of the Congress on Evolutionary Computation Y1 - 2005 A1 - Defaweux, A. A1 - Lenaerts, T. A1 - van Hemert, J. I. A1 - Parent, J. KW - constraint satisfaction KW - transition models AB - This paper proposes an evolutionary approach for the composition of solutions in an incremental way. The approach is based on the metaphor of transitions in complexity discussed in the context of evolutionary biology. Partially defined solutions interact and evolve into aggregations until a full solution for the problem at hand is found. The impact of the initial population on the outcome and the dynamics of the process is evaluated using the domain of binary constraint satisfaction problems. JF - Proceedings of the Congress on Evolutionary Computation PB - {IEEE} Press ER - TY - CONF T1 - Evolutionary Transitions as a Metaphor for Evolutionary Optimization T2 - LNAI 3630 Y1 - 2005 A1 - Defaweux, A. A1 - Lenaerts, T. A1 - van Hemert, J. I. ED - M. Capcarrere ED - A. A. Freitas ED - P. J. Bentley ED - C. G. Johnson ED - J. Timmis KW - constraint satisfaction KW - transition models AB - This paper proposes a computational model for solving optimisation problems that mimics the principle of evolutionary transitions in individual complexity. More specifically it incorporates mechanisms for the emergence of increasingly complex individuals from the interaction of more simple ones. The biological principles for transition are outlined and mapped onto an evolutionary computation context. The class of binary constraint satisfaction problems is used to illustrate the transition mechanism. JF - LNAI 3630 PB - Springer-Verlag SN - 3-540-28848-1 ER - TY - CONF T1 - Heuristic Colour Assignment Strategies for Merge Models in Graph Colouring T2 - Springer Lecture Notes on Computer Science Y1 - 2005 A1 - Juhos, I. A1 - Tóth, A. A1 - van Hemert, J. I. ED - G. Raidl ED - J. Gottlieb KW - constraint satisfaction KW - graph colouring AB - In this paper, we combine a powerful representation for graph colouring problems with different heuristic strategies for colour assignment. Our novel strategies employ heuristics that exploit information about the partial colouring in an aim to improve performance. An evolutionary algorithm is used to drive the search. We compare the different strategies to each other on several very hard benchmarks and on generated problem instances, and show where the novel strategies improve the efficiency. JF - Springer Lecture Notes on Computer Science PB - Springer-Verlag, Berlin ER - TY - CONF T1 - Transition Models as an incremental approach for problem solving in Evolutionary Algorithms T2 - Proceedings of the Genetic and Evolutionary Computation Conference Y1 - 2005 A1 - Defaweux, A. A1 - Lenaerts, T. A1 - van Hemert, J. I. A1 - Parent, J. ED - H.-G. Beyer ED - et al KW - constraint satisfaction KW - transition models AB - This paper proposes an incremental approach for building solutions using evolutionary computation. It presents a simple evolutionary model called a Transition model. It lets building units of a solution interact and then uses an evolutionary process to merge these units toward a full solution for the problem at hand. The paper provides a preliminary study on the evolutionary dynamics of this model as well as an empirical comparison with other evolutionary techniques on binary constraint satisfaction. JF - Proceedings of the Genetic and Evolutionary Computation Conference PB - {ACM} Press ER - TY - CONF T1 - Binary Merge Model Representation of the Graph Colouring Problem T2 - Springer Lecture Notes on Computer Science Y1 - 2004 A1 - Juhos, I. A1 - Tóth, A. A1 - van Hemert, J. I. ED - J. Gottlieb ED - G. Raidl KW - constraint satisfaction KW - graph colouring AB - This paper describes a novel representation and ordering model that aided by an evolutionary algorithm, is used in solving the graph \emph{k}-colouring problem. Its strength lies in reducing the search space by breaking symmetry. An empirical comparison is made with two other algorithms on a standard suit of problem instances and on a suit of instances in the phase transition where it shows promising results. JF - Springer Lecture Notes on Computer Science PB - Springer-Verlag, Berlin SN - 3-540-21367-8 ER - TY - JOUR T1 - Robust parameter settings for variation operators by measuring the resampling ratio: A study on binary constraint satisfaction problems JF - Journal of Heuristics Y1 - 2004 A1 - van Hemert, J. I. A1 - Bäck, T. KW - constraint satisfaction KW - evolutionary computation KW - resampling ratio AB - In this article, we try to provide insight into the consequence of mutation and crossover rates when solving binary constraint satisfaction problems. This insight is based on a measurement of the space searched by an evolutionary algorithm. From data empirically acquired we describe the relation between the success ratio and the searched space. This is achieved using the resampling ratio, which is a measure for the amount of points revisited by a search algorithm. This relation is based on combinations of parameter settings for the variation operators. We then show that the resampling ratio is useful for identifying the quality of parameter settings, and provide a range that corresponds to robust parameter settings. VL - 10 ER - TY - CONF T1 - A Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems T2 - Springer Lecture Notes on Computer Science Y1 - 2004 A1 - van Hemert, J. I. A1 - Solnon, C. ED - J. Gottlieb ED - G. Raidl KW - ant colony optimisation KW - constraint programming KW - constraint satisfaction KW - evolutionary computation AB - We compare two heuristic approaches, evolutionary computation and ant colony optimisation, and a complete tree-search approach, constraint programming, for solving binary constraint satisfaction problems. We experimentally show that, if evolutionary computation is far from being able to compete with the two other approaches, ant colony optimisation nearly always succeeds in finding a solution, so that it can actually compete with constraint programming. The resampling ratio is used to provide insight into heuristic algorithms performances. Regarding efficiency, we show that if constraint programming is the fastest when instances have a low number of variables, ant colony optimisation becomes faster when increasing the number of variables. JF - Springer Lecture Notes on Computer Science PB - Springer-Verlag, Berlin SN - 3-540-21367-8 ER - 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 - CONF T1 - Evolving binary constraint satisfaction problem instances that are difficult to solve T2 - Proceedings of the IEEE 2003 Congress on Evolutionary Computation Y1 - 2003 A1 - van Hemert, J. I. KW - constraint satisfaction KW - problem evolving AB - We present a study on the difficulty of solving binary constraint satisfaction problems where an evolutionary algorithm is used to explore the space of problem instances. By directly altering the structure of problem instances and by evaluating the effort it takes to solve them using a complete algorithm we show that the evolutionary algorithm is able to detect problem instances that are harder to solve than those produced with conventional methods. Results from the search of the evolutionary algorithm confirm conjectures about where the most difficult to solve problem instances can be found with respect to the tightness. JF - Proceedings of the IEEE 2003 Congress on Evolutionary Computation PB - IEEE Press SN - 0-7803-7804-0 ER - TY - CONF T1 - A new permutation model for solving the graph k-coloring problem T2 - Kalmàr Workshop on Logic and Computer Science Y1 - 2003 A1 - Juhos, I. A1 - Tóth, A. A1 - Tezuka, M. A1 - Tann, P. A1 - van Hemert, J. I. KW - constraint satisfaction KW - graph colouring AB - This paper describes a novel representation and ordering model, that is aided by an evolutionary algorithm, is used in solving the graph k-coloring. A comparison is made between the new representation and an improved version of the traditional graph coloring technique DSATUR on an extensive list of graph k-coloring problem instances with different properties. The results show that our model outperforms the improved DSATUR on most of the problem instances. JF - Kalmàr Workshop on Logic and Computer Science ER - TY - CONF T1 - Comparing Classical Methods for Solving Binary Constraint Satisfaction Problems with State of the Art Evolutionary Computation T2 - Springer Lecture Notes on Computer Science Y1 - 2002 A1 - van Hemert, J. I. ED - S. Cagnoni ED - J. Gottlieb ED - E. Hart ED - M. Middendorf ED - G. Raidl KW - constraint satisfaction AB - Constraint Satisfaction Problems form a class of problems that are generally computationally difficult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of binary constraint satisfaction prob-lems. We find that the evolutionary algorithms are less effective than the classical techniques. JF - Springer Lecture Notes on Computer Science PB - Springer-Verlag, Berlin ER - TY - CONF T1 - Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction T2 - Springer Lecture Notes on Computer Science Y1 - 2002 A1 - van Hemert, J. I. A1 - Bäck, T. ED - J. J. Merelo ED - A. Panagiotis ED - H.-G. Beyer ED - Jos{\'e}-Luis Fern{\'a}ndez-Villaca{\~n}as ED - Hans-Paul Schwefel KW - constraint satisfaction KW - resampling ratio AB - In this paper we present a new tool to measure the efficiency of evolutionary algorithms by storing the whole searched space of a run, a process whereby we gain insight into the number of distinct points in the state space an algorithm has visited as opposed to the number of function evaluations done within the run. This investigation demonstrates a certain inefficiency of the classical mutation operator with mutation-rate 1/l, where l is the dimension of the state space. Furthermore we present a model for predicting this inefficiency and verify it empirically using the new tool on binary constraint satisfaction problems. JF - Springer Lecture Notes on Computer Science PB - Springer-Verlag, Berlin SN - 3-540-44139-5 ER - TY - CONF T1 - Use of Evolutionary Algorithms for Telescope Scheduling T2 - Integrated Modeling of Telescopes Y1 - 2002 A1 - Grim, R. A1 - Jansen, M. L. M. A1 - Baan, A. A1 - van Hemert, J. I. A1 - de Wolf, H. ED - Torben Anderson KW - constraint satisfaction KW - scheduling AB - LOFAR, a new radio telescope, will be designed to observe with up to 8 independent beams, thus allowing several simultaneous observations. Scheduling of multiple observations parallel in time, each having their own constraints, requires a more intelligent and flexible scheduling function then operated before. In support of the LOFAR radio telescope project, and in co-operation with Leiden University, Fokker Space has started a study to investigate the suitability of the use of evolutionary algorithms applied to complex scheduling problems. After a positive familiarisation phase, we now examine the potential use of evolutionary algorithms via a demonstration project. Results of the familiarisation phase, and the first results of the demonstration project are presented in this paper. JF - Integrated Modeling of Telescopes PB - The International Society for Optical Engineering ({SPIE}) VL - 4757 ER - TY - CONF T1 - Evolutionary Computation in Constraint Satisfaction and Machine Learning --- An abstract of my PhD. T2 - Proceedings of the Brussels Evolutionary Algorithms Day (BEAD-2001) Y1 - 2001 A1 - van Hemert, J. I. ED - Anne Defaweux ED - Bernard Manderick ED - Tom Lenearts ED - Johan Parent ED - Piet van Remortel KW - constraint satisfaction KW - data mining JF - Proceedings of the Brussels Evolutionary Algorithms Day (BEAD-2001) PB - Vrije Universiteit Brussel (VUB) ER - TY - CONF T1 - Constraint Satisfaction Problems and Evolutionary Algorithms: A Reality Check T2 - Proceedings of the Twelfth Belgium/Netherlands Conference on Artificial Intelligence (BNAIC'00) Y1 - 2000 A1 - van Hemert, J. I. ED - van den Bosch, A. ED - H. Weigand KW - constraint satisfaction AB - Constraint satisfaction has been the subject of many studies. Different areas of research have tried to solve all kind of constraint problems. Here we will look at a general model for constraint satisfaction problems in the form of binary constraint satisfaction. The problems generated from this model are studied in the research area of constraint programming and in the research area of evolutionary computation. This paper provides an empirical comparison of two techniques from each area. Basically, this is a check on how well both areas are doing. It turns out that, although evolutionary algorithms are doing well, classic approaches are still more successful. JF - Proceedings of the Twelfth Belgium/Netherlands Conference on Artificial Intelligence (BNAIC'00) PB - BNVKI, Dutch and the Belgian AI Association 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 -