第七讲 禁忌搜索

1第四章禁忌搜索（TabuSearch

）一.导言二.TS的基本原理及步骤三.TS的算法步骤四.TS可以克服局优的分析五.TS举例六.TS的中、长期表的使用七.TS表的应用举例八.学习TS的几点体会3的邻域搜索陷入循环1的邻域12的邻域24的邻域43在邻域中找到最好的解31977年F.Glover提出禁忌搜索算法，90年代初得到广泛重视。是GA之后提出的另一启发式优化方法。模仿人类的记忆功能，使用禁忌表封锁刚搜索过的区域，以避免迂回搜索。同时赦免禁忌区域中的一些优良状态，以保证搜索的多样性。一.导言（1）4TS的基本思想——避免在搜索过程中的循环只进不退的原则——用Tabu表锁住退路，将近期历史搜索过程存放在禁忌表中，防止算法重新进入。不以局部最优作为停止准则，算法接受劣解，只要不在禁忌表的较好解都可作为下一次迭代的初始解。邻域选优的规则模拟了人类的记忆功能——找过的地方都记下来，不再找第二次。随着迭代的进行，禁忌表不断更新，一定迭代次数后，早期进入禁忌表解被解禁退出。一.导言（2）5禁忌表作用示例（1）七种不同绝缘材料构成一种绝缘体，如何排列七种材料使得绝缘效果最好？绝缘效果以绝缘数值表示，数值越大，效果越好。某次迭代后，材料的排列顺序为2-4-7-3-5-6-1，交换各种材料对绝缘效果的改善情况见下表：交换的材料绝缘效果改善1，32(正值表示绝缘效果变好)2，313，4-1(负值表示绝缘效果变坏)1，7-21，6-4……6禁忌表作用示例（2）可见，交换材料1和3可增加绝缘数值2，并且改善效果最好，交换后2-4-7-1-5-6-3.绝缘数值为18，将交换（1，3）加入禁忌表。此时两两交换材料对绝缘效果的影响见下表。交换的材料绝缘效果1，3-22，4-46，7-64，5-73，5-9……7禁忌表作用示例（3）上表看出，交换（1，3）对绝缘数值的降低最小，但是交换后又回到以前的状态，为避免回到上一次交换前的状态，采用禁忌表。所以，选择交换（2，4），是其它选择中使绝缘数值降低最小的一对。此禁忌表中存放的不是解，而是解的移动。为实现全局搜索，往往设置渴望水平，若一个移动达到渴望水平，能跳离局部最优，该移动可以不受禁忌表的限制，称为破禁。8TS的要素构成(1)编码方法(2)适值函数的构造(3)初始解的获得(4)移动与邻域移动(5)禁忌表(TabuList)(6)选择策略(7)渴望水平函数(AspirationLevelFunction)(8)停止准则——与GA相似一.导言（3）9(1)编码方法灵活的选择编码方法，如背包的0-1编码。同一问题有多种编码方法，如分组问题：不相同的n件物品分为m组，n=9，m=3.编码1：

1-3-4-0-2-6-7-5-0-8-9（1-4-3-0-6-2-5-7-0-9-8）

0起到隔开作用1-3-4分为一组，2-6-7-5一组，8-9一组。编码2：

1-2-1-1-2-2-2-3-3（2-1-2-2-1-1-1-3-3）表示1-3-4分为一组，2-6-7-5一组，8-9一组10(2)适值函数的构造适值函数是用来对搜索状态进行评价的。对目标函数的任何变形都可作为目标函数，只要该变形保持严格单调。11（3）初始解的获得可以随机给出初始解，也可以是其它启发式算法给出的较好的初始解。禁忌搜索算法主要是基于邻域搜索的，所以初始解对算法搜索性能影响很大。对于较为复杂的约束问题，随机产生的初始解可能是不可行解，应该采用一些启发式方法找到一个可行解作为初始解。12(4)移动与邻域移动移动是产生新解的途径，从当前解可以进行的所有的移动构成邻域，因此移动规则的设计是算法的关键。移动规则类似于交叉算子，根据具体问题进行分析设计，如排序问题中采用两两交换方式的移动规则。

13(5)禁忌表(TabuList)禁忌表是为了防止搜索过程出现循环而陷入局部最优的，是禁忌搜索算法的核心。某些移动经一定迭代次数后被解禁，又可重新访问，因此禁忌表称为短期表。禁忌对象：放入禁忌表的元素，主要包括三种，（1）以状态本身或状态变化为禁忌对象，其禁忌范围适中；（2）以状态分量或状态分量的变化作为禁忌对象，其禁忌范围较小；（3）以目标值为禁忌对象，其禁忌范围较大。禁忌长度：禁忌表的大小。禁忌表越小，计算时间和存储空间越少，但禁忌表过小，会造成搜索过程进入循环。禁忌长度分为固定禁忌长度和随时间变化禁忌长度两类。三种禁忌对象：（1）解的简单变化（类比于函数中的自变量x的变化）

三种禁忌对象：（2）向量分量的变化（类比于函数中的映射规则变化）

设原有的解向量为(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本变化为(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)即只有第i个分量发生变化。也包含多个分量变化的情形。三种禁忌对象：（3）目标值的变化（类比于函数的值域的变化）

目标值的变化隐含着解集合的变化。17(6)选择策略选择策略是从邻域中选择一个较好解作为下一次迭代初始解的方法。候选解集的确定是选择策略的关键，对算法性能影响很大。候选解集为整个邻域。选择策略是从整个邻域内选择一个最优解为下一次迭代的初始解，计算时间较长。候选解集为邻域的真子集。这种选择策略只扫描邻域的一部分构成候选解集，虽不能找到邻域内最优解，但减少了搜索时间。18(7)渴望水平函数在有些特定的条件下，不管某个移动是否在禁忌表中，都接受这个移动并更新当前解和历史最优解。这个特定的条件即为渴望水平。渴望水平的设定有如下几种形式：（1）基于适配值的准则，如果某个候选解的适配值高于历史最优解，无论是否处于禁忌表中，都选择接受。（2）基于搜索方向的准则，某禁忌对象进入紧急表时改善了适配值，而这次这个被禁忌的候选解由改善了适配值，故破禁。（3）基于影响力的准则，有的禁忌对象对适配值的影响较大，解禁会对解有较大影响，解禁时要考虑。（4）其它准则19(8)停止准则——与GA相似给定最大迭代次数得到满意解设定某对象的最大禁忌频率分散搜索：是为了对整个解的空间进行更广泛的覆盖，而不是仅仅局限在某个局部的区域。分散搜索（Diversification）和集中搜索（Intensification）策略无邻域的搜索有邻域的搜索有邻域的搜索&分散搜索策略集中搜索：如果当前搜索区域内发现了比较好的解，如果进一步对当前区域进行更集中的搜索，那么可能会发现更多更好的解。分散搜索（Diversification）和集中搜索（Intensification）策略分散搜索策略（Diversificationstrategy）在当前搜索区域内进行了一定次数的搜索了之后（如25次），若不能发现更好的解，那么就执行分散搜索策略。把tabulist清空，然后从一个新的初始解开始搜索。集中搜索：如果最好解的记录被更新，那么就执行集中搜索策略，即清空tabulist.这样可以在当前区域进行更自由的搜索。集中化intensification因为这附近良解比较多再花点功夫找找看多样化diversification这附近已经探索得差不多了再到别的地方找找看集中化与多样化的有机结合

φ多様化集中化现代启发式算法的核心问题26问题的描述及邻域的概念

TS仅用于离散优化，排斥实优化 二.TS的基本原理及步骤（1）27

二.TS的基本原理及步骤（2）28邻域举例：

x=[0,1,0,0,1,0,0] u=1, d=[0,0,1,0,0,0,0]注意：移动的意义是灵活的，目的是便于搜索。如：排序问题中一次换位可称为一次移动，还可以定义为选一个切点，两部分作交叉运算。二.TS的基本原理及步骤（3）29练习定义邻域移动为位值加1或减1,对整数编码[22353]，以下染色体是否在其邻域内：

[23353]，[23253]，[22355]，

[22343]，[22253]，[22344]，

是否是否否是30练习（2）定义邻域移动为两两换位,对顺序编码[42351]，以下染色体是否在其邻域内：

[43251]，[43512]，[43351]，

[52341]，[12354]，[34251]，

是否是否否是31禁忌表的概念禁忌表的作用：防止搜索出现循环记录前若干步走过的点、方向或目标值，禁止返回表是动态更新的——把最新的解记入，最老的解从表中释放(解禁)。表的长度称为Tabu-Size，一般取5、7、11，表长越大分散性越好。二.TS的基本原理及步骤（4）32邻域搜索规则每一步移动到不在T表中的邻域中的最优解，即若 ，则令则本次移动到最优解邻域搜索规则的作用：保证TS的优良局部搜索功能二.TS的基本原理及步骤（5）33渴望水平函数 是一个取决于和的值，若有则是不受T表限制。即使，仍可取渴望水平，一般为历史上曾经达到的最好目标值。二.TS的基本原理及步骤（6）34步骤：选一个初始点， ，令 ， ，迭代指标 ；若 停止，否则令 ，若

(其中NG为最大迭代数)停止；注： 表示非正常终止，造成的原因：邻域小，T表长。正常设置为(T表长度<邻域大小)。步骤②的作用是设置循环体出口。三.TS的算法步骤（1）35若 ，令 ,更新 (当前邻域最优目标函数值)；注：步骤③的作用邻域选优若 ， 且 ，令

,更新C(x)；注：步骤④的作用破禁检查三.TS的算法步骤（2）36三.TS的算法步骤（3）若 ，令，注：步骤⑤的作用选优并记录历史最好点,更新渴望水平)更新T表，转步2(存入T表中的第一个位置)37失败出口(避免)破禁检查初始开始更新T表停止YN停止YN若令若输出终止出口step2step3step4step5step1邻域移动择优规则38从邻域搜索的方法看移向 中最好的解，但不与当前解比较 是 中的最优点，但 可能劣于四.TS可以克服局优的分析（1）39选优规则看始终保持历史上的最优解，不以当前解为最优从停止规则上看不以最优判据为停止规则，而是指定最大迭代步数为停止条件，这样不能保证最优性。四.TS可以克服局优的分析（2）40问题的提出由7层不同的绝缘材料构成的一种绝缘体，应如何排列顺序，可获得最好的绝缘性能。五.TS举例（1）41

编码方式：顺序编码 初始编码：2-5-7-3-4-6-1

目标值：极大化目标值。邻域定义：两两交换是一个邻域移动邻域大小：TabuSize：3 NG：5五.TS举例（2）42初始表初始编码：2-5-7-3-4-6-1结论：交换4和5五.TS举例（3）移动5，467，443，622，304，1-1…………T表12343迭代1

编码：2-4-7-3-5-6-1 ==16结论：交换1和3五.TS举例（4）移动3，122，313，4-17，1-26，1-4…………T表14，52344迭代2

编码：2-4-7-1-5-6-3 ==18结论：因交换1和3已在禁忌表中，故只能交换2和4五.TS举例（5）移动1，3-22，4-47，6-64，5-75，3-9…………T表11，324，53若选择这项 =16，渴望水平不能发生作用45迭代3

编码：4-2-7-1-5-6-3 =14， =18结论：因渴望水平发挥作用，交换在破禁表中的4,5五.TS举例（6）移动4，565，327，101，3-32，6-6…………T表12，421，334，5因 =20大于渴望水平=18此时渴望水平发生作用，破禁。交换4和5。 46迭代4

编码：5-2-7-1-4-6-3 = =20结论：交换7和1五.TS举例（7）移动7，104，3-36，3-55，4-62，6-8…………T表14，522，431，347迭代5

编码：5-2-1-7-4-6-3 = =20结论：迭代已到5次，得到最优解

5-2-7-1-4-6-3和5-2-1-7-4-6-3 = =20五.TS举例（8）48引入中长期表的目的改善TS的广域搜索能力，TS的局域搜索能力很好，邻域选优快，但广域搜索能力较差。搜索能力是TS的关键，采用中长期表可改善TS的广域搜索能力。六.TS的中、长期表的使用（1）49中期表——频数表,频率表频数表的作用频数表是用来记忆不同方向的移动次数，从而加以惩罚(比如两两交换，记录每对交换的发生次数)以提高搜索方向的多样性。在不考虑中期表的情况下，每一次迭代在候选解集中选择目标函数值最小的解，若考虑中期表，每一次迭代是在候选解集中选择目标函数值小且被禁忌次数比较少的解。六.TS的中、长期表的使用（2）50在邻域选优公式中，令注：惩罚因子的取值一般应远小于目标值(1%目标值或1‰目标值)，越大分散性越好，广域搜索能力强，但会损坏邻域搜索。六.TS的中、长期表的使用（3）51频数表的记录方法（以n元素排列问题为例）将短期表和中期表放在一起，建立n×n的矩阵，右上部分为短期表，左下部分为中期表，对角线上的元素没有意义。对上半部分每做一步搜索将所有>0的数减1；对数组上半部分，给新发生的移动所对应的数组元加上Tabu-Size;T表的下半部分，用来记频数，每次(i,j)交换(i<j)，对应的((j,i)+1)来记忆频数。六.TS的中、长期表的使用（4）52频数表的优点：同一数组作为T表和频数表共同使用，方便操作又节省了时间。六.TS的中、长期表的使用（5）53频数表：Tabu-Size=7六.TS的中、长期表的使用（6）T表73，461，755，643，732，624，511，354长期表的使用——多阶段TS算法长期表的作用 使用短期表（禁忌表）的搜索方式为邻域搜索，中期表的搜索方式为区域强化式搜索，长期表的搜索方式实现了全局多样化搜索。 长期表用来记录多个初始解，从这些初始解开始进行禁忌搜索，每个阶段的初始解，在下一阶段产生初始解时，使之尽可能与已有的初始解有较大的距离，为了使各个初始解在可行域内具有良好的分散性，以实现全局搜索。短期表（禁忌表）仅记录禁忌信息，中期表记录禁忌信息和禁忌次数，长期表将各阶段初始解记录下来。六.TS的中、长期表的使用（7）55图示六.TS的中、长期表的使用（8）56函数表达式长期表的TS有很好的性能。六.TS的中、长期表的使用（9）57七.TS表的应用举例（TSP问题）变量定义：n＝搜索次数N＝搜索N次，程序结束NI＝连续没有找到更好解的次数M＝连续M次没有找到更好解，执行分散搜索策略BS＝找到的最好的解

58Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的候选解比BS好？接受新的解用新的解替换当前解用新的解替换BS;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否59TSP算例Citytocity1234561124791021120138361713469515660Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否61Tabulist初始化(清空)设M,N的值

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

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

及相关参数SequenceThelengthoftheroute43125633BSSequenceThelengthoftheroute13245628Tabulist{31，41}，NI=2,n=2当前解76Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否77分散搜索（diversification）SequenceThelengthoftheroute45326145BSSequenceThelengthoftheroute13245628Tabulist{}，NI=0,n=2连续M次没有出现更好解，因此产生新初始解随机生产新的当前解78Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否79求得一系列候选解，并按优劣排序SequenceThelengthoftheroute6453212846532132456321344536213645321637用插值的方法求得候选解随机数＝580Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart是IntensificationIt’sintabu？找出下一个次好的新解NI=NI+1NI=0n=n+1n<NDiversificationNI=0NI=M?否否是否是更新tabulist接受新的解；用新的解替换当前解是否为最后一个候选解？是否是否81判断是否为tabu,决定接受与否SequenceThelengthoftheroute64532128BSSequenceThelengthoftheroute13245628接受最好的候选解，并替换当前解Tabulist{64，}，NI=1,n=3当前解82Tabulist初始化(清空)设M,N的值求得初始解BS=初始解n=0;NI=0求得一系列候选解，并按优劣排序最好的新解比BS好？接受新的解用新的解替换当前解用新的解替换当前解;EndStart