back to main page
2. methods and code
finding the exact solution
The TSP is an NP-complete problem, implying that there is no known algorithm
to solve it exactly in better than O(an) time (for n
cities). In fact, there are (n-1)!/2 possible combinations, so to
try every one requires factorial time with the problem size. This method
was implemented for a 6-city problem, with code
adapted from the given one.
The optimal tour found for the 6 cities was:
1 --- 2 --- 5 --- 4 --- 6 --- 3 --- 1
which has distance 9.242640 units.
The processor times for the 5 and 6 city runs were below the timer resolution,
so could only be estimated by running each program many times. From running
each 1000 times, the timings were:
Table 2.1. Exact method timings.
|
measured time (sec)
|
run time (sec)
|
combinations
|
combination time
|
5 cities
|
2.3424000e-02
|
2.3424000e-05
|
120
|
1.952e-07
|
6 cities
|
1.6787200e-01
|
1.6787200e-04
|
720
|
2.332e-07
|
The time for each combination can be estimated as 2e-07 seconds. Extrapolating
the factorial scaling of the problem, the number of combinations for the
29 cities problem is 8.84e30. This gives a time estimate of 1.77e24 seconds,
or 5.60e16 years. Clearly an approximate method is requried.
code structure
The code for this project was written in Fortran 90 (not available on non-proprietry
systems, but may be adapted for f95 or even f77). The exact algorithm is
hard-coded for 6 cities: tspexact6.f90.
The method could be made generic using recursion.
The other methods investigated are coded as modules, and run from a single
executable. Each run is defined and parameterised using a configuration
file. The files are:
Table 2.2. Source code and other files.
These can be downloaded as an archive: tsp.tgz. Additionally, a couple
of perl scripts were written to process the results:
interp.pl interpolates the reported
output from several files so that data points exist at all steps. It also
calculates the average relative error of the solutions.tourtrace.pl looks up the
(x, y) points for a tour so that it can be plotted.
All methods were set to run a pre-specified number of iterations, rather
than for a set time or using any convergence criteria. This may be inefficient
but is simpler for comparison (at least on one measure -- more on this later).
On every run the validity of the final tour was checked, by ensuring that
each city was included once.
uniform random sampling
A naïve baseline approach is to take the tour with minimum distance
from uniform random sampling. On each iteration the tour is permuted by
randomly choosing two indices and swapping them.
On the 6 city set, using 100 iterations, the processor time averaged over
1000 repeats was 5.9e-05 seconds, which is of similar order to the exact
method. Three attempts gave solutions with relative errors of 3.1%, 1.2%
and 0%, which seems reasonable for uniform sampling of such a large proportion.
Sketching the solution confirms that it is sane.
simulated annealing
Simulated Annealing attempts to mimic the process of annealing in slowly
cooled metal. The atoms rearrange themselves into a near-optimal energy
state despite the apparent improbability of this occuring. Simulated Annealing
abstracts this with a kind of biased random walk: some solution is subjected
to a perturbation with probability dependent on the cost of doing so, and
the current "temperature". Specifically, the method mimics the Boltzmann
distribution: the probability of accepting a pertubation is exp(cost/T).
In other words, more costly exploration can occur at high temperatures. The
annealing schedule specifies how T changes over time -- this
is generally decreasing.
The Boltzmann probability distribution is generated with the Metropolis
algorithm. The perturbation used is either a simple swapping of any two cities,
or equal probability of reversing a tour segment and shifting a tour segment
to another locus. In general this approach is similar to that given in Numerical Recipies.
The configuration allowed setting a constant, linear decrease, quadratic
decrease (staying longer at high temperatures), or linear-constant schedule.
The initial temperature could also be set. Generally, unless otherwise specified,
a constant temperature of 0.5 was used. This was the initial temperature given
in Numerical Recipies, but of course should depend on the scale of the problem.
To enable comparison with other methods, runs were specified by the number
of trials to run -- the number of different tours looked at. For SA
this includes rejected perturbations.
evolutionary algorithm
The method was similar to that described in Fogel, D. B. (1998). An Evolutionary
Approach to the Traveling Salesman Problem. Biological Cybernetics.
60. 139-144. Note that this is not a genetic algorithm, since it uses no genetic
operators (crossover).
The term 'population' is used to mean the parent population. Another
parameter is the birth rate -- each parent is perturbed this many times to
create offspring. Additionally, the parents are included in the 'genepool'
for selection along with their offspring.
So, here the number of trials = (parents * birth_rate + parents) * generations.
Two possible methods of selection were used. 'Boltzmann 10% selection' works
as follows: each tour is compared with 10% of its peers chosen at random.
If the difference c is accepted by the Metropolis-Boltzmann function
(i.e. if c < 0 or rand < exp(c/T)) then the original
tour's fitness is incremented. Otherwise, the rival tour's fitness is incremented.
Finally, those tours with the highest fitness are selected to be parents.
The other method is rank selection. This simply means sorting the tours
by length and selecting the shortest ones to be parents.
parallelisation
MPI was used to implement
a parallel version of Simulated Annealing. Some advantage was attempted to
be gained by occasionally synchronising each process with the best tour found
so far. The idea was to exploit any variation to 'ride the lower bound'.
There may be a trade-off between the cost of more frequent communication and the advantage of taking more frequent minima.
Variation was promoted by running the processes with different annealing schedules
(although there would be variation anyway from random peturbaions):
initial temperature was given an exponential distribution across processes so that
at least one was practically zero. For each the temperature dropped linearly over time to zero.
This method was applied to the Canada problem.
back to main page