門檻接受法 (Threshold Accepting)

最佳化方法

簡介

歷史

確定性搜尋

基本搜尋法

逐漸深入法

α-β 修剪

A* 搜尋法

隨機搜尋

單粒子隨機搜尋

貪婪演算法

爬山演算法

模擬退火法

禁忌搜尋法

多粒子隨機搜尋

演化策略

鳥群演算法

蟻群演算法

蜂群演算法

程式實作

基本搜尋法

爬山演算法

基因演算法

鳥群演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

門檻接受法(Threshold Accepting, TA)是Dueck & Scheuer[7]在1990年發表的一個啟發式最佳化方法,與模擬退火法 (SA) 一樣是由爬山演算法改良而來的。

TA 與 SA 都會允許爬山演算法向較差的解移動,而且都以溫度控制接受與否,溫度不斷下降的結果也都會讓兩者最達到穩定狀態,也就是退化成爬山演算法。

但TA 與 SA 不同的是,TA 使用一個門檻值作為接受與否的標準,而 SA 則是採用機率式的接受判斷法。

ThresholdAccepting.jpg

門檻函數

(1)
\begin{align} P^{TA} = \biggl\{ \substack {1 \quad if \Delta E \leq TH_k \\ \\ 0 \quad if \Delta E > TH_k } } \end{align}

門檻遞減

門檻值通常為一遞減函數,並隨著時間t 增加而下降

(2)
\begin{align} (TH_k)_{k=0}^{k-1} : t \rightarrow TH(t) \end{align}

演算法

參考文獻

  1. Dueck, G. and T. Scheuer, “Threshold Accepting: a general purpose optimization algorithm appeared superior to simulated annealing”, Journal of Computational Physics, Vol. 90, pp. 161-175, 1990
  2. Winker, P. (2001). Optimization Heuristics in Econometrics: Applications of Threshold Accepting. Wiley.
  3. 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.
  4. 楊智凱,「以門檻接受法改善TSP 及 VRP 路網成本」,國立交通大學土木工程研究所,碩士論文,1995。
  5. 韓復華、楊智凱,「門檻接受法在TSP 問題上之應用」, 運輸計劃季刊, Vol. 25,No. 2, pp. 163-188, 2006。
  6. 韓復華、楊智凱、卓裕仁,「應用門檻接受法求解車輛路線問題之研究」,運輸計劃季刊,Vol. 26, No. 2,pp. 253-280, 2007。

Facebook

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