## Author

## 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.

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]).

# 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 |