禁忌搜索算法

禁忌搜索

TabuSearch

禁忌搜索(TabuSearch或TabooSearch，簡稱TS)的思想最早由Glover(1986)提出，它是對局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對人類智力過程的一種模擬。禁忌搜索概述禁忌搜索概述TS算法通過引入一個靈活的存儲結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過藐視準(zhǔn)則來赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實現(xiàn)全局優(yōu)化。相對于模擬退火和遺傳算法，TS是又一種搜索特點不同的算法。迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢。特點Neighborhoodsearch+memoryNeighborhoodsearchMemoryRecordthesearchhistoryForbidcyclingsearchTabuSearch3的鄰域搜索陷入循環(huán)1的鄰域12的鄰域24的鄰域43在鄰域中找到最好的解加入禁忌表，避免陷入循環(huán)禁忌表長度為3：{①,②,③}規(guī)則：不得接受與禁忌表中相同的解禁忌表的變化： 第一步搜索時{}第二步搜索時{①}第三步搜索時{①,②,}第四步搜索時{①,②,③}避免循環(huán)的原理：當(dāng)前解為④時，其領(lǐng)域中最好的解為①，原本下一步應(yīng)為①，但其與禁忌表中的元素相同，所以選擇次好的解⑤，從而避免死循環(huán)3的鄰域1的鄰域12的鄰域24的鄰域435禁忌表的更新更新原則：先進(jìn)先出{①,②,③}{②,③,④}{③,④,⑤}….禁忌表中元素禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一個生成相鄰解的動作等等完整解：{12345,13245,31245}生成相鄰解的操作（如交換的動作）：{32,31}從12345開始，取3出來，插入1245每個位置前面禁忌表長度太短：計算速度快，但容易陷入死循環(huán)太長：計算速度慢在搜索過程中，禁忌表長度設(shè)為固定在搜索過程中，禁忌表長度可動態(tài)變化禁忌表長度：5—10如果找到了一個新的解比當(dāng)前記錄的最好解還要好，那么即使從當(dāng)前得到這個新的解被tabulist禁止，仍然接受這個新的解，并更新tabulist.即tabulist對這個解沒有禁止作用假設(shè)記錄生成相鄰解的方法，Tabulist={②,③,④},下一步采用②方法生成了迄今為止最好的解，仍然接受這個，更新Tabulist={②,③,②},藐視準(zhǔn)則（Aspirationcriterion）分散搜索：是為了對整個解的空間進(jìn)行更廣泛的覆蓋，而不是僅僅局限在某個局部的區(qū)域。分散搜索（Diversification）和集中搜索（Intensification）策略無鄰域的搜索有鄰域的搜索有鄰域的搜索&分散搜索策略集中搜索：如果當(dāng)前搜索區(qū)域內(nèi)發(fā)現(xiàn)了比較好的解，如果進(jìn)一步對當(dāng)前區(qū)域進(jìn)行更集中的搜索，那么可能會發(fā)現(xiàn)更多更好的解。分散搜索（Diversification）和集中搜索（Intensification）策略分散搜索策略（Diversificationstrategy）在當(dāng)前搜索區(qū)域內(nèi)進(jìn)行了一定次數(shù)的搜索了之后（如25次），若不能發(fā)現(xiàn)更好的解，那么就執(zhí)行分散搜索策略。把tabulist清空，然后從一個新的初始解開始搜索。集中搜索：如果最好解的記錄被更新，那么就執(zhí)行集中搜索策略，即清空tabulist.這樣可以在當(dāng)前區(qū)域進(jìn)行更自由的搜索。要設(shè)計一個禁忌搜索算法，需要確定以下環(huán)節(jié)1)初始解和適配值函數(shù)（目標(biāo)函數(shù)）；2)鄰域結(jié)構(gòu)(如何生成相鄰解)和禁忌對象(禁忌表中的元素)；3)候選解選擇；4)禁忌表及其長度；5)藐視準(zhǔn)則6)集中搜索和分散搜索策略7)終止準(zhǔn)則?！兞慷x：n＝搜索次數(shù)N＝搜索N次，程序結(jié)束NI＝連續(xù)沒有找到更好解的次數(shù)M＝連續(xù)M次沒有找到更好解，執(zhí)行分散搜索策略BS＝找到的最好的解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的候選解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換BS;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否TSP算例Citytocity12345611247910211201383617134695156Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否Tabulist初始化(清空)設(shè)M,N的值

Tabulist{}，長度為2。記錄從當(dāng)前解生成新的解的過程中，產(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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute4132563014325635134256381325464013256445用插值的方法求得候選解：生成隨機(jī)數(shù)r=[1,6],選取第r個位置上的元素，插入到其余位置前面隨機(jī)數(shù)＝4Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否判斷是否為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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute1432562943125633432156354325163643256138用插值的方法求得候選解隨機(jī)數(shù)＝2Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否判斷是否為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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否判斷是否為tabu,決定接受與否SequenceThelengthoftheroute4132563043125633BSSequenceThelengthoftheroute13245628考慮下一個最好的候選解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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否更新當(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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否分散搜索（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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute6453212846532132456321344536213645321637用插值的方法求得候選解隨機(jī)數(shù)＝5Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否判斷是否為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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否求得一系列候選解，并按優(yōu)劣排序SequenceThelengthoftheroute4653212565432127653421196532413565321446用插值的方法求得候選解隨機(jī)數(shù)＝2Tabulist初始化(清空)設(shè)M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候選解，并按優(yōu)劣排序最好的新解比BS好？接受新的解用新的解替換當(dāng)前解用新的解替換當(dāng)前解;EndStart是IntensificationIt’sintabu？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否判斷是否為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？找出下一個次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替換當(dāng)前解是否為最后一個候選解？是否是否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: