Computing Threshold Sequences

Enrico Schumann

## Keywords

Threshold Accepting

Unreviewed

# Quantile-Based Methods

The threshold sequence in Threshold Accepting (TA) needs to be closely linked to the chosen definition of the neighbourhood. Larger neighbourhoods, which imply larger changes from one candidate solution to the next, should be accompanied by larger initial threshold values, and vice versa. Winker and Fang  suggested to obtain thresholds in a purely data-driven procedure; the pseudocode is given below.

In words: Select a large number \$n_{\mathtt{Deltas}}\$ of random solutions, and one neighbour for each. Then compute the absolute differences in the objective function between each pair. The thresholds are then descreasing quantiles of these changes. At the extreme (as in the given algorithm), every absolute difference constitutes one threshold. There is some evidence that starting the algorithm with a lower quantile improves the efficiency. Hence \$n_{\mathtt{Deltas}}\$ is usually greater than \$n_{\mathtt{Rounds}}\$.

A variant of this approach is have a ‘random walk’ through the data, see the following pseudocode ().