Threshold Accepting

Enrico Schumann

Keywords

Threshold Accepting

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

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.