禁忌搜索算法讲课讲稿.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,禁忌搜索算法,禁忌搜索概述,TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。,相对于模拟退火和遗传算法，TS是又一种搜索特点不同的算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。,特点,Neighborhood search+memory,Neighborhood search,Memory,Record the search history,Forbid cycling search,Tabu Search,3的邻域,搜索陷入循环,1的邻域,1,2的邻域,2,4的邻域,4,3,在邻域中找到最好的解,加入禁忌表，避免陷入循环,禁忌表长度为3：,规则：不得接受与禁忌表中相同的解,禁忌表的变化：,第一步搜索时 ,第二步搜索时 ,第三步搜索时,第四步搜索时,避免循环的原理：当前解为,时，其领域中最好的解为，原本下一步应为，但其与禁忌表中的元素相同，所以选择次好的解，从而避免死循环,3的邻域,1的邻域,1,2的邻域,2,4的邻域,4,3,5,禁忌表的更新,更新原则：先进先出,.,禁忌表中元素,禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一个生成相邻解的动作等等,完整解：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;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,TSP算例,City to city,1,2,3,4,5,6,1,12,4,7,9,10,2,11,20,13,8,3,6,17,13,4,6,9,5,15,6,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,Tabu list 初始化(清空)设M,N的值,Tabu list ，长度为2。记录从当前解生成新的解的过程中，产生的新的相邻关系,M=2,N=4,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,求得初始解 BS=初始解,Sequence,The length of the route,132456,28,BS,Sequence,The length of the route,132456,28,初始解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,Sequence,The length of the route,413256,30,143256,35,134256,38,132546,40,132564,45,用插值的方法求得候选解：生成随机数r=1,6,选取第r个位置上的元素，插入到其余位置前面,随机数4,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,判断是否为tabu,决定接受与否,Sequence,The length of the route,413256,30,BS,Sequence,The length of the route,132456,28,接受最好的候选解，并替换当前解,Tabu list 41，NI=1,n=1,当前解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,Sequence,The length of the route,143256,29,431256,33,432156,35,432516,36,432561,38,用插值的方法求得候选解,随机数2,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,判断是否为tabu,决定接受与否,Sequence,The length of the route,413256,30,143256,29,BS,Sequence,The length of the route,132456,28,考虑最好的候选解,Tabu list 41，NI=1,n=1,新生成相邻关系(14),is Tabu!Reject it,当前解,候选解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,判断是否为tabu,决定接受与否,Sequence,The length of the route,413256,30,431256,33,BS,Sequence,The length of the route,132456,28,考虑下一个最好的候选解,Tabu list 41，NI=1,n=1,新生成相邻关系(3,1),is not Tabu!accept it,当前解,候选解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,更新当前解、最好解、tabu list 及相关参数,Sequence,The length of the route,431256,33,BS,Sequence,The length of the route,132456,28,Tabu list 31，41，NI=2,n=2,当前解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,分散搜索（diversification）,Sequence,The length of the route,453261,45,BS,Sequence,The length of the route,132456,28,Tabu list ，NI=0,n=2,随机生产新的当前解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,Sequence,The length of the route,645321,28,465321,32,456321,34,453621,36,453216,37,用插值的方法求得候选解,随机数5,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,判断是否为tabu,决定接受与否,Sequence,The length of the route,645321,28,BS,Sequence,The length of the route,132456,28,接受最好的候选解，并替换当前解,Tabu list 64，NI=1,n=3,当前解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,Sequence,The length of the route,465321,25,654321,27,653421,19,653241,35,653214,46,用插值的方法求得候选解,随机数2,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification,NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新,的解替换当前解,是否为最后一,个候选解？,是,否,是,否,判断是否为tabu,决定接受与否,Sequence,The length of the route,645321,28,465321,25,BS,Sequence,The length of the route,132456,28,考虑最好的候选解,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 route,465321,25,BS,Sequence,The length of the route,465321,25,应用藐视法则，更新BS、当前解，及NI、n,清空 Tabu list ，NI=0,n=4,当前解,Tabu list,初始化(清空),设M,N的值,求得初始解,BS=初始解,n=0;NI=0,求得一系列候选解，,并按优劣排序,最好的新解比,BS好？,接受新的解用新的,解替换当前解,用新的解替换,当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个,次好的新解,NI=NI+1,NI=0,n=n+1,ncost=189,Generate neighbor:obtain sequence(1,2,4,3,6,5)-cost=180,Replace 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=170,170cost=170,170cost=175,175180 and(3,5)is not in tabu list,Replace current sequence by(1,2,4,5,3,6),Update Tabu list(3,5),(5,6),Step,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,