TY - CHAP T1 - Evolutionary Computation and Constraint Satisfaction Y1 - 2015 A1 - van Hemert, J. ED - Kacpryk, J. ED - Pedrycz, W. KW - constraint satisfaction KW - evolutionary computation AB - In this chapter we will focus on the combination of evolutionary computation techniques and constraint satisfaction problems. Constraint Programming (CP) is another approach to deal with constraint satisfaction problems. In fact, it is an important prelude to the work covered here as it advocates itself as an alternative approach to programming (Apt). The first step is to formulate a problem as a CSP such that techniques from CP, EC, combinations of the two (c.f., Hybrid) or other approaches can be deployed to solve the problem. The formulation of a problem has an impact on its complexity in terms of effort required to either find a solution or proof no solution exists. It is therefore vital to spend time on getting this right. Main differences between CP and EC. CP defines search as iterative steps over a search tree where nodes are partial solutions to the problem where not all variables are assigned values. The search then maintain a partial solution that satisfies all variables assigned values. Instead, in EC most often solver sample a space of candidate solutions where variables are all assigned values. None of these candidate solutions will satisfy all constraints in the problem until a solution is found. Another major difference is that many constraint solvers from CP are sound whereas EC solvers are not. A solver is sound if it always finds a solution if it exists. PB - Springer ER - 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 - Generic T1 - European Graduate Student Workshop on Evolutionary Computation Y1 - 2008 A1 - Di Chio, Cecilia A1 - Giacobini, Mario A1 - van Hemert, Jano ED - Di Chio, Cecilia ED - Giacobini, Mario ED - van Hemert, Jano KW - evolutionary computation AB - Evolutionary computation involves the study of problem-solving and optimization techniques inspired by principles of evolution and genetics. As any other scientific field, its success relies on the continuity provided by new researchers joining the field to help it progress. One of the most important sources for new researchers is the next generation of PhD students that are actively studying a topic relevant to this field. It is from this main observation the idea arose of providing a platform exclusively for PhD students. ER - TY - Generic T1 - Evolutionary Computation in Combinatorial Optimization, 8th European Conference T2 - Lecture Notes in Computer Science Y1 - 2008 A1 - van Hemert, Jano A1 - Cotta, Carlos ED - van Hemert, Jano ED - Cotta, Carlos KW - evolutionary computation AB - Metaheuristics have shown to be effective for difficult combinatorial optimization problems appearing in various industrial, economical, and scientific domains. Prominent examples of metaheuristics are evolutionary algorithms, tabu search, simulated annealing, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, ant colony optimization and estimation of distribution algorithms. Problems solved successfully include scheduling, timetabling, network design, transportation and distribution, vehicle routing, the travelling salesman problem, packing and cutting, satisfiability and general mixed integer programming. EvoCOP began in 2001 and has been held annually since then. It is the first event specifically dedicated to the application of evolutionary computation and related methods to combinatorial optimization problems. Originally held as a workshop, EvoCOP became a conference in 2004. The events gave researchers an excellent opportunity to present their latest research and to discuss current developments and applications. Following the general trend of hybrid metaheuristics and diminishing boundaries between the different classes of metaheuristics, EvoCOP has broadened its scope over the last years and invited submissions on any kind of metaheuristic for combinatorial optimization. JF - Lecture Notes in Computer Science PB - Springer VL - LNCS 4972 ER - TY - CONF T1 - Graph Colouring Heuristics Guided by Higher Order Graph Properties T2 - Lecture Notes in Computer Science Y1 - 2008 A1 - Juhos, Istv\'{a}n A1 - van Hemert, Jano ED - van Hemert, Jano ED - Cotta, Carlos KW - evolutionary computation KW - graph colouring AB - Graph vertex colouring can be defined in such a way where colour assignments are substituted by vertex contractions. We present various hyper-graph representations for the graph colouring problem all based on the approach where vertices are merged into groups. In this paper, we show this provides a uniform and compact way to define algorithms, both of a complete or a heuristic nature. Moreover, the representation provides information useful to guide algorithms during their search. In this paper we focus on the quality of solutions obtained by graph colouring heuristics that make use of higher order properties derived during the search. An evolutionary algorithm is used to search permutations of possible merge orderings. JF - Lecture Notes in Computer Science PB - Springer VL - 4972 ER - TY - Generic T1 - European Graduate Student Workshop on Evolutionary Computation Y1 - 2007 A1 - Giacobini, Mario A1 - van Hemert, Jano ED - Mario Giacobini ED - van Hemert, Jano KW - evolutionary computation AB - Evolutionary computation involves the study of problem-solving and optimization techniques inspired by principles of evolution and genetics. As any other scientific field, its success relies on the continuity provided by new researchers joining the field to help it progress. One of the most important sources for new researchers is the next generation of PhD students that are actively studying a topic relevant to this field. It is from this main observation the idea arose of providing a platform exclusively for PhD students. CY - Valencia, Spain ER - TY - Generic T1 - Evolutionary Computation in Combinatorial Optimization, 7th European Conference T2 - Lecture Notes in Computer Science Y1 - 2007 A1 - Cotta, Carlos A1 - van Hemert, Jano ED - Carlos Cotta ED - van Hemert, Jano KW - evolutionary computation AB - Metaheuristics have often been shown to be effective for difficult combinatorial optimization problems appearing in various industrial, economical, and scientific domains. Prominent examples of metaheuristics are evolutionary algorithms, simulated annealing, tabu search, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and ant colony optimization. Successfully solved problems include scheduling, timetabling, network design, transportation and distribution, vehicle routing, the traveling salesman problem, satisfiability, packing and cutting, and general mixed integer programming. EvoCOP began in 2001 and has been held annually since then. It was the first event specifically dedicated to the application of evolutionary computation and related methods to combinatorial optimization problems. Originally held as a workshop, EvoCOP became a conference in 2004. The events gave researchers an excellent opportunity to present their latest research and to discuss current developments and applications as well as providing for improved interaction between members of this scientific community. Following the general trend of hybrid metaheuristics and diminishing boundaries between the different classes of metaheuristics, EvoCOP has broadened its scope over the last years and invited submissions on any kind of metaheuristic for combinatorial optimization. JF - Lecture Notes in Computer Science PB - Springer VL - LNCS 4446 UR - http://springerlink.metapress.com/content/105633/ ER - TY - Generic T1 - European Graduate Student Workshop on Evolutionary Computation Y1 - 2006 A1 - Giacobini, Mario A1 - van Hemert, Jano ED - Giacobini, Mario ED - van Hemert, Jano KW - evolutionary computation AB - Evolutionary computation involves the study of problem-solving and optimization techniques inspired by principles of evolution and genetics. As any other scientific field, its success relies on the continuity provided by new researchers joining the field to help it progress. One of the most important sources for new researchers is the next generation of PhD students that are actively studying a topic relevant to this field. It is from this main observation the idea arose of providing a platform exclusively for PhD students. CY - Budapest, Hungary 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 - 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 - Generic T1 - Genetic Programming, Proceedings of the 8th European Conference T2 - Lecture Notes in Computer Science Y1 - 2005 A1 - Keijzer, M. A1 - Tettamanzi, A. A1 - Collet, P. A1 - van Hemert, J. A1 - Tomassini, M. ED - M. Keijzer ED - A. Tettamanzi ED - P. Collet ED - van Hemert, J. ED - M. Tomassini KW - evolutionary computation JF - Lecture Notes in Computer Science PB - Springer VL - 3447 SN - 3-540-25436-6 UR - http://www.springeronline.com/sgw/cda/frontpage/0,11855,3-40100-22-45347265-0,00.html?changeHeader=true ER - TY - CONF T1 - Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation T2 - LNCS Y1 - 2004 A1 - van Hemert, J. I. A1 - la Poutré, J. A. ED - Xin Yao ED - Edmund Burke ED - Jose A. Lozano ED - Jim Smith ED - Juan J. Merelo-Guerv\'os ED - John A. Bullinaria ED - Jonathan Rowe ED - Peter Ti\v{n}o Ata Kab\'an ED - Hans-Paul Schwefel KW - dynamic problems KW - evolutionary computation KW - vehicle routing AB - We introduce the concept of fruitful regions in a dynamic routing context: regions that have a high potential of generating loads to be transported. The objective is to maximise the number of loads transported, while keeping to capacity and time constraints. Loads arrive while the problem is being solved, which makes it a real-time routing problem. The solver is a self-adaptive evolutionary algorithm that ensures feasible solutions at all times. We investigate under what conditions the exploration of fruitful regions improves the effectiveness of the evolutionary algorithm. JF - LNCS PB - Springer-Verlag CY - Birmingham, UK VL - 3242 SN - 3-540-23092-0 ER - TY - CONF T1 - Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation T2 - LNCS Y1 - 2004 A1 - van Hemert, J. I. A1 - Urquhart, N. B. ED - Xin Yao ED - Edmund Burke ED - Jose A. Lozano ED - Jim Smith ED - Juan J. Merelo-Guerv\'os ED - John A. Bullinaria ED - Jonathan Rowe ED - Peter Ti\v{n}o Ata Kab\'an ED - Hans-Paul Schwefel KW - evolutionary computation KW - problem evolving KW - travelling salesman AB - This paper introduces a generator that creates problem instances for the Euclidean symmetric travelling salesman problem. To fit real world problems, we look at maps consisting of clustered nodes. Uniform random sampling methods do not result in maps where the nodes are spread out to form identifiable clusters. To improve upon this, we propose an evolutionary algorithm that uses the layout of nodes on a map as its genotype. By optimising the spread until a set of constraints is satisfied, we are able to produce better clustered maps, in a more robust way. When varying the number of clusters in these maps and, when solving the Euclidean symmetric travelling salesman person using Chained Lin-Kernighan, we observe a phase transition in the form of an easy-hard-easy pattern. JF - LNCS PB - Springer-Verlag CY - Birmingham, UK VL - 3242 SN - 3-540-23092-0 UR - http://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz 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 -