INSPIRING FUTURES

Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation.

van Hemert, Jano I and Urquhart, Neil B (2004) Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation. In: Parallel Problem Solving From Nature (PPSN) VIII, 18th-22nd September 2004, Birmingham, England, UK.

Full text not available from this repository. (Request a copy)

Abstract/Description

We introduce 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.

Item Type: Conference or Workshop Item (Paper)
ISBN: 3540230920
Additional Information: Paper in: Yao, Xin ... et al. (eds.) Parallel Problem Solving from Nature: 8th International Conference, Birmingham, UK, September 18-22, 2004, Proceedings. Lecture Notes in Comptuter Science Vol 3242. Berlin: Springer & Heidelberg: Gmbh, 2004.
Uncontrolled Keywords: Constraint theory; Evolutionary computing; Random processes; Clusters; Optimization; Sampling methods;
University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods
Library of Congress Subjects: Q Science > QA Mathematics > QA76 Computer software
Item ID: 1755
Depositing User: RAE Import
Date Deposited: 21 Jul 2008 12:57
Last Modified: 26 Oct 2010 13:49
URI: http://researchrepository.napier.ac.uk/id/eprint/1755

Actions (login required)

View Item

Edinburgh Napier University is a registered Scottish charity. Registration number SC018373