禁忌搜尋演算法 (TABU Search)

最佳化方法

簡介

歷史

確定性搜尋

基本搜尋法

逐漸深入法

α-β 修剪

A* 搜尋法

隨機搜尋

單粒子隨機搜尋

貪婪演算法

爬山演算法

模擬退火法

禁忌搜尋法

多粒子隨機搜尋

演化策略

鳥群演算法

蟻群演算法

蜂群演算法

程式實作

基本搜尋法

爬山演算法

基因演算法

鳥群演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

Tabu Search 是一種輔助啟發法則,利用記錄先前之搜尋結果以避免陷入局部最佳解。

Tabu 是禁忌的意思,是 Polynesia 的 Tongan 語言中用來指稱某些不可碰觸的可怕事物之詞彙。

Tabu Search 利用短期記憶的結構,記錄前幾次的移動,以避免倒退或繞圈圈的情況,這個短期記憶就稱為禁忌串列 (Tabu List),禁忌串列越大,則陷入區域最佳解的機會越低。

但是過度的遵守禁忌,可能會導致錯失最佳解,因此必須搭配期望法則 (Aspiration Criteria),以便讓禁忌解有再度被選擇的機會,

Simple Tabu Search 演算法

Simple Tabu Search Algorithm
k = 1
s = initial solution
WHILE the stopping condition is not met DO 
    Identify N(s). (Neighbourhood set) 
    Identify T(s,k). (Tabu set) 
    Identify A(s,k). (Aspirant set) 
    N(s,k) = {N(s) - T(s,k)} + A(s,k)
    Choose the best s’  in  N(s,k)
    Memorize s’ if it improves the previous best known solution
    s = s’. 
    k = k + 1
END WHILE

長期記憶??

Facebook

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