back to main page

4. Canada: 4663 cities


greedy
To give some indication of the scale of this problem, an example of a greedy tour is given in Figure 4.1. Much of the detail can't be seen in this image, since there is significant variation in scale.


simulated annealing

Annealing For this problem random sampling seems to make essentially no improvement, remaining about 10,000% error, as expected given the unimaginable enormity of the tour space.

Simulated Annealing shows rapid improvement from the random seed tour initially (see Figure 4.2). The optimisation over time appears to be logarithmic on a log scale (or linear on a log-log scale), implying a second-order logarithmic function.

Seeding the algorithm with a greedy tour gives an obvious advantage in efficiency, but both cases still cannot do much better than about 10% relative error (see Table 4.1). Given the low (essentially zero) temperature, this suggests that the SA is stuck in a local minimum and may benefit from a different annealing schedule.

Table 4.1. Performance of Simulated Annealing after 1,000,000,000 trials. These are results from a single run. Here temperature T=0.5 where relevant.

 relative error (%)
 trials for rel. err. to reach 10%
 CPU time (mins)
random sampling
 9512.4
 --
 21.8
SA
 7.7
 252,000,000
 29.5
SA with greedy seed
 7.3
 89,000,000
 29.2


Annealing It was established that there was little or no effect of a temperature (T) of 50 compared to zero. A strong effect could be seen with T=10,000 (see Figure 4.3): there was an initial improvement to about 5,000% error, then no change.

The first schedule tried was to drop the temperature instantly from T=10,000 to T=0 after half the iterations -- the blue curve on Figure 4.3. The idea was to search globally for a while, then greedily optimise. This turned out to be just like running T=0 for half the time. A less extreme approach of starting with T=1,000 gave similar results.

Since the solution seemed to be stagnating with constant temperature, a linear decrease was tried from T=10,000 to T=0 at the end of the run (the green curve). Clearly it was still improving when the run stopped -- it needed more time with T=0. So, the linear decrease was tried in the first half, and T=0 for the second half (green dotted curve). While it attained the level of the constant T=0 run, there was no advantage, at least on this time scale.

Incidentally, the steady state tour lengths for T=10,000 and T=1,000 are probably due to the scaling of the problem. As can be seen from Figure 4.1, a wide range of lengths are involved. Presumably there are some changes on a large scale for which these values of T are insignificant, but smaller-scale 'polishing' gets overwhelmed.

evolutionary algorithm

Evolutionary The evolutionary algorithm took a surprisingly long time to run. It was only possible to run 10,000,000 trials in a reasonable time, being around 100 times slower than SA. This was unexpected since the opposite was the case with the 29 city data set.

It was found that temperature had no effect with a population as large as 50 (see Figure 4.4) when using Boltzmann 10% selection. Again rank selection was the more efficient method for populations of 50 and 5. A linear schedule similar to the one that gave reasonable results for SA (above) was tried with a population of 5, but it did poorly. Its stagnation is probably due to interference from the small selection sampling.

These observations are consistent with the smaller data set, but the dramatic difference is in the time to run (see Table 4.2). The advantage in that regard from a smaller population seems to have disappeared. The poor scaling may be characteristic of the algorithm; Fogel (1988) only reported using the approach up to 100 cities -- 4663 is a whole different kettle of fish. However, I suspect it is due to unneccesary array copying in my code (oops... i'm used to dealing with references). Also, I had turned off the -fast compilating switch while debugging, and forgot to turn it back on! [Both these theories were tested and turned out to be false.]
Table 4.2. Performance of Evolutionary Algorithm after 10,000,000 trials. These are results from a single run. The annealing time is interpolated from the run in Table 4.1. Here temperature T=0 where relevant, and as usual the birth rate is 20.
population and selection method
 generations
 relative error (%)
 CPU time (mins)
Simulated Annealing
 --
 104.8
 0.3
p=50, Boltzmann 10%
 10,000
 1090.0
 64.5
p=50, rank
 10,000
 924.7
 59.0
p=5, Boltzmann 10% (linear schedule)
 100,000
 1557.0
 28.3
p=5, rank
 100,000
 150.7
 27.6

parallelisation

There was some benefit from the parallelisation approach (see methods section), although I'm not sure whether it is more than would come from trivial parallelisation. Synchronisation occurred every 1,000,000 trials (100 times). It was run on 4 processors, each handling 100,000,000 trials. The result was better than simply running 100,000,000, but not as good as running 400,000,000 trials sequentially -- see Table 4.3. The result was equivalent to running sequentially for 134,000,000 trials.

In terms of the number of trials examined, the speedup from running on 4 CPUs was 3.47.

Table 4.3. Performance of parallel vs sequential Simulated Annealing for running 400,000,000 trials.

 trials
 relative error (%)
 CPU time (mins)
 wall time (mins)
single processor, constant T=0
 100,000,000
 15.2
 3.0
 3.0
single processor, constant T=0
 400,000,000
 9.0
 11.8
 11.8
4 processors, T={1000, 36, 1.3, 0.05} linear down to 0
 400,000,000
 12.2
 12.1
 3.4



For this data set a reasonable solution (~7% relative error) was found using Simulated Annealing. This is shown in Figure 4.5.

solution
back to main page