




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領
文檔簡介
禁忌搜索
TabuSearch
禁忌搜索(TabuSearch或TabooSearch,簡稱TS)的思想最早由Glover(1986)提出,它是對局部鄰域搜索的一種擴展,是一種全局逐步尋優(yōu)算法,是對人類智力過程的一種模擬。禁忌搜索概述禁忌搜索概述TS算法通過引入一個靈活的存儲結(jié)構(gòu)和相應的禁忌準則來避免迂回搜索,并通過藐視準則來赦免一些被禁忌的優(yōu)良狀態(tài),進而保證多樣化的有效探索以最終實現(xiàn)全局優(yōu)化。相對于模擬退火和遺傳算法,TS是又一種搜索特點不同的算法。迄今為止,TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機器學習、電路設計和神經(jīng)網(wǎng)絡等領域取得了很大的成功,近年來又在函數(shù)全局優(yōu)化方面得到較多的研究,并大有發(fā)展的趨勢。特點Neighborhoodsearch+memoryNeighborhoodsearchMemoryRecordthesearchhistoryForbidcyclingsearchTabuSearch3的鄰域搜索陷入循環(huán)1的鄰域12的鄰域24的鄰域43在鄰域中找到最好的解加入禁忌表,避免陷入循環(huán)禁忌表長度為3:{①,②,③}規(guī)則:不得接受與禁忌表中相同的解禁忌表的變化: 第一步搜索時{}第二步搜索時{①}第三步搜索時{①,②,}第四步搜索時{①,②,③}避免循環(huán)的原理:當前解為④時,其領域中最好的解為①,原本下一步應為①,但其與禁忌表中的元素相同,所以選擇次好的解⑤,從而避免死循環(huán)3的鄰域1的鄰域12的鄰域24的鄰域435禁忌表的更新更新原則:先進先出{①,②,③}{②,③,④}{③,④,⑤}….禁忌表中元素禁忌表中元素的可以是完整的解,可以是完整解的一部分,也可以是采取的一個生成相鄰解的動作等等完整解:{12345,13245,31245}生成相鄰解的操作(如交換的動作):{32,31}從12345開始,取3出來,插入1245每個位置前面禁忌表長度太短:計算速度快,但容易陷入死循環(huán)太長:計算速度慢在搜索過程中,禁忌表長度設為固定在搜索過程中,禁忌表長度可動態(tài)變化禁忌表長度:5—10如果找到了一個新的解比當前記錄的最好解還要好,那么即使從當前得到這個新的解被tabulist禁止,仍然接受這個新的解,并更新tabulist.即tabulist對這個解沒有禁止作用假設記錄生成相鄰解的方法,Tabulist={②,③,④},下一步采用②方法生成了迄今為止最好的解,仍然接受這個,更新Tabulist={②,③,②},藐視準則(Aspirationcriterion)分散搜索:是為了對整個解的空間進行更廣泛的覆蓋,而不是僅僅局限在某個局部的區(qū)域。分散搜索(Diversification)和集中搜索(Intensification)策略無鄰域的搜索有鄰域的搜索有鄰域的搜索&分散搜索策略集中搜索:如果當前搜索區(qū)域內(nèi)發(fā)現(xiàn)了比較好的解,如果進一步對當前區(qū)域進行更集中的搜索,那么可能會發(fā)現(xiàn)更多更好的解。分散搜索(Diversification)和集中搜索(Intensification)策略分散搜索策略(Diversificationstrategy)在當前搜索區(qū)域內(nèi)進行了一定次數(shù)的搜索了之后(如25次),若不能發(fā)現(xiàn)更好的解,那么就執(zhí)行分散搜索策略。把tabulist清空,然后從一個新的初始解開始搜索。集中搜索:如果最好解的記錄被更新,那么就執(zhí)行集中搜索策略,即清空tabulist.這樣可以在當前區(qū)域進行更自由的搜索。要設計一個禁忌搜索算法,需要確定以下環(huán)節(jié)1)初始解和適配值函數(shù)(目標函數(shù));2)鄰域結(jié)構(gòu)(如何生成相鄰解)和禁忌對象(禁忌表中的元素);3)候選解選擇;4)禁忌表及其長度;5)藐視準則6)集中搜索和分散搜索策略7)終止準則?!兞慷x:n=搜索次數(shù)N=搜索N次,程序結(jié)束NI=連續(xù)沒有找到更好解的次數(shù)M=連續(xù)M次沒有找到更好解,執(zhí)行分散搜索策略BS=找到的最好的解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的候選解比BS好?接受新的解用新的解替換當前解用新的解替換BS;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否TSP算例Citytocity12345611247910211201383617134695156Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否Tabulist初始化(清空)設M,N的值
Tabulist{},長度為2。記錄從當前解生成新的解的過程中,產(chǎn)生的新的相鄰關(guān)系M=2N=4Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否求得初始解BS=初始解
SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否求得一系列候選解,并按優(yōu)劣排序SequenceThelengthoftheroute4132563014325635134256381325464013256445用插值的方法求得候選解:生成隨機數(shù)r=[1,6],選取第r個位置上的元素,插入到其余位置前面隨機數(shù)=4Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute41325630BSSequenceThelengthoftheroute13245628接受最好的候選解,并替換當前解Tabulist{41,},NI=1,n=1當前解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否求得一系列候選解,并按優(yōu)劣排序SequenceThelengthoftheroute1432562943125633432156354325163643256138用插值的方法求得候選解隨機數(shù)=2Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563014325629BSSequenceThelengthoftheroute13245628考慮最好的候選解Tabulist{41,},NI=1,n=1新生成相鄰關(guān)系(14),isTabu!Rejectit當前解候選解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563043125633BSSequenceThelengthoftheroute13245628考慮下一個最好的候選解Tabulist{41,},NI=1,n=1新生成相鄰關(guān)系(3,1),isnotTabu!acceptit當前解候選解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否更新當前解、最好解、tabulist
及相關(guān)參數(shù)SequenceThelengthoftheroute43125633BSSequenceThelengthoftheroute13245628Tabulist{31,41},NI=2,n=2當前解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否分散搜索(diversification)SequenceThelengthoftheroute45326145BSSequenceThelengthoftheroute13245628Tabulist{},NI=0,n=2隨機生產(chǎn)新的當前解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否求得一系列候選解,并按優(yōu)劣排序SequenceThelengthoftheroute6453212846532132456321344536213645321637用插值的方法求得候選解隨機數(shù)=5Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute64532128BSSequenceThelengthoftheroute13245628接受最好的候選解,并替換當前解Tabulist{64,},NI=1,n=3當前解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否求得一系列候選解,并按優(yōu)劣排序SequenceThelengthoftheroute4653212565432127653421196532413565321446用插值的方法求得候選解隨機數(shù)=2Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute6453212846532125BSSequenceThelengthoftheroute13245628考慮最好的候選解Tabulist{64,}新生成相鄰關(guān)系(4,6),isTabu!However,itisbetterthanBS.Thus,applytheaspirationstrategy,acceptit!當前解候選解判斷是否為tabu,決定接受與否SequenceThelengthoftheroute46532125BSSequenceThelengthoftheroute46532125應用藐視法則,更新BS、當前解,及NI、n清空Tabulist{},NI=0,n=4當前解Tabulist初始化(清空)設M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解,并按優(yōu)劣排序最好的新解比BS好?接受新的解用新的解替換當前解用新的解替換當前解;EndStart是IntensificationIt’sintabu?找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解;用新的解替換當前解是否為最后一個候選解?是否是否EffectiveTabuSearchEffectiveModelingNeighborhoodstructureObjectivefunction(fitnessorcost)Aspirationcriteria
ThecriteriaforoverrulingthetabuconstraintsanddifferentiatingthepreferenceofamongtheneighborsTabuSearchStep1:Startwithaninitialfeasiblesolution.Step2:Generateallpossiblesolutionsintheneighborhoodofthesolution(usingperturbations/moves)Step3:Eachmove(solution)isevaluatedandthebestneighbor(move)isselected.Step4:Iftheselectedbestmoveisinthetabulist,thenthenextbestmoveisselected.Thesolutionobtainedisbetterthanthebestsolutionrecordedsofar,thenthenewsolutionisthebestsolution. Taburestrictionrule:Amoveistabuifthatmoveisintabulist
Tabutenure:No.ofiterationsamoveremainstabu. Tabulist:Thesetofmovesthatarenotconsideredforevaluationtillitstabutenureends.Ifthechosensolutionisnotbetterthanthebestsolution,stilladdthebestmovetotabulist.Reasonbeingisthatifnoimprovementsarefoundfornumberofiterationsequaltotheno.ofelementsinthetabulist,thelistbecomesemptyandnoprohibitionisgiven.Step5:Storethecurrentmove/solutioninthetabulistandreleasethemoveforwhichtabutenureisover.Continuethesearchprocesswiththecurrentsolutiontilltheterminationconditionisreached.Tabulist:Thelistconsistsofcombinationofjobattributes,thejobnumberanditspreviouslocationorpositionforrestrictionrule(a)andonlythejobnumberfor(b).
Tabulistsize:Experimentsarecarriedoutwithfixedanddynamicallychangingtabulistsizes.
Withrespecttodynamicallychangingtabulistsizesweimplementedthefollowingstrategy:
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 超市停車協(xié)議書模板
- 贈予房屋過戶合同協(xié)議
- 財務全職外派合同協(xié)議
- 購買服務補充合同協(xié)議
- 購買河沙協(xié)議書范本
- 2025年酒店管理考核試題及答案
- 第38屆全國中學生物理競賽復賽試題
- 2022年全國中學生數(shù)學奧林匹克競賽(預賽)暨2022年全國高中數(shù)學聯(lián)合競賽加試(B 卷)參考答案及評分標準
- 櫥柜加工安裝合同協(xié)議
- 比亞迪合伙協(xié)議書模板
- 小水滴的訴說省公開課一等獎新名師優(yōu)質(zhì)課比賽一等獎課件
- 人體生物醫(yī)學研究倫理審查PPT幻燈片
- 餐飲場所消防安全培訓
- 制作自然發(fā)酵酸奶的方法
- 《肖申克的救贖》中英雙語劇本
- 護士長管理能力培訓講義課件
- 2022年黑龍江省鄉(xiāng)村醫(yī)生招聘筆試試題及答案解析
- 濟南市海綿城市建設建筑與小區(qū)改造項目案例-山東省經(jīng)濟技術(shù)開發(fā)中心宿舍-2
- 幼兒園辦學資料:幼兒圖書目錄
- 扣款申請單(標準模版)
- DB31-T 1338-2021船舶供應服務物料產(chǎn)品分類與編碼要求
評論
0/150
提交評論