Threshold Accepting

Author

Enrico Schumann

Keywords

Threshold Accepting

Review Status

Unreviewed

The algorithm

Threshold Accepting (TA) is a local search method and was first described by Dueck and Scheuer [1] and Moscato and Fontanari [2]. For a detailed description, see Winker [3].

A classical local search starts with a random feasible solution and then explores its neighbourhood in the solution space by moving (usually randomly) from its current position, accepting a new solution if and only if it improves the objective function. TA overcomes the problem of stopping in local minima by also allowing uphill-moves, that is TA also accepts new solutions which lead to higher objective function values.

The pseudo-code can be given as follows

PC_TA.pdf

Here, $f$ is the objective function to be minimised. $x^c$ denotes the current solution, $x^n$ is the ‘new’ (or neighbour) solution, and $\mathcal{X}$ is the set of feasible solutions.

TA starts with a (random) feasible solution. Given a threshold sequence $\tau$ of length $n_\mathrm{{Rounds}}$, one can see that TA always accepts a solution that improves the objective function $f$, but deteriorations are only accepted if they are not worse than a particular threshold, $\tau_r$. Over time, the threshold decreases to zero, thus TA turns into a classical local search.

Neighbourhood and Thresholds

To implement TA, three points need to be specified:

  1. The objective function $f$: This function is generally given by the problem at hand.
  2. The neigbourhood definition (the function $\mathcal{N}$): Given a candidate solution $x^c$, one needs to define how to move from this solution to an alternative, but ‘close’ solution $x^n$. (Mathematically speaking, the new solution must be in the neighbourhood of $x^c$)
  3. The thresholds: Given a neigbourhood definition, one needs to determine the magnitude of the deterioration in the objective function that the algorithm should still accept for a new solution.

Whereas the first of these points is usually clear from the given problem, the second and third are closely related and need more attention. Larger neighbourhoods often require larger initial thresholds, et vice versa. Methods have been proposed to generate the thresholds in a purely data-driven way, see for example Winker and Fang [4]. For a more detailed description of this approach, see the ‘Tutorials’ links below.

Internal Links

Concepts
Simulated Annealing
Tutorials
Computing Threshold Sequences
Some Diagnostics for Threshold Accepting
Tips
Related Articles

External links

References
1. Dueck, G. and T. Scheuer (1990). Threshold Accepting. A General Purpose Optimization Algorithm Superior to Simulated Annealing. Journal of Computational Physics 90, 161-175.
2. Moscato, P. and J. Fontanari (1990). Stochastic Versus Deterministic Update in Simulated Annealing. Physics Letters A 146, 204-208.
4. Winker, P. and K. Fang (1997). Application of Threshold-Accepting to the Evaluation of the Discrepancy of a Set of Points. SIAM Journal on Numerical Analysis 34, 2028-2042.
Weblinks
The R-package NMOF contains an implementation of Threshold Accepting (the function TAopt). The package is available from R-Forge .

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License