-禁忌搜索課件

1、智能優(yōu)化方法AI-Based Optimization MethodsBy Professor Dingwei WangNortheastern UniversityChina 2004第1頁，共46頁。1第四章禁忌搜索第2頁，共46頁。2第四章 禁忌搜索（ Tabu Search ）一.導(dǎo)言二.TS的基本原理及步驟三.TS的算法步驟四.TS可以克服局優(yōu)的分析五.TS舉例六.TS的中、長期表的使用七.TS表的應(yīng)用舉例八.學(xué)習(xí)TS的幾點體會第3頁，共46頁。3TS的提出1977年F.Glover提出TS ，90年代初得到廣泛重視一.導(dǎo)言（1）第4頁，共46頁。4TS的基本思想避免在搜索過程中的循

2、環(huán)只進(jìn)不退的原則用Tabu表鎖住退路不以局部最優(yōu)作為停止準(zhǔn)則鄰域選優(yōu)的規(guī)則模擬了人類的記憶功能找過的地方都記下來，不再找第二次一.導(dǎo)言（2）第5頁，共46頁。5TS的要素構(gòu)成禁忌表(Tabu List)渴望水平函數(shù)(Aspiration Level Function)移動規(guī)則鄰域選優(yōu)選優(yōu)規(guī)則保持歷史上的最優(yōu)解停止準(zhǔn)則與GA相似一.導(dǎo)言（3）第6頁，共46頁。6問題的描述及鄰域的概念TS僅用于離散優(yōu)化，排斥實優(yōu)化二. TS的基本原理及步驟（1）第7頁，共46頁。7二. TS的基本原理及步驟（2）第8頁，共46頁。8鄰域舉例：X=0,1,0,0,1,0,0u=1,d=0,0,1,0,0,0,0注意

3、：移動的意義是靈活的，目的是便于搜索。如：排序問題中一次換位可稱為一次移動，還可以定義為選一個切點，兩部分作交叉運算。二. TS的基本原理及步驟（3）第9頁，共46頁。9禁忌表的概念禁忌表的作用：防止搜索出現(xiàn)循環(huán)記錄前若干步走過的點、方向或目標(biāo)值，禁止返回表是動態(tài)更新的把最新的解記入，最老的解從表中釋放(解禁)。表的長度稱為Tabu-Size，一般取5、 7 、11，表長越大分散性越好。二. TS的基本原理及步驟（4）第10頁，共46頁。10鄰域搜索規(guī)則每一步移動到不在T表中的鄰域中的最優(yōu)解，即若 ，則令則本次移動到最優(yōu)解鄰域搜索規(guī)則的作用：保證TS的優(yōu)良局部搜索功能二. TS的基本原理及步驟

4、（5）第11頁，共46頁。11渴望水平函數(shù)是一個取決于 和 的值，若有則 是不受T表限制。即使 ，仍可取 渴望水平，一般為歷史上曾經(jīng)達(dá)到的最好目標(biāo)值。二. TS的基本原理及步驟（6）第12頁，共46頁。12步驟：選一個初始點 ， ，令 ， ，迭代指標(biāo) ；若停止，否則令，若(其中NG為最大迭代數(shù))停止；注：表示非正常終止，造成的原因：鄰域小，T表長。正常設(shè)置為(T表長度0的數(shù)減1；對數(shù)組上半部分，給新發(fā)生的移動所對應(yīng)的數(shù)組元加上Tabu-Size;T表的下半部分，用來記頻數(shù)，每次(i,j)交換(ij)，對應(yīng)的(j,i)+1)來記憶頻數(shù)。六.TS的中、長期表的使用（4）第30頁，共46頁。30頻數(shù)

5、表的優(yōu)點：同一數(shù)組作為T表和頻數(shù)表共同使用，方便操作又節(jié)省了時間。六.TS的中、長期表的使用（5）第31頁，共46頁。31頻數(shù)表：Tabu-Size=7六.TS的中、長期表的使用（6）T表11，221，53第32頁，共46頁。32長期表的使用多階段TS算法長期表的作用長期表用來記錄每個階段的初始解，在下一階段產(chǎn)生初始解時，使之盡可能與已有的初始解有較大的距離。六.TS的中、長期表的使用（7）第33頁，共46頁。33圖示六.TS的中、長期表的使用（8）第34頁，共46頁。34函數(shù)表達(dá)式長期表的TS有很好的性能。六.TS的中、長期表的使用（9）第35頁，共46頁。35問題的來源1994年Icmel

6、l發(fā)表的論文，C&OR V21,No.8Computer and Operations Research問題：帶有折扣資金流的約束網(wǎng)絡(luò)計劃問題(資源受限)例題見下頁七.TS表的應(yīng)用舉例（1）第36頁，共46頁。36n個工作組成的項目,求極小化折扣資金流的計劃七.TS表的應(yīng)用舉例（2）第37頁，共46頁。37H=(1,3),(1,4),(2,5),(2,6),(3,7),(5,7),(4,8),(6,8)解：變量定義：七.TS表的應(yīng)用舉例（3）SE12687345第38頁，共46頁。38問題模型： 式 式 式 式 式脫期罰項n是最后完成的工作脫期懲罰因子第39頁，共46頁。39數(shù)學(xué)模型的解釋：式

7、折扣資金；式每個工作只能完成1次;式資源約束；式工作i沒做完不允許做工作j仔細(xì)思考，以上數(shù)學(xué)表達(dá)式的下標(biāo)設(shè)計是非常精妙的尤其是式資源約束。七.TS表的應(yīng)用舉例（5）第40頁，共46頁。40將以上模型簡化七.TS表的應(yīng)用舉例（6）第41頁，共46頁。41該式表示i在j之前這一項表示條件取和注：對于條件取和、 ，常規(guī)的優(yōu)化方法不能計算，但可用TS求解 。第42頁，共46頁。42編碼方式：自然數(shù)編碼狀態(tài)：鄰域定義：鄰域大?。?n七.TS表的應(yīng)用舉例（8）第43頁，共46頁。43鄰域搜索規(guī)則： 中有可行解時，取可行解中目標(biāo)值最小的鄰域解； 中無可行解時，取約束違反量最小的鄰域解七.TS表的應(yīng)用舉例（9）第44頁，共46頁。44TS的記憶功能短、中、長期表要靈活使用TS相對于GA,SA是更快的算法，局域搜索能力強，但全局搜索能力較弱；改善TS的全局搜索能力，提高