back to main page

3. Western Sahara: 29 cities


initialisation

random Two methods were used to create the initial tours. In most cases a random tour was used, generated by repeatedly picking random cities from the pool of unallocated ones. An example of this is given in Figure 3.1.
greedy
An alternative method was to generate a greedy tour by starting at a random city, then repeatedly choosing the closest unallocated city. This results in a tour that is locally optimal near the beginning, and becomes less optimal towards the end, when there are fewer options left. An example is given in Figure 3.2.

The greedy routing serves as a useful benchmark for evaluating the performance of the following methods, which attempt to find a more globally optimal solution. Additionally, the methods can be 'seeded' with a greedy tour, to see whether that improves their ultimate performance and efficiency.

uniform random sampling

Optimisation by random sampling
Using random sampling, improvement was observed from the random initial tour, as can be seen in Figure 3.3. Note, however, that the trials-axis is on a log scale, so there is very little improvement after about 100,000 trials. The relative error never got below 100%. Seeding with a greedy tour generally resulted in no observed improvement.

Running for 10,000,000 trials took an average of 9.1 seconds, and gave an average relative error of 117.1%, mean deviation 2.2%.



simulated annealing

Optimisation by SA
The SA method gave obvious improvement from the random initial tour. It rapidly leaves behind random sampling, as shown in Figure 3.4. (Unless otherwise stated, temperature T=0.5 (constant). More on this later). The method of perturbing the tour seemed to be important. Interestingly, simple swapping did slightly better than the reverse/shift operator for the first 50 or so trials, but then the opposite is true after about 200 trials.

Each curve on Figure 3.4 shows the average relative error from three runs, and the bars show mean deviations from the average.

Figure 3.5 shows the continuation of Figure 3.4 up to 10,000 trials. Note that here (and from now on) the relative error axis is on a log scale, to emphasise convergence behaviour close to the optimum.

Optimisation by SA

The divergence of the SA methods using reverse/shift and swapping perturbations continues. In fact, on this time scale, it made the difference between converging to a near-optimal solution, and apparently stagnating at about 20% error. However, it should be noted that the results of the swapping method have high deviation (see Table 3.1); also, it may not be a fair comparison since one reverse/shift operation could be thought of as several swap operations.

Seeding SA (using reverse/shift perturbation) with a greedy initial tour still resulted in substantial improvement at first, and on average had a better running solution until about 2000 trials. Convergence to near-optimality (1% relative error) occurred at about the same time as with random seeding, or later.

Table 3.1. Performance of Simulated Annealing after 10,000 trials, averaged over 3 runs. Here temperature T=0.5 where relevant.

 average relative error (%) and mean deviation
 trials for average rel. err. to reach greedy level (30.8%)
 trials for average rel. err. to reach 1%
 CPU time (secs)
random sampling
 117.1 +/- 2.2
 --
 --
 9.1
SA (swapping)
 22.8 +/- 11.4
 2381
 --
 12.1
SA (reverse/shift)
 0.2 +/- 0.2
 491
 3475
 13.2
SA with greedy seed (reverse/shift)
 0.7 +/- 0.9
 0
 5333
 13.2

Table 3.1 confirms the previous comments about relative performance. It also suggests that greedy seeding may inhibit convergence at small relative errors (below 1%). The difference in running time of the methods is small.

For an investigation of the effect of temperature on Simulated Annealing, see the Canadian problem.

evolutionary algorithm

The population (parent population) was set to 50, with a birth rate of 20, giving 1000 offspring in each generation. The first type of selection method used was Boltzmann 10% selection (see methods section).

Evolutionary Figure 3.6 shows the optimisation over 100,000 trials (100 generations). The difference between a constant high temperature and constant zero temperature is surprisingly little. There is a slight suggestion that high temperature does better at high errors, and low temperature does better at low errors, as expected from the concept of annealing.

Seeding the algorithm with greedy tours in this context means that each parent is set to a greedy tour from a random starting point -- so they are not necessarily all the same. In contrast to SA, this seeding seemed to converge at a similar rate to the random seeding, and since it started at a better level, finds a good solution much faster, although again may have had trouble improving below 1% relative error.



Evolutionary The insensitivity to temperature could be due to the population size providing a buffer against selecting poor tours. To explore further the role of temperature (as well as the role of population), comparisons of high and zero temperature were done with several population sizes. The results are shown in Figure 3.7.

In Fugure 3.7, the blue curves (population p=50) are the same as on Figure 3.6. It is apparent that smaller populations can give more efficient convergence (on this measure). However, as population is reduced, high temperature severely degrades the convergence rate; the selection is not strong enough to ensure that fitness is maintained in the small population. Additionally, even with zero temperature, the optimisation seems to struggle at the final stages with a very small population -- presumably because the 10% sampling is too small.

Evolutionary The best performance from Boltzmann 10% selection seems to come from zero temperature. This is equivalent to a basic scheme of incrementing fitness of the better tour when each is compared with another randomly chosen. A simpler scheme along these lines is rank selection, so that was implemented. Rank selection also solves the sampling problem of small populations.

Figure 3.8 shows the effect of population size with rank selection. Again we see that smaller populations are more efficient, and there are now apparently no interference effects on small populations. Comparing rank selection with Boltzmann 10% selection for a population of 50 shows that the rank method is more efficient. The obvious concern with this method is potential loss of diversity, or stagnation in local minima, but this should be still be less severe than for SA with zero temperature.

Looking at optimisation measured against number of trials, the EA always performed worse than SA. In fact, such an evolutionary algorithm with rank selection is equivalent to Simulated Annealing (with T=0) if the population is 1 and birth rate is 1. Anything less direct than that seems to be less efficient. However, this measure of 'trials' (see methods section) is not necessarily useful. The most relevant measure of performance is the time taken.
Table 3.2. Performance of Evolutionary Algorithm after 100,000 trials, averaged over 3 runs. The annealing results are from 10,000 trials. The "time to reach 1%" is calculated by assuming that time is linear with trials. Here temperature T=0 where relevant, and as usual the birth rate is 20.
population and selection method
 generations
 average relative error (%) and mean deviation
 trials for average rel. err. to reach greedy level (30.8%)
 trials for average rel. err. to reach 1%
 CPU time (secs)
 time to reach 1% (secs)
Simulated Annealing
 --
 0.2 +/- 0.2
 491
 3,475
 13.2
 4.58
p=50, Boltzmann 10%
 100
 0.3 +/- 0.2
 20,000
 50,000
 2.7
 1.35
p=25, Boltzmann 10%
 200
 0.2 +/- 0.2
 10,500
 31,000
 1.5
 0.47
p=5, Boltzmann 10%
 1000
 0.7 +/- 0.2
 3,900
 62,000
 0.5
 0.31
p=50, rank
 100
 0.5 +/- 1.6
 15,000
 36,000
 0.2
 0.07
p=25, rank
 200
 0.9 +/- 0.5
 8,000
 27,000
 0.2
 0.05
p=5, rank
 1000
 0.5 +/- 0.7
 2,000
 9,000
 0.2
 0.02
p=1, rank
 5000
 1.2 +/- 0.8
 820
 --
(6,000 to 1.2%)
 0.2
 --
(0.01 to 1.2%)
p=50, Boltzmann 10% with greedy seed
 100
 0.5 +/- 0.7
 0
 21,000
 2.7
 0.57

It can be seen from Table 3.2 that, contrary to the conclusions from looking at the number of trials, the evolutionary algorithm always performed better than Simulated Annealing, by the time to converge to 1% average relative error. So while SA does better with the tours it looks at, it accepts more changes than necessary and that is costly. As from the previous discussion, it is confirmed that here rank selection is much more efficient than Boltzmann 10% selection. The other result that can be seen from Table 3.2 is that seeding with a greedy tour -- at least for that case -- results in convergence in 42% of the time of random seeding.

For this data set the exact solution was found with both Simulated Annealing and the Evolutionary Algorithm. The optimal routing is shown in Figure 3.8.

solution
back to main page