禁忌搜索算法

禁忌搜索

TabuSearch

禁忌搜索(TabuSearch或TabooSearch，簡(jiǎn)稱(chēng)TS)的思想最早由Glover(1986)提出，它是對(duì)局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對(duì)人類(lèi)智力過(guò)程的一種模擬。禁忌搜索概述禁忌搜索概述TS算法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(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)域取得了很大的成功，近年來(lái)又在函數(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í){①,②,③}避免循環(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開(kāi)始，取3出來(lái)，插入1245每個(gè)位置前面禁忌表長(zhǎng)度太短：計(jì)算速度快，但容易陷入死循環(huán)太長(zhǎng)：計(jì)算速度慢在搜索過(guò)程中，禁忌表長(zhǎng)度設(shè)為固定在搜索過(guò)程中，禁忌表長(zhǎng)度可動(dòng)態(tài)變化禁忌表長(zhǎng)度：5—10如果找到了一個(gè)新的解比當(dāng)前記錄的最好解還要好，那么即使從當(dāng)前得到這個(gè)新的解被tabulist禁止，仍然接受這個(gè)新的解，并更新tabulist.即tabulist對(duì)這個(gè)解沒(méi)有禁止作用假設(shè)記錄生成相鄰解的方法，Tabulist={②,③,④},下一步采用②方法生成了迄今為止最好的解，仍然接受這個(gè)，更新Tabulist={②,③,②},藐視準(zhǔn)則（Aspirationcriterion）分散搜索：是為了對(duì)整個(gè)解的空間進(jìn)行更廣泛的覆蓋，而不是僅僅局限在某個(gè)局部的區(qū)域。分散搜索（Diversification）和集中搜索（Intensification）策略無(wú)鄰域的搜索有鄰域的搜索有鄰域的搜索&分散搜索策略集中搜索：如果當(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)更好的解，那么就執(zhí)行分散搜索策略。把tabulist清空，然后從一個(gè)新的初始解開(kāi)始搜索。集中搜索：如果最好解的記錄被更新，那么就執(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)則?！兞慷x：n＝搜索次數(shù)N＝搜索N次，程序結(jié)束NI＝連續(xù)沒(méi)有找到更好解的次數(shù)M＝連續(xù)M次沒(méi)有找到更好解，執(zhí)行分散搜索策略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<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否TSP算例Citytocity12345611247910211201383617134695156Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否Tabulist初始化(清空)設(shè)M,N的值

Tabulist{}，長(zhǎng)度為2。記錄從當(dāng)前解生成新的解的過(guò)程中，產(chǎn)生的新的相鄰關(guān)系M=2N=4Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute4132563014325635134256381325464013256445用插值的方法求得候選解：生成隨機(jī)數(shù)r=[1,6],選取第r個(gè)位置上的元素，插入到其余位置前面隨機(jī)數(shù)＝4Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute41325630BSSequenceThelengthoftheroute13245628接受最好的候選解，并替換當(dāng)前解Tabulist{41，}，NI=1,n=1當(dāng)前解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute1432562943125633432156354325163643256138用插值的方法求得候選解隨機(jī)數(shù)＝2Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563014325629BSSequenceThelengthoftheroute13245628考慮最好的候選解Tabulist{41，}，NI=1,n=1新生成相鄰關(guān)系(14),isTabu!Rejectit當(dāng)前解候選解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563043125633BSSequenceThelengthoftheroute13245628考慮下一個(gè)最好的候選解Tabulist{41，}，NI=1,n=1新生成相鄰關(guān)系(3,1),isnotTabu!acceptit當(dāng)前解候選解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否更新當(dāng)前解、最好解、tabulist

及相關(guān)參數(shù)SequenceThelengthoftheroute43125633BSSequenceThelengthoftheroute13245628Tabulist{31，41}，NI=2,n=2當(dāng)前解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否分散搜索（diversification）SequenceThelengthoftheroute45326145BSSequenceThelengthoftheroute13245628Tabulist{}，NI=0,n=2隨機(jī)生產(chǎn)新的當(dāng)前解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute6453212846532132456321344536213645321637用插值的方法求得候選解隨機(jī)數(shù)＝5Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute64532128BSSequenceThelengthoftheroute13245628接受最好的候選解，并替換當(dāng)前解Tabulist{64，}，NI=1,n=3當(dāng)前解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute4653212565432127653421196532413565321446用插值的方法求得候選解隨機(jī)數(shù)＝2Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute6453212846532125BSSequenceThelengthoftheroute13245628考慮最好的候選解Tabulist{64，}新生成相鄰關(guān)系(4,6),isTabu!However,itisbetterthanBS.Thus,applytheaspirationstrategy,acceptit!當(dāng)前解候選解判斷是否為tabu,決定接受與否SequenceThelengthoftheroute46532125BSSequenceThelengthoftheroute46532125應(yīng)用藐視法則，更新BS、當(dāng)前解，及NI、n清空Tabulist{}，NI=0,n=4當(dāng)前解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個(gè)次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個(gè)候選解？是否是否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: