01484nas 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.gz01378nas a2200229 4500008004100000020001800041245010800059210006900167260002800236300001100264520063400275653002800909653002100937100001600958700001300974700001600987700001801003700001601021700004801037700002401085856003901109 2002 eng d a3-540-44139-500aMeasuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction0 aMeasuring the Searched Space to Guide Efficiency The Principle a bSpringer-Verlag, Berlin a23--323 aIn 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.10aconstraint satisfaction10aresampling ratio1 aHemert, J I1 aBäck, T1 aMerelo, J J1 aPanagiotis, A1 aBeyer, H -G1 aFern{\'a}ndez-Villaca{\~n}as, Jos{\'e}-Luis1 aSchwefel, Hans-Paul uhttp://research.nesc.ac.uk/node/27