Computing Threshold Sequences

Author

Enrico Schumann

Keywords

Threshold Accepting

Review Status

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 [1] suggested to obtain thresholds in a purely data-driven procedure; the pseudocode is given below.

PC_TA3.pdf

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 ([2]).

PC_TA2.pdf

Internal Links

Concepts
Threshold Accepting
Tutorials
Tips
Related Articles

External links

References
1. 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.
2. Gilli, M., E. Kellezi and H. Hysi (2006). A Data-Driven Optimization Heuristic for Downside Risk Minimization. The Journal of Risk 8, 1-18, working paper available from SSRN.
Weblinks

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