禁忌搜索算法.ppt

《禁忌搜索算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、禁忌搜索TabuSearch禁忌搜索(TabuSearch或TabooSearch，簡(jiǎn)稱TS)的思想最早由Glover(1986)提出，它是對(duì)局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對(duì)人類智力過程的一種模擬。禁忌搜索概述禁忌搜索概述TS算法通過引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。相對(duì)于模擬退火和遺傳算法，TS是又一種搜索特點(diǎn)不同的算法。迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計(jì)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取

2、得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢(shì)。特點(diǎn)Neighborhoodsearch+memoryNeighborhoodsearchMemoryRecordthesearchhistoryForbidcyclingsearchTabuSearch3的鄰域搜索陷入循環(huán)1的鄰域12的鄰域24的鄰域43在鄰域中找到最好的解加入禁忌表，避免陷入循環(huán)禁忌表長(zhǎng)度為3：{①,②,③}規(guī)則：不得接受與禁忌表中相同的解禁忌表的變化：第一步搜索時(shí){}第二步搜索時(shí){①}第三步搜索時(shí){①,②,}第四步搜索時(shí){①,②

3、,③}避免循環(huán)的原理：當(dāng)前解為④時(shí)，其領(lǐng)域中最好的解為①，原本下一步應(yīng)為①，但其與禁忌表中的元素相同，所以選擇次好的解⑤，從而避免死循環(huán)3的鄰域1的鄰域12的鄰域24的鄰域435禁忌表的更新更新原則：先進(jìn)先出{①,②,③}{②,③,④}{③,④,⑤}….禁忌表中元素禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一個(gè)生成相鄰解的動(dòng)作等等完整解：{12345,13245,31245}生成相鄰解的操作（如交換的動(dòng)作）：{32,31}從12345開始，取3出來，插入1245每個(gè)位置前面禁忌表長(zhǎng)度太短：計(jì)算速度快，

4、但容易陷入死循環(huán)太長(zhǎng)：計(jì)算速度慢在搜索過程中，禁忌表長(zhǎng)度設(shè)為固定在搜索過程中，禁忌表長(zhǎng)度可動(dòng)態(tài)變化禁忌表長(zhǎng)度：5—10如果找到了一個(gè)新的解比當(dāng)前記錄的最好解還要好，那么即使從當(dāng)前得到這個(gè)新的解被tabulist禁止，仍然接受這個(gè)新的解，并更新tabulist.即tabulist對(duì)這個(gè)解沒有禁止作用假設(shè)記錄生成相鄰解的方法，Tabulist={②,③,④},下一步采用②方法生成了迄今為止最好的解，仍然接受這個(gè)，更新Tabulist={②,③,②},藐視準(zhǔn)則（Aspirationcriterion）分散搜索：是為了對(duì)整個(gè)解的空間

5、進(jìn)行更廣泛的覆蓋，而不是僅僅局限在某個(gè)局部的區(qū)域。分散搜索（Diversification）和集中搜索（Intensification）策略無鄰域的搜索有鄰域的搜索有鄰域的搜索&分散搜索策略集中搜索：如果當(dāng)前搜索區(qū)域內(nèi)發(fā)現(xiàn)了比較好的解，如果進(jìn)一步對(duì)當(dāng)前區(qū)域進(jìn)行更集中的搜索，那么可能會(huì)發(fā)現(xiàn)更多更好的解。分散搜索（Diversification）和集中搜索（Intensification）策略分散搜索策略（Diversificationstrategy）在當(dāng)前搜索區(qū)域內(nèi)進(jìn)行了一定次數(shù)的搜索了之后（如25次），若不能發(fā)現(xiàn)更好的解，

6、那么就執(zhí)行分散搜索策略。把tabulist清空，然后從一個(gè)新的初始解開始搜索。集中搜索：如果最好解的記錄被更新，那么就執(zhí)行集中搜索策略，即清空tabulist.這樣可以在當(dāng)前區(qū)域進(jìn)行更自由的搜索。要設(shè)計(jì)一個(gè)禁忌搜索算法，需要確定以下環(huán)節(jié)1)初始解和適配值函數(shù)（目標(biāo)函數(shù)）；2)鄰域結(jié)構(gòu)(如何生成相鄰解)和禁忌對(duì)象(禁忌表中的元素)；3)候選解選擇；4)禁忌表及其長(zhǎng)度；5)藐視準(zhǔn)則6)集中搜索和分散搜索策略7)終止準(zhǔn)則。’變量定義：n＝搜索次數(shù)N＝搜索N次，程序結(jié)束NI＝連續(xù)沒有找到更好解的次數(shù)M＝連續(xù)M次沒有找到更好解，執(zhí)行分

7、散搜索策略BS＝找到的最好的解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的候選解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換BS;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n

8、0211201383617134695156Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu