過程模型化

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

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

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

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

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

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

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

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

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

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

11、變化元素 禁忌長(zhǎng)度：禁忌的步數(shù)狀態(tài)變化（三種變化） 解的簡(jiǎn)單變化 解向量分量的變化 目標(biāo)值變化,3.1 變化因素,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,解的簡(jiǎn)單變化,3.1 變化因素,這種變化最為簡(jiǎn)單，如從（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個(gè)分量發(fā)生變化。 也包含多個(gè)分量變化的情形。,3.1 變化因素,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,目標(biāo)值的變化 目標(biāo)值的變化隱含著解集合的變化。,3.1 變化因素,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對(duì)象的選取 情況1：禁忌對(duì)象

13、為簡(jiǎn)單的解變化 禁忌長(zhǎng)度為4，從2－opt鄰域中選出最佳的5個(gè)解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對(duì)象的選取 情況1：禁忌對(duì)象為簡(jiǎn)單的解變化 第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ù)和操作,,禁忌對(duì)象的選取 情況1：禁忌對(duì)象為簡(jiǎn)單的解變化 第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ù)和操作,,禁忌對(duì)象的選取 情況1：禁忌對(duì)象為簡(jiǎn)單的解變化 第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ù)和操作,,禁忌對(duì)象的選取 情況1：禁忌對(duì)象為簡(jiǎn)單的解變化 第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)此時(shí)H已達(dá)到4個(gè)解，新選入的解代替最早被禁的解,,,,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對(duì)象的選取 情況1：禁忌對(duì)象為簡(jiǎn)單的解變化 第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ù)和操作,,禁忌對(duì)象的選取 情況2：禁忌對(duì)象為分量變化

19、 禁忌長(zhǎng)度為3，從2－opt鄰域中選出最佳的5個(gè)解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對(duì)象的選取 情況2：禁忌對(duì)象為分量變化 第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為空集，從候選集中選最好的一個(gè)，它是B與C的對(duì)換構(gòu)成,,3 禁忌搜索的關(guān)鍵參數(shù)和操作,,禁忌對(duì)象的選取 情況2：禁忌對(duì)象為分量變化 第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ù)和操作,,禁忌對(duì)象的選取 情況2：禁忌對(duì)象為分量變化 第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ù)和操作,,禁忌對(duì)象的選取 情況3：禁忌對(duì)象為目標(biāo)值變化 禁忌長(zhǎng)度為3，從2－opt鄰域中選出最佳的5個(gè)解組成候選集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。,3.2 禁忌表,3 禁忌搜索的關(guān)鍵參

23、數(shù)和操作,,禁忌對(duì)象的選取 情況3：禁忌對(duì)象為目標(biāo)值變化 第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ù)和操作,,禁忌對(duì)象的選取 情

24、況3：禁忌對(duì)象為目標(biāo)值變化 第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ù)和操作,,禁忌對(duì)象的選取 解的簡(jiǎn)單變化比

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

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

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

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

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

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

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

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