%0 Book Section
%D 2015
%T Evolutionary Computation and Constraint Satisfaction
%A van Hemert, J.
%E Kacpryk, J.
%E Pedrycz, W.
%K constraint satisfaction
%K evolutionary computation
%X 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.
%I Springer
%P 1271–1284
%G eng
%& 65
%R 10.1007/978-3-662-43505-2
%0 Book Section
%B Studies in Computational Intelligence
%D 2008
%T Contraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem
%A Juhos, I.
%A van Hemert, J. I.
%E Cotta, C.
%E van Hemert, J. I.
%K constraint satisfaction
%K evolutionary computation
%K graph colouring
%B Studies in Computational Intelligence
%I Springer
%P 167--184
%G eng
%9 incollection
%0 Conference Proceedings
%D 2008
%T European Graduate Student Workshop on Evolutionary Computation
%A Di Chio, Cecilia
%A Giacobini, Mario
%A van Hemert, Jano
%E Di Chio, Cecilia
%E Giacobini, Mario
%E van Hemert, Jano
%K evolutionary computation
%X 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.
%G eng
%9 proceedings
%0 Conference Proceedings
%B Lecture Notes in Computer Science
%D 2008
%T Evolutionary Computation in Combinatorial Optimization, 8th European Conference
%A van Hemert, Jano
%A Cotta, Carlos
%E van Hemert, Jano
%E Cotta, Carlos
%K evolutionary computation
%X 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.
%B Lecture Notes in Computer Science
%I Springer
%V LNCS 4972
%G eng
%9 proceedings
%0 Conference Paper
%B Lecture Notes in Computer Science
%D 2008
%T Graph Colouring Heuristics Guided by Higher Order Graph Properties
%A Juhos, Istv\'{a}n
%A van Hemert, Jano
%E van Hemert, Jano
%E Cotta, Carlos
%K evolutionary computation
%K graph colouring
%X 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.
%B Lecture Notes in Computer Science
%I Springer
%V 4972
%P 97--109
%G eng
%9 inproceedings
%0 Conference Proceedings
%D 2007
%T European Graduate Student Workshop on Evolutionary Computation
%A Giacobini, Mario
%A van Hemert, Jano
%E Mario Giacobini
%E van Hemert, Jano
%K evolutionary computation
%X 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.
%C Valencia, Spain
%G eng
%9 proceedings
%0 Conference Proceedings
%B Lecture Notes in Computer Science
%D 2007
%T Evolutionary Computation in Combinatorial Optimization, 7th European Conference
%A Cotta, Carlos
%A van Hemert, Jano
%E Carlos Cotta
%E van Hemert, Jano
%K evolutionary computation
%X 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.
%B Lecture Notes in Computer Science
%I Springer
%V LNCS 4446
%G eng
%U http://springerlink.metapress.com/content/105633/
%9 proceedings
%0 Conference Proceedings
%D 2006
%T European Graduate Student Workshop on Evolutionary Computation
%A Giacobini, Mario
%A van Hemert, Jano
%E Giacobini, Mario
%E van Hemert, Jano
%K evolutionary computation
%X 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.
%C Budapest, Hungary
%G eng
%9 proceedings
%0 Journal Article
%J Evolutionary Computation
%D 2006
%T Evolving combinatorial problem instances that are difficult to solve
%A van Hemert, J. I.
%K constraint programming
%K constraint satisfaction
%K evolutionary computation
%K problem evolving
%K satisfiability
%K travelling salesman
%X 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.
%B Evolutionary Computation
%V 14
%P 433--462
%G eng
%U http://www.mitpressjournals.org/toc/evco/14/4
%9 article
%0 Conference Paper
%B Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006)
%D 2006
%T Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO
%A Gruber, M.
%A van Hemert, J. I.
%A Raidl, G. R.
%E Maarten Keijzer
%E et al
%K constraint satisfaction
%K evolutionary computation
%K variable neighbourhood search
%X 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.
%B Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2006)
%I ACM
%C Seattle, USA
%V 2
%P 1187--1194
%G eng
%9 inproceedings
%0 Conference Proceedings
%B Lecture Notes in Computer Science
%D 2005
%T Genetic Programming, Proceedings of the 8th European Conference
%A Keijzer, M.
%A Tettamanzi, A.
%A Collet, P.
%A van Hemert, J.
%A Tomassini, M.
%E M. Keijzer
%E A. Tettamanzi
%E P. Collet
%E van Hemert, J.
%E M. Tomassini
%K evolutionary computation
%B Lecture Notes in Computer Science
%I Springer
%V 3447
%@ 3-540-25436-6
%G eng
%U http://www.springeronline.com/sgw/cda/frontpage/0,11855,3-40100-22-45347265-0,00.html?changeHeader=true
%9 proceedings
%0 Conference Paper
%B LNCS
%D 2004
%T Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation
%A van Hemert, J. I.
%A la Poutré, J. A.
%E Xin Yao
%E Edmund Burke
%E Jose A. Lozano
%E Jim Smith
%E Juan J. Merelo-Guerv\'os
%E John A. Bullinaria
%E Jonathan Rowe
%E Peter Ti\v{n}o Ata Kab\'an
%E Hans-Paul Schwefel
%K dynamic problems
%K evolutionary computation
%K vehicle routing
%X 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.
%B LNCS
%I Springer-Verlag
%C Birmingham, UK
%V 3242
%P 690--699
%@ 3-540-23092-0
%G eng
%9 inproceedings
%0 Conference Paper
%B LNCS
%D 2004
%T Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation
%A van Hemert, J. I.
%A Urquhart, N. B.
%E Xin Yao
%E Edmund Burke
%E Jose A. Lozano
%E Jim Smith
%E Juan J. Merelo-Guerv\'os
%E John A. Bullinaria
%E Jonathan Rowe
%E Peter Ti\v{n}o Ata Kab\'an
%E Hans-Paul Schwefel
%K evolutionary computation
%K problem evolving
%K travelling salesman
%X 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.
%B LNCS
%I Springer-Verlag
%C Birmingham, UK
%V 3242
%P 150--159
%@ 3-540-23092-0
%G eng
%U http://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz
%9 inproceedings
%0 Journal Article
%J Journal of Heuristics
%D 2004
%T Robust parameter settings for variation operators by measuring the resampling ratio: A study on binary constraint satisfaction problems
%A van Hemert, J. I.
%A Bäck, T.
%K constraint satisfaction
%K evolutionary computation
%K resampling ratio
%X 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.
%B Journal of Heuristics
%V 10
%P 629--640
%G eng
%9 article
%0 Conference Paper
%B Springer Lecture Notes on Computer Science
%D 2004
%T A Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems
%A van Hemert, J. I.
%A Solnon, C.
%E J. Gottlieb
%E G. Raidl
%K ant colony optimisation
%K constraint programming
%K constraint satisfaction
%K evolutionary computation
%X 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.
%B Springer Lecture Notes on Computer Science
%I Springer-Verlag, Berlin
%P 114--123
%@ 3-540-21367-8
%G eng
%9 inproceedings