01935nas a2200181 4500008004100000022002200041245005700063210005700120260001300177300001600190520140400206653002801610653002901638100001401667700001601681700001601697856004001713 2015 eng d a978030662043594-500aEvolutionary Computation and Constraint Satisfaction0 aEvolutionary Computation and Constraint Satisfaction bSpringer a1271–12843 aIn 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.10aconstraint satisfaction10aevolutionary computation1 aHemert, J1 aKacpryk, J.1 aPedrycz, W. uhttp://research.nesc.ac.uk/node/99800602nas a2200181 4500008004100000245010900041210006900150260001300219300001300232653002800245653002900273653002000302100001300322700001600335700001300351700001600364856004000380 2008 eng d00aContraction-Based Heuristics to Improve the Efficiency of Algorithms Solving the Graph Colouring Problem0 aContractionBased Heuristics to Improve the Efficiency of Algorit bSpringer a167--18410aconstraint satisfaction10aevolutionary computation10agraph colouring1 aJuhos, I1 aHemert, J I1 aCotta, C1 aHemert, J I uhttp://research.nesc.ac.uk/node/32201067nas a2200169 4500008004100000245006700041210006700108520053500175653002900710100002100739700002100760700001700781700002100798700002100819700001700840856004000857 2008 eng d00aEuropean Graduate Student Workshop on Evolutionary Computation0 aEuropean Graduate Student Workshop on Evolutionary Computation3 aEvolutionary 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. 10aevolutionary computation1 aDi Chio, Cecilia1 aGiacobini, Mario1 aHemert, Jano1 aDi Chio, Cecilia1 aGiacobini, Mario1 aHemert, Jano uhttp://research.nesc.ac.uk/node/32301940nas a2200169 4500008004100000245008400041210006900125260001300194490001400207520141000221653002901631100001701660700001801677700001701695700001801712856004001730 2008 eng d00aEvolutionary Computation in Combinatorial Optimization, 8th European Conference0 aEvolutionary Computation in Combinatorial Optimization 8th Europ bSpringer0 vLNCS 49723 aMetaheuristics 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.10aevolutionary computation1 aHemert, Jano1 aCotta, Carlos1 aHemert, Jano1 aCotta, Carlos uhttp://research.nesc.ac.uk/node/23401306nas a2200193 4500008004100000245007100041210006900112260001300181300001200194490000900206520073400215653002900949653002000978100002200998700001701020700001701037700001801054856004001072 2008 eng d00aGraph Colouring Heuristics Guided by Higher Order Graph Properties0 aGraph Colouring Heuristics Guided by Higher Order Graph Properti bSpringer a97--1090 v49723 aGraph 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.10aevolutionary computation10agraph colouring1 aJuhos, Istv\'{a}n1 aHemert, Jano1 aHemert, Jano1 aCotta, Carlos uhttp://research.nesc.ac.uk/node/23301031nas a2200157 4500008004100000245006700041210006700108260002000175520053500195653002900730100002100759700001700780700002100797700001700818856003800835 2007 eng d00aEuropean Graduate Student Workshop on Evolutionary Computation0 aEuropean Graduate Student Workshop on Evolutionary Computation aValencia, Spain3 aEvolutionary 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. 10aevolutionary computation1 aGiacobini, Mario1 aHemert, Jano1 aGiacobini, Mario1 aHemert, Jano uhttp://research.nesc.ac.uk/node/502073nas a2200169 4500008004100000245008400041210006900125260001300194490001400207520152900221653002901750100001801779700001701797700001801814700001701832856005401849 2007 eng d00aEvolutionary Computation in Combinatorial Optimization, 7th European Conference0 aEvolutionary Computation in Combinatorial Optimization 7th Europ bSpringer0 vLNCS 44463 aMetaheuristics 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.10aevolutionary computation1 aCotta, Carlos1 aHemert, Jano1 aCotta, Carlos1 aHemert, Jano uhttp://springerlink.metapress.com/content/105633/01034nas a2200157 4500008004100000245006700041210006700108260002200175520053500197653002900732100002100761700001700782700002100799700001700820856003900837 2006 eng d00aEuropean Graduate Student Workshop on Evolutionary Computation0 aEuropean Graduate Student Workshop on Evolutionary Computation aBudapest, Hungary3 aEvolutionary 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. 10aevolutionary computation1 aGiacobini, Mario1 aHemert, Jano1 aGiacobini, Mario1 aHemert, Jano uhttp://research.nesc.ac.uk/node/1001287nas a2200193 4500008004100000245007300041210006900114300001300183490000700196520067600203653002700879653002800906653002900934653002100963653001900984653002401003100001601027856005001043 2006 eng d00aEvolving combinatorial problem instances that are difficult to solve0 aEvolving combinatorial problem instances that are difficult to s a433--4620 v143 aIn 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.10aconstraint programming10aconstraint satisfaction10aevolutionary computation10aproblem evolving10asatisfiability10atravelling salesman1 aHemert, J I uhttp://www.mitpressjournals.org/toc/evco/14/401469nas a2200217 4500008004100000245011200041210006900153260002200222300001500244490000600259520078400265653002801049653002901077653003401106100001401140700001601154700001501170700002101185700000701206856003801213 2006 eng d00aNeighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO0 aNeighborhood Searches for the Bounded Diameter Minimum Spanning aSeattle, USAbACM a1187--11940 v23 aWe 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.10aconstraint satisfaction10aevolutionary computation10avariable neighbourhood search1 aGruber, M1 aHemert, J I1 aRaidl, G R1 aKeijzer, Maarten1 aal uhttp://research.nesc.ac.uk/node/800751nas a2200241 4500008004100000020001800041245006800059210006700127260001300194490000900207653002900216100001500245700001800260700001400278700001400292700001700306700001500323700001800338700001400356700001400370700001700384856010800401 2005 eng d a3-540-25436-600aGenetic Programming, Proceedings of the 8th European Conference0 aGenetic Programming Proceedings of the 8th European Conference bSpringer0 v344710aevolutionary computation1 aKeijzer, M1 aTettamanzi, A1 aCollet, P1 aHemert, J1 aTomassini, M1 aKeijzer, M1 aTettamanzi, A1 aCollet, P1 aHemert, J1 aTomassini, M uhttp://www.springeronline.com/sgw/cda/frontpage/0,11855,3-40100-22-45347265-0,00.html?changeHeader=true01484nas a2200301 4500008004100000020001800041245008800059210006900147260003600216300001300252490000900265520058500274653002100859653002900880653002000909100001600929700001700945700001300962700001800975700002000993700001501013700003001028700002401058700001901082700001801101700002401119856003901143 2004 eng d a3-540-23092-000aDynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation0 aDynamic Routing Problems with Fruitful Regions Models and Evolut aBirmingham, UKbSpringer-Verlag a690--6990 v32423 aWe 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.10adynamic problems10aevolutionary computation10avehicle routing1 aHemert, J I1 aPoutré, J A1 aYao, Xin1 aBurke, Edmund1 aLozano, Jose, A1 aSmith, Jim1 aMerelo-Guerv\'os, Juan, J1 aBullinaria, John, A1 aRowe, Jonathan1 an, Peter Ti\v1 aSchwefel, Hans-Paul uhttp://research.nesc.ac.uk/node/1901761nas a2200301 4500008004100000020001800041245012300059210006900182260003600251300001300287490000900300520078600309653002901095653002101124653002401145100001601169700001801185700001301203700001801216700002001234700001501254700003001269700002401299700001901323700001801342700002401360856007501384 2004 eng d a3-540-23092-000aPhase transition properties of clustered travelling salesman problem instances generated with evolutionary computation0 aPhase transition properties of clustered travelling salesman pro aBirmingham, UKbSpringer-Verlag a150--1590 v32423 aThis 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.10aevolutionary computation10aproblem evolving10atravelling salesman1 aHemert, J I1 aUrquhart, N B1 aYao, Xin1 aBurke, Edmund1 aLozano, Jose, A1 aSmith, Jim1 aMerelo-Guerv\'os, Juan, J1 aBullinaria, John, A1 aRowe, Jonathan1 an, Peter Ti\v1 aSchwefel, Hans-Paul uhttp://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz01316nas a2200169 4500008004100000245014000041210006900181300001300250490000700263520073000270653002801000653002901028653002101057100001601078700001301094856003901107 2004 eng d00aRobust parameter settings for variation operators by measuring the resampling ratio: A study on binary constraint satisfaction problems0 aRobust parameter settings for variation operators by measuring t a629--6400 v103 aIn 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.10aconstraint satisfaction10aevolutionary computation10aresampling ratio1 aHemert, J I1 aBäck, T uhttp://research.nesc.ac.uk/node/1801488nas a2200217 4500008004100000020001800041245013700059210006900196260002800265300001300293520075400306653002801060653002701088653002801115653002901143100001601172700001401188700001601202700001301218856003901231 2004 eng d a3-540-21367-800aA Study into Ant Colony Optimization, Evolutionary Computation and Constraint Programming on Binary Constraint Satisfaction Problems0 aStudy into Ant Colony Optimization Evolutionary Computation and bSpringer-Verlag, Berlin a114--1233 aWe 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.10aant colony optimisation10aconstraint programming10aconstraint satisfaction10aevolutionary computation1 aHemert, J I1 aSolnon, C1 aGottlieb, J1 aRaidl, G uhttp://research.nesc.ac.uk/node/22