Jano I van Hemert
Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation.
van Hemert, Jano I; Urquhart, Neil B
Abstract
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.
Citation
van Hemert, J. I., & Urquhart, N. B. (2004). Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation.
Conference Name | Parallel Problem Solving From Nature (PPSN) VIII |
---|---|
Start Date | Sep 18, 2004 |
End Date | Sep 22, 2004 |
Publication Date | Sep 1, 2004 |
Deposit Date | Jul 21, 2008 |
Peer Reviewed | Peer Reviewed |
Pages | 151-160 |
ISBN | 3540230920 |
Keywords | Constraint theory; Evolutionary computing; Random processes; Clusters; Optimization; Sampling methods; |
Public URL | http://researchrepository.napier.ac.uk/id/eprint/1755 |
You might also like
State assignment for sequential circuits using multi-objective genetic algorithm
(2011)
Journal Article
Manipulation and optimization techniques for Boolean logic
(2010)
Journal Article
Optimization of MPRM functions using tabular techniques and genetic algorithms.
(2008)
Journal Article
Agent motion planning with GAs enhanced by memory models.
(2001)
Journal Article
Demo paper: AGADE - Scalability of ontology based agent simulations
(2016)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search