禁忌搜尋

禁忌搜尋

禁忌搜尋(Tabu Search,TS,又稱禁忌搜尋法)是一種現代啟發式算法,由美國科羅拉多大學教授Fred Glover在1986年左右提出的,是一個用來跳脫局部最優解的搜尋方法。其先創立一個初始化的方案;基於此,算法“移動”到一相鄰的方案。經過許多連續的移動過程,提高解的質量。

基本介紹

迄今為止,TS算法在組合最佳化、生產調度、機器學習、電路設計和神經網路等領域取得了很大的成功,近年來又在函式全局最佳化方面得到較多的研究,並大有發展的趨勢。

針對局部鄰域搜尋,為了實現全局最佳化,可嘗試的途徑有:以可控性機率接受劣解來逃逸局部極小,如模擬退火算法;擴大鄰域搜尋結構,如TSP的2opt擴展到k-opt;多點並行搜尋,如進化計算;變結構鄰域搜尋( Mladenovic et al,1997);另外,就是採用TS的禁忌策略儘量避免迂迴搜尋,它是一種確定性的局部極小突跳策略。

禁忌搜尋是人工智慧的一種體現,是局部鄰域搜尋的一種擴展。禁忌搜尋最重要的思想是標記對應已搜尋的局部最優解的一些對象,並在進一步的疊代搜尋中儘量避開這些對象(而不是絕對禁止循環),從而保證對不同的有效搜尋途徑的探索。禁忌搜尋涉及到鄰域(neighborhood)、禁忌表(tabu list)、禁忌長度(tabu length)、候選解(candidate)、藐視準則(aspiration criterion)等概念。  

示例

組合最佳化是TS算法套用最多的領域。置換問題,如TSP、調度問題等,是一大批組合最佳化問題的典型代表,在此用它來解釋簡單的禁忌搜尋算法的思想和操作。對於 n元素的置換問題,其所有排列狀態數為n!,當n較大時搜尋空間的大小將是天文數字,而禁忌搜尋則希望僅通過探索少數解來得到滿意的最佳化解。

首先,對置換問題定義一種鄰域搜尋結構,如互換操作(SWAP),即隨機交換兩個點的位置,則每個狀態的鄰域解有Cn2=n(n一1)/2個。稱從一個狀態轉移到其鄰域中的另一個狀態為一次移動(move),顯然每次移動將導致適配值(反比於目標函式值)的變化。其次,我們採用一個存儲結構來區分移動的屬性,即是否為禁忌“對象”在以下示例中:考慮7元素的置換問題,並用每一狀態的相應21個鄰域解中最優的5次移動(對應最佳的5個適配值)作為候選解;為一定程度上防止迂迴搜尋,每個被採納的移動在禁忌表中將滯留3步(即禁忌長度),即將移動在以下連續3步搜尋中將被視為禁忌對象;需要指出的是,由於當前的禁忌對象對應狀態的適配值可能很好,因此在算法中設定判斷,若禁忌對象對應的適配值優於“ best so far”狀態,則無視其禁忌屬性而仍採納其為當前選擇,也就是通常所說的藐視準則(或稱特赦準則)。

簡單的禁忌搜尋是在領域搜尋的基礎上,通過設定禁忌表來禁忌一些已經歷的操作,並利用藐視準則來獎勵一些優良狀態,其中領域結構、候選解、禁忌長度、禁忌對象、藐視準則、終止準則等是影響禁忌搜尋算法性能的關鍵。需要指出的是:

(1)由於TS是局部領域搜尋的一種擴充,因此領域結構的設計很關鍵,它決定了當前解的領域解的產生形式和數目,以及各個解之間的關係。

(2)出於改善算法的最佳化時間性能的考慮,若領域結構決定了大量的領域解(尤其對大規模問題,如TSP的SWAP操作將產生Cn2個領域解),則可以僅嘗試部分互換的結果,而候選解也僅取其中的少量最佳狀態。

(3)禁忌長度是一個很重要的關鍵參數,它決定禁忌對象的任期,其大小直接進而影響整個算法的搜尋進程和行為。同時,以上示例中,禁忌表中禁忌對象的替換是採用FIFO方式(不考慮藐視準則的作用),當然也可以採用其他方式,甚至是動態自適應的方式。

(4)藐視準則的設定是算法避免遺失優良狀態,激勵對優良狀態的局部搜尋,進而實現全局最佳化的關鍵步驟。

(5)對於非禁忌候選狀態,算法無視它與當前狀態的適配值的優劣關係,僅考慮它們中間的最佳狀態為下一步決策,如此可實現對局部極小的突跳(是一種確定性策略)。

(6)為了使算法具有優良的最佳化性能或時間性能,必須設定一個合理的終止準則來結束整個搜尋過程。

此外,在許多場合禁忌對象的被禁次數(frequency)也被用於指導搜尋,以取得更大的搜尋空間。禁忌次數越高,通常可認為出現循環搜尋的機率越大。  

算法流程

算法

禁忌搜尋 禁忌搜尋

給以禁忌表H= 並選定一個初始解x;滿足停止規則時,停止計算,輸出結果;否則,在x的鄰域N(x)中選出滿足不受禁忌的候選集Can_N(x);在Can_N(x)中選一個評價值最佳的解x1,x=x1;更新歷史記錄H,重複STEP2。

注意事項

不受禁忌的候選集包括兩種,一種是那些沒有被禁忌的元素,另一種是可以被解除禁忌的元素。  

相關詞條

相關搜尋

熱門詞條

聯絡我們