第二节 禁忌搜索算法

一、导言

禁忌搜索（Tabu Search或Taboo Search, TS）是继遗传算法之后出现的又一种亚启发式（Meta-heuristic）优化算法，最早于1977年由 Glover提出。禁忌搜索模仿人类的记忆功能，使用禁忌表来封锁刚搜索过的区域来避免迂回搜索，同时赦免禁忌区域中的一些优良状态，进而保证搜索的多样性，从而达到全局优化。迄今为止，禁忌搜索已经成功应用于组合优化、生产调度、机器学习、神经网络、电力系统以及通信系统等领域，近年来又对禁忌搜索进行了一些改进与扩展。

二、禁忌搜索算法的基本思想

禁忌搜索的基本思想就是在搜索过程中将近期的搜索过程历史存放在禁忌表（Tabu List）中，阻止算法重复进入，这样就有效地防止了搜索过程的循环。禁忌表模仿了人类的记忆功能，禁忌搜索因此得名，所以称它是一种智能优化算法。

相对于普通邻域搜索而言，禁忌搜索最大的特点是可以接受劣解，这是避免陷入局优的首要条件。相应的，禁忌搜索不能以局部最优为停止准则，而是设定最大迭代次数或者给出其他特殊的停止准则。

三、禁忌搜索算法的构成要素

禁忌搜索过程中，很多构成要素对搜索的速度与质量起着至关重要的作用，包括编码方式（Encode）、适值函数（Fitness Function）、初始解（Initial Solutions）、移动（Moving）与邻域（Neighborhood）、禁忌表（Tabu List）、禁忌对象（Tabu Obj ect）、禁忌长度（Tabu Size）、渴望水平（Aspiration Level）和终止准则（Stopping Rule）等。

（一）编码方式

使用禁忌搜索求解一个问题之前，需要选择一种编码方式。编码就是将实际问题的解用一种便于算法操作的形式来描述，通常采用数学的形式；算法进行过程中或者算法结束后，还需要通过解码来还原到实际问题的解。

（二）适值函数

适值函数是用来对搜索状态进行评价的，将目标函数直接作为适值函数是最直接也是最容易理解的做法。例如，式（2-1）中目标函数为c（x），设适值函数用′c（x）表示，那么

这和遗传算法的适值函数的标定是同一道理。

（三）初始解

禁忌搜索可以随机给出初始解，也可以事先使用其他启发式等算法给出一个较好的初始解。

（四）移动与邻域

移动是从当前解产生新解的途径，例如问题（P）中用移动s产生新解s（x）。从当前解可以进行的所有移动构成邻域，也可以理解为：从当前解，经过“一步”可以到达的区域。适当的移动规则的设计，是取得高效搜索算法的关键。

（五）禁忌表

在禁忌搜索中，禁忌表是用来防止搜索过程中出现循环，避免陷入局部最优的。它通常记录最近接受的若干次移动，在一定次数之内禁止再次被访问；过了一定次数之后，这些移动从禁忌表中退出，又可以重新被访问。

（六）禁忌对象

所谓禁忌对象就是放入禁忌表中的那些元素，而禁忌的目的就是避免迂回搜索，尽量搜索一些有效的途径。尽管可以有多种方式给出禁忌对象，但是归纳起来，主要有如下三种：

（1）以状态的本身或者状态的变化作为禁忌对象；

（2）以状态分量或者状态分量的变化作为禁忌对象；

（3）采取类似于等高线的做法，将目标值作为禁忌对象。

这三种做法中，第一种做法的禁忌范围适中，第二种做法的禁忌范围较小，第三种做法的禁忌范围较大。

（七）禁忌长度

所谓禁忌长度，就是禁忌表的大小。禁忌长度不但影响了搜索的时间，还直接关系着搜索的两个关键策略：局域搜索策略和广域搜索策略。

总结起来，主要有如下一些设定禁忌长度的方法：

（1）禁忌长度t固定不变；

（2）禁忌长度t随迭代的进行而改变。

大量研究表明，动态的禁忌长度比固定不变的禁忌长度具有更好的性能。

（八）渴望水平

在某些特定的条件下，不管某个移动是否在禁忌表中，我们都接受这个移动，并更新当前解和历史最优解。移动满足的这个特定条件，称为渴望水平（Aspiration Level），或称为破禁水平、特赦准则、蔑视准则等。

渴望水平的设定也有多种形式，总结起来包括如下几种。

1．基于适配值的准则

对于开始提到的问题（P），这种渴望水平可以描述为

从直观上理解，这个准则就是找到了更好的解，那么即使这个移动被禁忌了，也要给它破禁，同时要更新历史最优解。

2．基于搜索方向的准则

如果某禁忌对象进入禁忌表的时候改善了适配值，而这次这个被禁忌的候选解又改善了适配值，那么这个移动破禁。对于问题（P），这个准则可以描述为

式中：x——该对象上次被禁忌时的解。

3．基于影响力的准则

对于这种策略的直观理解：解禁一个影响力较大的对象，可能对适配值有较大的影响。

4．其他准则

例如，当所有候选解都被禁忌，而且不满足上述渴望水平，那么可以选择其中一个最好的解来解除禁忌，否则，算法将无法继续下去。

禁忌策略与渴望水平是禁忌搜索中的两大核心策略，两者是对立统一的，也可以看作是一个统一原则的两个方面。可以通过设置不同的禁忌长度来禁止一些对象，又可以通过设置不同的渴望水平来解除一些对象，从而实现全局搜索。

（九）终止准则

和其他元启发式算法，包括遗传算法、模拟退化等一样，禁忌搜索不能保证找到问题的全局最优解，而且没有判断是否找到全局最优解的准则。因此，必须另外给出停止准则来终止搜索，常用准则包括：

（1）给定最大迭代步数；

（2）得到满意解；

（3）设定某对象的最大禁忌步数。

四、禁忌搜索算法的基本步骤

简单地讲，禁忌搜索以禁忌表来记录最近搜索过的一些状态，对于当前邻域中一个比较好的解，如果不在禁忌表中，那么可选择它作为下一步迭代的初始解，否则宁愿选择一个比较差的但不在禁忌表中的解；而如果某个解或者状态足够的好，则无论其是否在禁忌表中，都接受这个解；如此迭代，直至满足事先设定的停止准则。由于禁忌搜索的渴望水平、选择策略以及停止准则等都可以有多种设定方式，如果再使用中期表和长期表，禁忌搜索的算法步骤将多种多样。下面给出一个最基本的步骤（不考虑中期表和长期表）。

Step 1：初始化。给出初始解，禁忌表设为空。

Step 2：判断是否满足终止条件。如果满足，输出结果，算法终止；否则继续以下步骤。

Step 3：对于候选解集中的最好解，判断其是否满足渴望水平。如果满足，更新渴望水平，更新当前解，转 Step 5；否则继续以下步骤。

Step 4：选择候选解集中不被禁忌（不对应于禁忌表中的一个对象）的最好解作为当前解。

Step 5：更新禁忌表。

Step 6：转Step 2。

五、批量计划问题的禁忌搜索算法

Hindi等人和Kuik等人采用禁忌搜索算法求解了有资源约束单层级的批量计划问题和具有装配结构的带资源约束批量计划问题。本书介绍Hindi等人的禁忌搜索算法。

（一）初始解

初始解的构造是根据一个可行的生产调度，该调度假设只有第一个时段进行生产，其余时段不生产。解是由一个二进制决策矩阵来表达的。

（二）邻域与移动规则

解的邻域定义为所有可行的生产调度，通过将一个时段的状态值从T1变为T0或者从T0变为T1而达到改变解状态的目的。

（三）移动的评价

移动的评价是根据移动前的目标函数值和移动后解的目标函数值的差值来决定的。

（四）禁忌约束

禁忌约束是为了预防移动的回溯而设定的。禁忌表中某一禁忌的后部信息对应某个时段，这样就防止某一存在于禁忌表中的时段被重复访问。禁忌表的长度取为Floor（T/3）。

（五）期望水平

期望水平是用来确定何时才能破除禁忌规则，使得禁忌搜索方法能够找到最好解。这里目标函数值被用来作为期望水平，当目标函数值有改进时，可以破除禁忌约束而执行当前移动。

（六）停止准则

如果搜索过程在经过一定数量Floor（2T/3）的迭代后，仍然没有改进当前解，则停止整个程序。