%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 Conference Paper
%B Springer Lecture Notes on Computer Science
%D 2002
%T Measuring the Searched Space to Guide Efficiency: The Principle and Evidence on Constraint Satisfaction
%A van Hemert, J. I.
%A Bäck, T.
%E J. J. Merelo
%E A. Panagiotis
%E H.-G. Beyer
%E Jos{\'e}-Luis Fern{\'a}ndez-Villaca{\~n}as
%E Hans-Paul Schwefel
%K constraint satisfaction
%K resampling ratio
%X In 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.
%B Springer Lecture Notes on Computer Science
%I Springer-Verlag, Berlin
%P 23--32
%@ 3-540-44139-5
%G eng
%9 inproceedings