過程模型化

1、禁忌搜索算法 （Tabu Search）吳浩博,,1 局部搜索2 禁忌搜索1 算法的主要思路2 禁忌搜索示例3 禁忌搜索的關(guān)鍵參數(shù)和操作3.1 變化因素3.2 禁忌表3.3 其他 4 禁忌搜索的實現(xiàn)與應(yīng)用4.1 圖結(jié)點染色,,1 局部搜索,,n個城市的對稱旅行商問題 簡單易行，但無法保證全局最優(yōu)性； 局部搜索主要依賴起點的選取和鄰域的結(jié)構(gòu)；

2、 為了得到好的解，可以比較不同的鄰域結(jié)構(gòu)和不同的初始點； 如果初始點的選擇足夠多， 總可以計算出全局最優(yōu)解。,局部搜索示例,,禁忌搜索算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優(yōu)的搜尋方法。在解決最優(yōu)問題上，一般區(qū)分為兩種方式：一種是傳統(tǒng)的方法，另一種方法則是一些啟發(fā)式搜索算法。,2 禁忌搜索,2.1 算法的

3、背景,2 禁忌搜索,,,2.1 算法的背景,,使用傳統(tǒng)的方法，我們必須對每一個問題都去設(shè)計一套算法，相當不方便，缺乏廣泛性，優(yōu)點在于我們可以證明算法的正確性，我們可以保證找到的答案是最優(yōu)的；而對于啟發(fā)式算法，針對不同的問題，我們可以套用同一個架構(gòu)來尋找答案，在這個過程中，我們只需要設(shè)計評價函數(shù)以及如何找到下一個可能解的函數(shù)等，所以啟發(fā)式算法的廣泛性比較高，但相對在準確度上就不一定能夠達到最優(yōu)，但是在實際問題中啟發(fā)式算法那有著更廣泛的

4、應(yīng)用。,禁忌搜索是一種亞啟發(fā)式隨機搜索算法，它從一個初始可行解出發(fā)，選擇一系列的特定搜索方向(移動)作為試探，選擇實現(xiàn)讓特定的目標函數(shù)值變化最多的移動。為了避免陷入局部最優(yōu)解，TS搜索中采用了一種靈活的“記憶”技術(shù)，對已經(jīng)進行的優(yōu)化過程進行記錄和選擇，指導(dǎo)下一步的搜索方向。 TS是人工智能的一種體現(xiàn)，是局部領(lǐng)域搜索的一種擴展。禁忌搜索是在領(lǐng)域搜索的基礎(chǔ)上，通過設(shè)置禁忌表來禁忌一些已經(jīng)歷的操作，并利用藐視準則來獎勵一些優(yōu)良狀態(tài)，

5、其中涉及鄰域 、禁忌表、禁忌長度、候選解、藐視準則等影響禁忌搜索算法性能的關(guān)鍵因素。迄今為止，TS算法在組合優(yōu)化等計算機領(lǐng)域取得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢。,2 禁忌搜索,2.1 算法的背景,2 禁忌搜索,,四城市非對稱TSP問題 初始解x0=(ABCD)，f(x0)=4，鄰域映射為兩個城市順序?qū)Q的2－opt，始、終點都是A城市。,2.2 禁忌搜索

6、示例,2 禁忌搜索,,四城市非對稱TSP問題 第1步 解的形式 禁忌對象及長度 候選解 f(x0)=4,2.2 禁忌搜索示例,?,2 禁忌搜索,,四城市非對稱TSP問題 第2步 解的形式 禁忌對象及長度 候選解 f(x1)=4.5,2.2 禁忌搜索示例,?,T,2

7、禁忌搜索,,四城市非對稱TSP問題 第3步 解的形式 禁忌對象及長度 候選解 f(x2)=3.5,2.2 禁忌搜索示例,?,T,T,2 禁忌搜索,,四城市非對稱TSP問題 第4步 解的形式 禁忌對象及長度 候選解 f(x3)=7.5 禁忌長度的選取,2.2

8、禁忌搜索示例,T,T,T,2 禁忌搜索,,四城市非對稱TSP問題 第4步（如果減小禁忌長度） 解的形式 禁忌對象及長度 候選解 f(x3)=7.5,2.2 禁忌搜索示例,?,T,T,2 禁忌搜索,,四城市非對稱TSP問題 第5步 解的形式 禁忌對象及長度 候選解 f(x

9、4)=4.5,2 禁忌搜索示例,?,T,T,,TS算法 框架,(1)是否有其他形式的候選集？(2)禁忌的長度如何確定？如果在算法中記憶下搜索到的當前最優(yōu)解，極端的兩種情況是：一是將所有的對換個數(shù)作為禁忌長度，此時等價于將候選集中的所有的對換遍歷；另外則取為1，這等價于局部搜索算法。(3)是否有評價值的其他替代形式？有時計算目標值的工作量較大，或無法接受計算目標值所花費的時間，于是需要其他的方法。(4)被禁的對換能否再一次解禁？

10、有這樣的直觀現(xiàn)象，當搜索到一個局部最優(yōu)解后，它鄰域中的其他狀態(tài)都被禁，我們是否解禁一些狀態(tài)以便跳出局部最優(yōu)？解禁的功能就是為了獲得更大的搜索范圍，以免陷入局部最優(yōu)。(5)如何利用更多的信息？在禁忌搜索算法中，還可記錄其他一些信息。如一個被禁對象（交換）被禁的次數(shù)，評價值變化的大小等。(6)終止原則，即一個算法停止的條件，怎樣給出？,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌表的主要指標（兩項指標） 禁忌對象：禁忌表中被禁的那些

11、變化元素 禁忌長度：禁忌的步數(shù)狀態(tài)變化（三種變化） 解的簡單變化 解向量分量的變化 目標值變化,3.1 變化因素,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,解的簡單變化,3.1 變化因素,這種變化最為簡單，如從（ABCDE）變到（ABCED）,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,向量分量的變化 設(shè)原有的解向量為(x1, …, xi-1, xi, xi+1, …, xn)，向量分量的最基

12、本變化為 (x1, …, xi-1, xi, xi+1,…, xn)→(x1, …, xi-1, yi, xi+1,…, xn) 即只有第i個分量發(fā)生變化。 也包含多個分量變化的情形。,3.1 變化因素,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,目標值的變化 目標值的變化隱含著解集合的變化。,3.1 變化因素,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況1：禁忌對象

13、為簡單的解變化 禁忌長度為4，從2－opt鄰域中選出最佳的5個解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況1：禁忌對象為簡單的解變化 第1步—— xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}

14、 Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。,3.2 禁忌表,xnext=(ACBDE),,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況1：禁忌對象為簡單的解變化 第2步—— xnow=(ACBDE)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)} Can

15、_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。,3.2 禁忌表,xnext=(ACBED),,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況1：禁忌對象為簡單的解變化 第3步—— xnow=(ACBED)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43) ，(ACBED;43)}

16、 Can_N(xnow)={(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)}。,3.2 禁忌表,xnext=(ABCED),,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況1：禁忌對象為簡單的解變化 第4步—— xnow=(ABCED)，f(xnow)=44，H={(ABCDE;45)，(ACBDE;43) ，(A

17、CBED;43) ，(ABCED;44)} Can_N(xnow)={(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)}。,3.2 禁忌表,xnext=(AECBD)此時H已達到4個解，新選入的解代替最早被禁的解,,,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況1：禁忌對象為簡單的解變化 第5步—— xnow=(

18、AECBD)，f(xnow)=44，H={(ACBDE;43) ，(ACBED;43) ，(ABCED;44) ，(AECBD;44)} Can_N(xnow)={(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)}。,3.2 禁忌表,xnext=(AEDBC),,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況2：禁忌對象為分量變化

19、 禁忌長度為3，從2－opt鄰域中選出最佳的5個解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況2：禁忌對象為分量變化 第1步—— xnow=(ABCDE)，f(xnow)=45，H=Φ Can_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AE

20、CDB;60)，(ABEDC;59)，(ABCED;44)}。,3.2 禁忌表,xnext=(ACBDE)由于H為空集，從候選集中選最好的一個，它是B與C的對換構(gòu)成,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況2：禁忌對象為分量變化 第2步—— xnow=(ACBDE)，f(xnow)=43，H={(B,C)} Can_N(xnow)={(ACBED;43)，(ADBCE;

21、44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}。,3.2 禁忌表,xnext=(ACBED),,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況2：禁忌對象為分量變化 第3步—— xnow=(ACBED)，f(xnow)=43，H={(B,C)，(D,E)} Can_N(xnow)={(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(

22、ADBEC;58)，(ACEBD;58)}。,3.2 禁忌表,xnext=(AEBCD)可以看出，情況2 比情況1禁忌的范圍要更大一些,,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情況3：禁忌對象為目標值變化 禁忌長度為3，從2－opt鄰域中選出最佳的5個解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參

23、數(shù)和操作,,禁忌對象的選取 情況3：禁忌對象為目標值變化 第1步—— xnow=(ABCDE)，f(xnow)=45，H={45} Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。,3.2 禁忌表,xnext=(ACBDE),,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 情

24、況3：禁忌對象為目標值變化 第2步—— xnow=(ACBDE)，f(xnow)=43，H={45，43} Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。,3.2 禁忌表,xnext=(ADBCE)這種方法禁忌的范圍更大,,,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對象的選取 解的簡單變化比

25、解的分量變化和目標值變化的受禁范圍要小，可能造成計算時間的增加，但也給予了較大的搜索范圍； 解分量的變化和目標值變化的禁忌范圍大，減少了計算時間，可能導(dǎo)致陷在局部最優(yōu)點。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌長度的選取 禁忌長度過短，一旦陷入局部最優(yōu)點，出現(xiàn)循環(huán)無法跳出； 禁忌長度過長，造成計算時間較大，也可能造成計算無法繼續(xù)下去。,3

26、.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,特赦（藐視）原則 （1）基于評價值的規(guī)則，若出現(xiàn)一個解的目標值好于前面任何一個最佳候選解，可特赦； （2）基于最小錯誤的規(guī)則，若所有對象都被禁忌，特赦一個評價值最小的解；,3.2 禁忌表,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,候選集合的確定 （1）從鄰域中選擇若干目標值最佳的鄰居入選；（2）隨機選取。,3.3 其他,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,評

27、價函數(shù) （1）直接評價函數(shù)，通過目標函數(shù)的運算得到評價函數(shù)； （2）間接評價函數(shù)，構(gòu)造其他評價函數(shù)替代目標函數(shù)，應(yīng)反映目標函數(shù)的特性，減少計算復(fù)雜性。,3.3 其他,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,記憶頻率信息 根據(jù)記憶的頻率信息（禁忌次數(shù)等）來控制禁忌參數(shù)（禁忌長度等）。 例如： 如果一個元素或序列重復(fù)出現(xiàn)或目標值變化很小，可增加禁忌長度以避開循環(huán)； 如果一個最佳目標值出

28、現(xiàn)頻率很高，則可以終止計算認為已達到最優(yōu)值。,3.3 其他,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,終止規(guī)則 （1）確定步數(shù)終止，優(yōu)點是易于操作和控制時間，但無法保證解的效果，應(yīng)記錄當前最優(yōu)解； （2）頻率控制原則，當某一個解、目標值或元素序列的頻率超過一個給定值時，終止計算； （3）目標控制原則，如果在一個給定步數(shù)內(nèi)，當前最優(yōu)值沒有變化，同規(guī)則2，可終止計算。,3.3 其他,,禁忌算法的特征由禁忌對象和長度

29、、候選集和評價函數(shù)、停止規(guī)則和一些計算信息組成綜合上面的討論，給出了他們的選取禁忌對象，禁忌長度，特赦規(guī)則，候選集合，評價函數(shù)，終止規(guī)則,3 禁忌搜索的關(guān)鍵參數(shù)和操作,3.3 其他,禁忌搜索算法：step1 選定一個初始解xnow及給以禁忌表H等于空集；step2 若滿足停止規(guī)則，停止計算；否則，在xnow的鄰域N（H，xnow）中選出滿足禁忌要求的候選集Can_N(xnow)；在Can_N(xnow)中選一個評價值最佳的

30、解xnext，xnow：=xnest；更新歷史記錄H，重復(fù)step2. 禁忌算法的step2中，xnow的鄰域N（H，xnow）中滿足禁忌要求的元素包含兩類：一類是那些沒有被禁忌的元素，另一類是可以被解除禁忌的元素。,舉一個參考文獻4中的例子：給定一個無向圖G，其頂點集V={1,2，···，n}，E是邊集，求最少用幾種顏色k，使不同顏色的點間沒有邊相連。求最小的k，使（V1，

31、3;··Vk）是V的一個劃分。,4 禁忌搜索的應(yīng)用和實現(xiàn),4.1 圖結(jié)點染色,總結(jié),與傳統(tǒng)的優(yōu)化算法相比，TS算法的主要特點是： 1．從移動規(guī)則看，每次只與最優(yōu)點比較，而不與經(jīng)過點比較，故可以爬出局部最優(yōu)。 2．選優(yōu)規(guī)則始終保持曾經(jīng)達到的最優(yōu)點，所以即使離開了全局最優(yōu)點也不會失去全局最優(yōu)性。 3．終止規(guī)則不以達到局部最優(yōu)為終止規(guī)則，而以最大迭代次數(shù)、出現(xiàn)頻率限制或者目標值偏離成都為

32、終止規(guī)則禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優(yōu)解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。因而在計算搜索領(lǐng)域有著廣泛應(yīng)用。,參考文獻,維基百科http://en.wikipedia.org/wiki/Tabu_search現(xiàn)代優(yōu)化計算方法 清華大學出版社陳麗 禁忌搜索算法的研究及其在TSP的應(yīng)用 2010Hertz A, de Werra D.The Tabu Search