The
Traveling Salesman
Problem
is the problem of a salesman who wants to find a shortest possible trip:
(1). starting from his home
town, (2). go through a given set of customer cities,
and (3). return to his home town.
Formally, TSP can be represented by
a complete weighted graph G=(V,E) with V being the set of vertices,
representing the cities, and E the set of edges fully connecting the
vertices. Each edge is assigned a value d<i-j>, which is the
distance between vertex i and j, with i and
j element of V. Then, TSP is the problem of finding a minimal length
Hamiltonian
circuit of the graph, where a Hamiltonian circuit is a closed tour
visiting exactly once each of the vertices of G. For symmetric TSP, the
distances between the cities are independent of the direction of
traversing the edges, that is, d<i-j>=d<j-i>
for every pair of nodes. In the more general asymmetric TSP (ATSP) at
least for one pair of nodes (i,j) we have d<i-j>!=d<j-i>.
Some example of TSP Instances
Benchmark TSP instances can be
found in
TSPLIB. Here are some examples of TSP instances based on the distribution of
cities.
Left to right: gil262 (random
spread), d198 (several clusters), pr107 (grid pattern), tsp225
(grid pattern).
Fitness Landscape and Search
Trajectory Analysis
Observable characteristics of TSP
fitness landscape:
-. There exist
"Big Valley" characteristic in various (if
not all) TSP instances
where good solutions are
clustered near to each other, and there is only "one" such cluster.
-. This is quite logical as good
(near optimal) TSP
solutions are generally share a lot number of similar edges.
-. When the best found solution is placed in the center of the screen,
then other
blue circles (good),
green triangles (medium), and
yellow
rectangles (bad) are encircling it, with the
black dots (very bad)
further outside.
TSP Fitness
Landscape, zoomed out
The same landscape, zoomed in
Observable behavior of Iterated Local Search (ILS):
The standard TSP-ILS manages to find
position near the best found solution, but once it is trapped in a
(deep) local optima, its standard perturbation fails to bring the ILS
out of that region. The search is trapped. The final best solution
reported by the ILS will be the local optima in this unfortunate search
region. This phenomenon is also observed using Run Time Distribution (RTD)
- a stagnation.
The tuned TSP-ILS-T (Tuned) is TSP-ILS,
but this time, after certain number of iterations elapsed without
improvement, force a stronger diversification (much stronger than the
ILS perturbation strength) to force it escape from the current search
region. The ILS will end up in different place somewhere near the best
found solution and resume from there. This TSP-ILS-T has higher
potential to hit the best found solution than TSP-ILS.
References
These results are reported in more
details in our publications (download the local copy of those papers
here):
S. Halim, R. Yap, H.C. Lau. An Integrated White+Black Box Approach for
Designing and Tuning Stochastic Local Search.
In Principles and Practice of Constraint Programming (CP
2007, Providence, Rhode Island, USA, September 23-27, 2007):
332-347
S. Halim, R. Yap, H.C. Lau.
Viz: A
Visual Analysis Suite for Explaining Local Search Behavior.
In User Interface System and Technology (UIST
2006, Montreux, Switzerland, October 15-18, 2006): 57-66
This document, results_tsp.html, has been accessed 5281 times since 05-Sep-08 17:52:03 SGT.
This is the 1st time it has been accessed today.
A total of 2869 different hosts have accessed this document in the
last 5714 days; your host, ec2-3-14-6-194.us-east-2.compute.amazonaws.com, has accessed it 1 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.
