by van Hemert, J and NB Urquhart
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.
Reference:
Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation (van Hemert, J and NB Urquhart), In Parallel Problem Solving from Nature (Xin Yao, Edmund Burke, Jose A Lozano, Jim Smith, Juan J Merelo-Guervós, John A Bullinaria, Jonathan Rowe, Peter Ti\vno Ata Kabán, Hans-Paul Schwefel, eds.), Springer, volume 3242, 2004.
Bibtex Entry:
@article{HU2004,
_day = {18},
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.},
address = {Birmingham, UK},
author = {van Hemert, J and NB Urquhart},
date-added = {2008-08-18 12:44:11 +0100},
date-modified = {2008-08-18 12:44:11 +0100},
editor = {Xin Yao and Edmund Burke and Jose A Lozano and Jim Smith and Juan J Merelo-Guerv\'os and John A Bullinaria and Jonathan Rowe and Peter Ti\v{n}o Ata Kab\'an and Hans-Paul Schwefel},
isbn = {3-540-23092-0},
journal = {Parallel Problem Solving from Nature},
keywords = {problem evolving; evolutionary computation; travelling salesman},
pages = {150--159},
pdf = {http://www.vanhemert.co.uk/publications/ppsn2004.Phase_transition_properties_of_clustered_travelling_salesman_problem_instances_generated_with_evolutionary_computation.pdf},
publisher = {Springer},
series = {LNCS},
title = {Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation},
url = {http://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz},
volume = {3242},
year = {2004},
bdsk-url-1 = {http://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz}}