禁忌搜索算法

1、禁忌搜索Tabu Search,禁忌搜索(Tabu Search或Taboo Search，简称TS)的思想最早由Glover(1986)提出，它是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。,禁忌搜索概述,禁忌搜索概述,TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。 相对于模拟退火和遗传算法，TS是又一种搜索特点不同的算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究

2、，并大有发展的趋势。,特点 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、的元素相同，所以选择次好的解，从而避免死循环,3的邻域,1的邻域,1,2的邻域,2,4的邻域,4,3,5,禁忌表的更新,更新原则：先进先出 , , , , , , .,禁忌表中元素,禁忌表中元素的可以是完整的解，可以是完整解的一部分，也可以是采取的一个生成相邻解的动作等等 完整解：12345,13245,31245 生成相邻解的操作（如交换的动作）： 32, 31 从12345开始，取3出来，插入1245每个位置前面,禁忌表长度,太短：计算速度快，但容易陷入死循环 太长：计算速度慢 在搜索过程中，禁忌表长度设为固定 在搜索过程中，禁忌表长度可动态变化 禁忌表长度：510,如果找到了一个新的解比

4、当前记录的最好解还要好，那么即使从当前得到这个新的解被tabu list禁止，仍然接受这个新的解，并更新tabu list. 即tabu list对这个解没有禁止作用 假设记录生成相邻解的方法，Tabu list = , , ,下一步采用方法生成了迄今为止最好的解，仍然接受这个，更新Tabu list=, , ,藐视准则（Aspiration criterion）,分散搜索：是为了对整个解的空间进行更广泛的覆盖，而不是仅仅局限在某个局部的区域。,分散搜索（Diversification）和 集中搜索（Intensification）策略,无邻域的搜索,有邻域的搜索,有邻域的搜索 NI=0,求得

5、一系列候选解， 并按优劣排序,最好的候选 解比BS好？,接受新的解用新的 解替换当前解,用新的解替换 BS;,End,Start,是,Intensification,Its in tabu？,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,TSP算例,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候选解， 并按优劣排序,最好的新解比 BS好？,接受

6、新的解用新的 解替换当前解,用新的解替换 当前解;,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=初始解,

7、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=初始解,BS,初始解,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候

8、选解， 并按优劣排序,最好的新解比 BS好？,接受新的解用新的 解替换当前解,用新的解替换 当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,用插值的方法求得候选解：生成随机数r=1,6,选取第r个位置上的元素，插入到其余位置前面,随机数4,Tabu list 初始化(清空) 设M,N

9、的值,求得初始解 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, 决定接受与否,BS,接受最好的候选解，并替换当前解,Tabu list 41， ，NI=1,

10、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,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,用插值的方法求得候选解

11、,随机数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, 决定接受与否,BS,考虑最好的候选解

12、,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,接受新的解；用新

13、 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,判断是否为tabu, 决定接受与否,BS,考虑下一个最好的候选解,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=

14、0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,更新当前解、最好解、tabu list 及相关参数,BS,Tabu list 31，41 ，NI=2,n=2,当前解,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候选解， 并按优劣排序,最好的新解比 BS好？,接受新的解用新的 解替换当前解,用新的解替换 当前解;,End,Start,是,Intensification,Its in tabu？

15、,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,分散搜索（diversification）,BS,Tabu list ，NI=0,n=2,随机生产新的当前解,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候选解， 并按优劣排序,最好的新解比 BS好？,接受新的解用新的 解替换当前解,用新的解替换 当前解;,End,Start,是,Intensif

16、ication,Its in tabu？,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,用插值的方法求得候选解,随机数5,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候选解， 并按优劣排序,最好的新解比 BS好？,接受新的解用新的 解替换当前解,用新的解替换 当前解;,End,Start,是,Intensific

17、ation,Its in tabu？,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,判断是否为tabu, 决定接受与否,BS,接受最好的候选解，并替换当前解,Tabu list 64， ，NI=1,n=3,当前解,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候选解， 并按优劣排序,最好的新解比 BS好？,接受新的解用新的 解替换当前解,用新的解

18、替换 当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,求得一系列候选解，并按优劣排序,用插值的方法求得候选解,随机数2,Tabu list 初始化(清空) 设M,N的值,求得初始解 BS=初始解,n=0;NI=0,求得一系列候选解， 并按优劣排序,最好的新解比 BS好？,接受新的解用新的 解替换当前解,用新的解替换

19、 当前解;,End,Start,是,Intensification,Its in tabu？,找出下一个 次好的新解,NI=NI+1,NI=0,n=n+1,nN,Diversification NI=0,NI=M?,否,否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,判断是否为tabu, 决定接受与否,BS,考虑最好的候选解,Tabu list 64， ,新生成相邻关系(4,6), is Tabu! However, it is better than BS. Thus, apply the aspiration strateg

20、y, accept it!,当前解 候选解,判断是否为tabu, 决定接受与否,BS,应用藐视法则，更新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,nN,Diversification NI=0,NI=M?,否,

21、否,是,否,是,更新tabulist,接受新的解；用新 的解替换当前解,是否为最后一 个候选解？,是,否,是,否,Effective Tabu Search,Effective Modeling Neighborhood structure Objective function (fitness or cost) Aspiration criteria The criteria for overruling the tabu constraints and differentiating the preference of among the neighbors,Tabu Search,Ste

22、p 1: Start with an initial feasible solution. Step 2: Generate all possible solutions in the neighborhood of the solution (using perturbations/ moves) Step 3: Each move (solution) is evaluated and the best neighbor (move) is selected. Step 4: If the selected best move is in the tabu list, then the n

23、ext best move is selected. The solution obtained is better than the best solution recorded so far, then the new solution is the best solution. Tabu restriction rule: A move is tabu if that move is in tabu list Tabu tenure: No. of iterations a move remains tabu. Tabu list: The set of moves that are n

24、ot considered for evaluation till its tabu tenure ends. If the chosen solution is not better than the best solution, still add the best move to tabu list. Reason being is that if no improvements are found for number of iterations equal to the no. of elements in the tabu list, the list becomes empty

25、and no prohibition is given. Step 5: Store the current move/solution in the tabu list and release the move for which tabu tenure is over. Continue the search process with the current solution till the termination condition is reached.,Tabu list: The list consists of combination of job attributes, th

26、e job number and its previous location or position for restriction rule (a) and only the job number for (b).Tabu list size: Experiments are carried out with fixed and dynamically changing tabu list sizes. With respect to dynamically changing tabu list sizes we implemented the following strategy: If there is no improvement in the prescribed nu