禁忌搜索算法

禁忌搜索

TabuSearch

禁忌搜索(TabuSearch或TabooSearch，简称TS)的思想最早由Glover(1986)提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索概述禁忌搜索概述TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。特点Neighborhoodsearch+memoryNeighborhoodsearchMemoryRecordthesearchhistoryForbidcyclingsearchTabuSearch3的邻域搜索陷入循环1的邻域12的邻域24的邻域43在邻域中找到最好的解加入禁忌表，避免陷入循环禁忌表长度为3：{①,②,③}规则：不得接受与禁忌表中相同的解禁忌表的变化： 第一步搜索时{}第二步搜索时{①}第三步搜索时{①,②,}第四步搜索时{①,②,③}避免循环的原理：当前解为④时，其领域中最好的解为①，原本下一步应为①，但其与禁忌表中的元素相同，所以选择次好的解⑤，从而避免死循环3的邻域1的邻域12的邻域24的邻域435禁忌表的更新更新原则：先进先出{①,②,③}{②,③,④}{③,④,⑤}….禁忌表中元素禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一个生成相邻解的动作等等完整解：{12345,13245,31245}生成相邻解的操作（如交换的动作）：{32,31}从12345开始，取3出来，插入1245每个位置前面禁忌表长度太短：计算速度快，但容易陷入死循环太长：计算速度慢在搜索过程中，禁忌表长度设为固定在搜索过程中，禁忌表长度可动态变化禁忌表长度：5—10如果找到了一个新的解比当前记录的最好解还要好，那么即使从当前得到这个新的解被tabulist禁止，仍然接受这个新的解，并更新tabulist.即tabulist对这个解没有禁止作用假设记录生成相邻解的方法，Tabulist={②,③,④},下一步采用②方法生成了迄今为止最好的解，仍然接受这个，更新Tabulist={②,③,②},藐视准则（Aspirationcriterion）分散搜索：是为了对整个解的空间进行更广泛的覆盖，而不是仅仅局限在某个局部的区域。分散搜索（Diversification）和集中搜索（Intensification）策略无邻域的搜索有邻域的搜索有邻域的搜索&分散搜索策略集中搜索：如果当前搜索区域内发现了比较好的解，如果进一步对当前区域进行更集中的搜索，那么可能会发现更多更好的解。分散搜索（Diversification）和集中搜索（Intensification）策略分散搜索策略（Diversificationstrategy）在当前搜索区域内进行了一定次数的搜索了之后（如25次），若不能发现更好的解，那么就执行分散搜索策略。把tabulist清空，然后从一个新的初始解开始搜索。集中搜索：如果最好解的记录被更新，那么就执行集中搜索策略，即清空tabulist.这样可以在当前区域进行更自由的搜索。要设计一个禁忌搜索算法，需要确定以下环节1)初始解和适配值函数（目标函数）；2)邻域结构(如何生成相邻解)和禁忌对象(禁忌表中的元素)；3)候选解选择；4)禁忌表及其长度；5)藐视准则6)集中搜索和分散搜索策略7)终止准则。’变量定义：n＝搜索次数N＝搜索N次，程序结束NI＝连续没有找到更好解的次数M＝连续M次没有找到更好解，执行分散搜索策略BS＝找到的最好的解Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的候选解比BS好？接受新的解用新的解替换当前解用新的解替换BS;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否TSP算例Citytocity12345611247910211201383617134695156Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否Tabulist初始化(清空)设M,N的值

Tabulist{}，长度为2。记录从当前解生成新的解的过程中，产生的新的相邻关系M=2N=4Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否求得一系列候选解，并按优劣排序SequenceThelengthoftheroute4132563014325635134256381325464013256445用插值的方法求得候选解：生成随机数r=[1,6],选取第r个位置上的元素，插入到其余位置前面随机数＝4Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比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求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否求得一系列候选解，并按优劣排序SequenceThelengthoftheroute1432562943125633432156354325163643256138用插值的方法求得候选解随机数＝2Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否判断是否为tabu,决定接受与否SequenceThelengthoftheroute4132563014325629BSSequenceThelengthoftheroute13245628考虑最好的候选解Tabulist{41，}，NI=1,n=1新生成相邻关系(14),isTabu!Rejectit当前解候选解Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否判断是否为tabu,决定接受与否SequenceThelengthoftheroute4132563043125633BSSequenceThelengthoftheroute13245628考虑下一个最好的候选解Tabulist{41，}，NI=1,n=1新生成相邻关系(3,1),isnotTabu!acceptit当前解候选解Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否更新当前解、最好解、tabulist

及相关参数SequenceThelengthoftheroute43125633BSSequenceThelengthoftheroute13245628Tabulist{31，41}，NI=2,n=2当前解Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否分散搜索（diversification）SequenceThelengthoftheroute45326145BSSequenceThelengthoftheroute13245628Tabulist{}，NI=0,n=2随机生产新的当前解Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否求得一系列候选解，并按优劣排序SequenceThelengthoftheroute6453212846532132456321344536213645321637用插值的方法求得候选解随机数＝5Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比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求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否求得一系列候选解，并按优劣排序SequenceThelengthoftheroute4653212565432127653421196532413565321446用插值的方法求得候选解随机数＝2Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否判断是否为tabu,决定接受与否SequenceThelengthoftheroute6453212846532125BSSequenceThelengthoftheroute13245628考虑最好的候选解Tabulist{64，}新生成相邻关系(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求得一系列候选解，并按优劣排序最好的新解比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: