禁忌搜索算法课件

禁忌搜索Tabu Search.禁忌搜索(Tabu Search或Taboo Search，简称TS)的思想最早由Glover(1986)提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。禁忌搜索概述.禁忌搜索概述TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。.特点Neighborhood search+memoryNeighborhood searchMemory Record the search historyForbid cycling searchTabu Search.3的的邻邻域域搜索陷入循环1的的邻邻域域12的的邻邻域域24的的邻邻域域43在邻域中找到最好的解.加入禁忌表，避免陷入循环禁忌表长度为3：,规则：不得接受与禁忌表中相同的解禁忌表的变化：第一步搜索时 第二步搜索时 第三步搜索时,第四步搜索时,.避免循环的原理：当前解为时，其领域中最好的解为，原本下一步应为，但其与禁忌表中的元素相同，所以选择次好的解，从而避免死循环3的的邻邻域域1的的邻邻域域12的的邻邻域域24的的邻邻域域435.禁忌表的更新更新原则：先进先出,.禁忌表中元素禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一个生成相邻解的动作等等完整解：12345,13245,31245生成相邻解的操作（如交换的动作）：32,31 从12345开始，取3出来，插入1245每个位置前面.禁忌表长度太短：计算速度快，但容易陷入死循环太长：计算速度慢在搜索过程中，禁忌表长度设为固定在搜索过程中，禁忌表长度可动态变化禁忌表长度：510.如果找到了一个新的解比当前记录的最好解还要好，那么即使从当前得到这个新的解被tabu list禁止，仍然接受这个新的解，并更新tabu list.即tabu list对这个解没有禁止作用假设记录生成相邻解的方法，Tabu list=,下一步采用方法生成了迄今为止最好的解，仍然接受这个，更新Tabu list=,藐藐视视准准则则（Aspiration criterion）.分分散散搜搜索索：是为了对整个解的空间进行更广泛的覆盖，而不是仅仅局限在某个局部的区域。分散搜索（分散搜索（Diversification）和）和 集中搜索（集中搜索（Intensification）策略）策略无无邻邻域的搜索域的搜索有有邻邻域的搜索域的搜索有有邻邻域的搜索域的搜索&分散搜索策略分散搜索策略.集集中中搜搜索索：如果当前搜索区域内发现了比较好的解，如果进一步对当前区域进行更集中的搜索，那么可能会发现更多更好的解。分散搜索（分散搜索（Diversification）和）和 集中搜索（集中搜索（Intensification）策略）策略.分分散散搜搜索索策策略略（Diversification strategy）在当前搜索区域内进行了一定次数的搜索了之后（如25次），若不能发现更好的解，那么就执行分散搜索策略。把tabu list清空，然后从一个新的初始解开始搜索。集中搜索：集中搜索：如果最好解的记录被更新，那么就执行集中搜索策略，即清空tabu list.这样可以在当前区域进行更自由的搜索。.要设计一个禁忌搜索算法，需要确定以下环节1)初始解和适配值函数（目标函数）；2)邻域结构(如何生成相邻解)和禁忌对象(禁忌表中的元素)；3)候选解选择；4)禁忌表及其长度；5)藐视准则6)集中搜索和分散搜索策略7)终止准则。.变量定义：n 搜索次数N 搜索N 次，程序结束NI 连续没有找到更好解的次数M 连续M次没有找到更好解，执行分散搜索策略BS 找到的最好的解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的候最好的候选选解比解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换BS;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.TSP算例City to city1 12 23 34 45 56 61 112124 47 79 910102 21111202013138 83 36 6171713134 46 69 95 515156 6.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.Tabu list 初始化初始化(清空清空)设设M,N的的值值Tabu list ，长度为2。记录从当前解生成新的解的过程中，产生的新的相邻关系M=2N=4.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.求得初始解求得初始解 BS=初始解初始解Sequence The length of the route13245628BSSequence The length of the route13245628初始解初始解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.求得一系列候求得一系列候选选解，并按解，并按优优劣排序劣排序SequenceThe length of the route4132563014325635134256381325464013256445用插用插值值的方法求得候的方法求得候选选解：生成随机数解：生成随机数r=1,6,选选取取第第r个位置上的元素，插入到其余位置前面个位置上的元素，插入到其余位置前面随机数随机数4.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.判断是否为tabu,决定接受与否Sequence The length of the route41325630BSSequence The length of the route13245628接受最好的候接受最好的候选选解，并替解，并替换换当前解当前解Tabu list 41，NI=1,n=1当前解当前解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.求得一系列候求得一系列候选选解，并按解，并按优优劣排序劣排序SequenceThe length of the route1432562943125633432156354325163643256138用插用插值值的方法求得候的方法求得候选选解解随机数随机数2.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.判断是否为tabu,决定接受与否Sequence The length of the route4132563014325629BSSequence The length of the route13245628考考虑虑最好的候最好的候选选解解Tabu list 41，NI=1,n=1新生成相邻关系(14),is Tabu!Reject it当前解当前解候候选选解解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.判断是否为tabu,决定接受与否Sequence The length of the route4132563043125633BSSequence The length of the route13245628考考虑虑下一个最好的候下一个最好的候选选解解Tabu list 41，NI=1,n=1新生成相邻关系(3,1),is not Tabu!accept it当前解当前解候候选选解解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.更新当前解、最好解、tabu list 及相关参数Sequence The length of the route43125633BSSequence The length of the route13245628Tabu list 31，41，NI=2,n=2当前解当前解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.分散搜索（diversification）Sequence The length of the route45326145BSSequence The length of the route13245628Tabu list ，NI=0,n=2随机生随机生产产新的新的当前解当前解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.求得一系列候求得一系列候选选解，并按解，并按优优劣排序劣排序SequenceThe length of the route6453212846532132456321344536213645321637用插用插值值的方法求得候的方法求得候选选解解随机数随机数5.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.判断是否为tabu,决定接受与否Sequence The length of the route64532128BSSequence The length of the route13245628接受最好的候接受最好的候选选解，并替解，并替换换当前解当前解Tabu list 64，NI=1,n=3当前解当前解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.求得一系列候求得一系列候选选解，并按解，并按优优劣排序劣排序SequenceThe length of the route4653212565432127653421196532413565321446用插用插值值的方法求得候的方法求得候选选解解随机数随机数2.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1nNDiversificationNI=0NI=M?否否否否是是否否是是更新更新tabulist接受新的解；用新接受新的解；用新的解替的解替换换当前解当前解是否是否为为最后一最后一个候个候选选解？解？是是否否是是否否.判断是否为tabu,决定接受与否Sequence The length of the route6453212846532125BSSequence The length of the route13245628考考虑虑最好的候最好的候选选解解Tabu list 64，新生成相邻关系(4,6),is Tabu!However,it is better than BS.Thus,apply the aspiration strategy,accept it!当前解当前解候候选选解解.判断是否为tabu,决定接受与否Sequence The length of the route46532125BSSequence The length of the route46532125应应用藐用藐视视法法则则，更新，更新BS、当前解，及、当前解，及NI、n清空 Tabu list ，NI=0,n=4当前解当前解.Tabu list 初始化初始化(清空清空)设设M,N的的值值求得初始解求得初始解BS=初始解初始解n=0;NI=0求得一系列候求得一系列候选选解，解，并按并按优优劣排序劣排序最好的新解比最好的新解比BS好？好？接受新的解用新的接受新的解用新的解替解替换换当前解当前解用新的解替用新的解替换换当前解当前解;EndStart是是IntensificationIts in tabu？找出下一个找出下一个次好的新解次好的新解NI=NI+1NI=0n=n+1ncost=189Generate neighbor:obtain sequence(1,2,4,3,6,5)-cost=180Replace current sequence by(1,2,4,3,6,5)Update Tabu list(2,4),(4,2)Step n+2:Generate neighbor:obtain sequence(1,2,4,3,5,6)-cost=170170cost=170170cost=175175180 and(3,5)is not in tabu listReplace current sequence by(1,2,4,5,3,6)Update Tabu list(3,5),(5,6)Step.