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 -