Back to heuristics for global optimisation

Threshold Accepting

Threshold accepting (TA) is a generally applicable heuristic algorithm developed by Dueck and Scheuer [1], that can be used to solve combinatorial optimisation problems. TA is an iterative improvement method formally very similar to simulated annealing (SA). Given an arbitrary solution to the problem both methods involve the selection of a neighbouring solution. This neighbourhood configuration replaces the existing configuration if a certain criterion is achieved and it is at this level that the essential difference between the two algorithms becomes apparent.

In SA a new solution is accepted automatically if it is better (according to the objective function) than the current configuration, if it is worse then acceptance is governed by a probability. The probability is dependent on a control parameter called temperature that is slowly decreased (cooled) as the algorithm proceeds. Cooling has the effect that the probability of a worse solution being accepted is reduced as time increases.

TA accepts a new solution if it is better than or 'not much worse` than the the existing configuration, formalised in the algorithm by a threshold parameter. In the case of minimisation, any new solution less than the current configuration quality plus the threshold is accepted as the new current solution. No stochastic test is required in the solution replacement procedure, acceptance is totally deterministic, although selection of a specific neighbourhood solution is stochastic. The greater simplicity of the algorithm leads to a claim of superiority of TA over SA made by Dueck and Scheuer [1]. The threshold is decreased with time so that fewer worse solutions are accepted as the algorithm proceeds. Given a problem structure with cost function f(x) and neighbourhood structure N(x,s) for a given configuration x and a neighbourhood generation operator s, the pseudo-algorithm for TA in the case of minimisation is given in figure 2.6.

The Great Deluge Algorithm and the Record-to-Record Travel Algorithm

The TA principle can be simplified further, resulting in two new generally applicable heuristics introduced by Dueck [2], the Great Deluge algorithm (GDA) and the Record-to-Record Travel algorithm (RTRT). These two algorithms differ from TA in the decision rule by which a neighbourhood candidate is accepted to replace the current solution.

It is easy to visualise the GDA, especially for maximisation. The quality of all solutions in the sample space together define a surface or a landscape of which the maximum or highest point is sought. By letting it `rain' continuously, the amount of water covering the landscape, the water level, increases. The algorithm `walks' around the fictitious landscape ensuring the solution never falls below this rising water level. At some point the algorithm will become trapped on a `peak' surround by water and the hope is that the algorithm has then found a peak that is nearly optimal. This analogy is formalised by the pseudo-algorithm given in figure 2.7, showing the minimisation variant of the GDA, with cost function f(x)and neighbourhood structure N(x,s) for a solution x.

Record-to-Record Travel is very similar to the GDA, the difference again lies in the acceptance rule. The RTRT algorithm accepts any new solution that has a quality not much worse than the best solution (or record) found so far. The pseudo-algorithm given in figure 2.8 shows this method implemented for minimisation, with the same problem structure as given for the GDA.

Parameter Selection

The claim is made that the GDA and the RTRT algorithm depend only on a single parameter, for the GDA this is the rain speed and for the RTRT algorithm it is the allowed deviation. Selecting a small deviation and large rain speed, for the two algorithms respectively, poor quality solutions are quickly produced. Alternatively, by choosing a large deviation and a small rain speed good quality solutions are slowly generated. The job then lies in finding appropriate values for these parameters, balancing the two goals of speed and quality of solution. The exact balance will depend on the specific problem under consideration, though generally it is hoped the algorithm will find good solutions in a `reasonable' amount of time.

Dueck [2] makes several suggestions concerning the selection of appropriate parameter values. For the GDA the rain speed UP is proposed to be on average somewhat smaller than 1% of the average distance between the quality of the current solution and water level. This water level update is achieved by replacing the current LEVEL update procedure given in figure 2.7 with:

where UP now represents a fraction. In the RTRT algorithm the allowed deviation DEV is taken to be a fixed fraction of the quality of the current best solution (i.e. a fraction of RECORD), although a further suggestion is made that the size of the fraction should be reduced as the algorithm proceeds. This first proposal is achieved by replacing the RECORD update procedure in figure 2.8 with:

References

  1. Gunter Dueck and Tobias Scheuer. Threshold Accepting: A General Purpose Optimization Algorithm Superior to Simulated Annealing. Journal of Computational Physics, 90:161--175, 1990.
  2. Gunter Dueck. New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel. Technical report, IBM Germany, Heidelberg Scientific Center, 1990.

This page is under development. Last updated 17 January 1995

Grant Telfar

grant@isor.vuw.ac.nz