Paper Info
Title
Phase Transition Properties of Clustered Travelling Salesman Problem Instances Generated with Evolutionary Computation
Abstract
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.
Year
DOI
Venue
2004
10.1007/978-3-540-30217-9_16
Lecture Notes in Computer Science
Keywords
Field
DocType
satisfiability,evolutionary algorithm,phase transition,evolutionary computing,random sampling,travelling salesman problem
Nearest neighbour algorithm,Cluster (physics),Mathematical optimization,Evolutionary algorithm,Computer science,Algorithm,Evolutionary computation,Travelling salesman problem,Sampling (statistics),Euclidean geometry,Genetic algorithm
Conference
Volume
ISSN
Citations 
3242
0302-9743
6
PageRank 
References 
Authors
0.52
11
2
Name
Order
Citations
PageRank
Jano I. van Hemert134133.09
neil b urquhart28314.70