Keywords: Travelling Salesman
http://vanhemert.co.uk/publications/index.php?keywords=travelling+salesman&bib=cv.bib&rss
bibtexbrowser v20101203Discovering the suitability of optimisation algorithms by learning from evolved instances
http://www.springerlink.com/content/6x83q3201gg71554/
Discovering the suitability of optimisation algorithms by learning from evolved instances (K.A. Smith-Miles, J.I. van Hemert), In Annals of Mathematics and Artificial Intelligence, volume 61, 2011.
cv.bib%3A%3ASmith-MilesHemert2011fk03 May 2011 00:00:00 +0000Evolving combinatorial problem instances that are difficult to solve
http://www.mitpressjournals.org/toc/evco/14/4
Evolving combinatorial problem instances that are difficult to solve (J.I. van Hemert), In Evolutionary Computation, volume 14, 2006.
In this paper we demonstrate how evolutionary computation can be used to acquire difficult to solve combinatorial problem instances, thereby stress-testing the corresponding algorithms used to solve these instances. The technique is applied in three important domains of combinatorial optimisation, binary constraint satisfaction, Boolean satisfiability, and the travelling salesman problem. Problem instances acquired through this technique are more difficult than ones found in popular benchmarks. We analyse these evolved instances with the aim to explain their difficulty in terms of structural properties, thereby exposing the weaknesses of corresponding algorithms. cv.bib%3A%3AHemert2006a01 Dec 2006 00:00:00 +0000Property analysis of symmetric travelling salesman problem instances acquired through evolution
http://vanhemert.co.uk/publications/index.php?key=Hemert2005&bib=cv.bib
Property analysis of symmetric travelling salesman problem instances acquired through evolution (J.I. van Hemert), In Evolutionary Computation in Combinatorial Optimization (G. Raidl, J. Gottlieb, eds.), Springer, 2005.
We show how an evolutionary algorithm can successfully be used to evolve a set of difficult to solve symmetric travelling salesman problem instances for two variants of the Lin-Kernighan algorithm. Then we analyse the instances in those sets to guide us towards deferring general knowledge about the efficiency of the two variants in relation to structural properties of the symmetric travelling salesman problem. cv.bib%3A%3AHemert200530 Mar 2005 00:00:00 +0000Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation
http://www.vanhemert.co.uk/files/clustered-phase-transition-tsp.tar.gz
Phase transition properties of clustered travelling salesman problem instances generated with evolutionary computation (J.I. van Hemert, N.B. 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.
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. cv.bib%3A%3AHU200418 Sep 2004 00:00:00 +0000