禁忌搜索算法（TS）

1 算法背景

禁忌搜索算法（Tabu Search或Taboo Search，简称TS）最早是由Glover等人在1986年提出。TS本质上是对局部领域搜索的一种扩展，是一种全局逐步寻优算法。TS算法通过模拟人类智能的记忆机制，引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。

禁忌搜索是人工智能的一种体现，该算法最重要的思想是标记对应已经搜索的局部最优解的一些对象并在进一步的迭代搜索中尽量避开这些对象，从而保证对不同的有效搜索途径进行探索。禁忌搜索提出了一种基于智能记忆的框架，在实际实现过程中可以根据问题的性质做有针对性的设计。在关于TS的研究中，一般比较常用的是与其他优化算法相结合，也就是把TS算法思想用到其他优化算法中去。

2 基本概念

2.1 领域移动

邻域移动是在当前解的基础上，按照特定的移动策略产生一定数目的新解，不断拓展搜索空间。通过邻域移动产生的新解被称为 邻域解 ，新解的数目称为 邻域解规模。

2.2 禁忌表

禁忌表是用来存放禁忌对象的一个容器，被放入禁忌表中的禁忌对象在解禁之前不能被再次搜索，禁忌表模拟了人的记忆机制，防止搜索陷入局部最优，进而探索更多的搜索空间。

禁忌表可以使用数组、队列、栈、链表等顺序结构实现，每个顺序结构的元素定义根据具体问题确定。

禁忌表中禁忌对象的替换可以采用FIFO方式(不考虑藐视准则的作用),也可以采用其他方式,甚至是动态自适应的方式。

2.3 禁忌长度

禁忌长度就是每个禁忌对象在禁忌表中的生存时间，也称为禁忌对象的任期。搜索过程每经历过一次迭代，禁忌长度（时间）减少1，非0的时候对应的禁忌对象就是禁忌状态，不能被搜索过程选为新解。搜索中为了减少搜索的代价（包括空间和时间），要求禁忌长度尽量小，但禁忌长度过小将使搜索无法跳出局部最小。

对于禁忌长度的选取主要有静态和动态两种方法。静态方法是指在搜索过程中，禁忌长度是一个固定值，比如 ，其n为问题维数或规模。动态方法是指在搜索过程中，禁忌长度也是动态变化的，当算法搜索能力较强时，可以增大禁忌长度从而延续当前的搜索能力，并避免搜索陷入局部优解，反之亦然。

2.4 候选解

候选解是当前解邻域解集的一个子集。搜索中为了减少搜索的代价（包括空间和时间），要求候选解集尽量小，候选解集过小将使搜索早熟收敛。候选解集的大小常根据问题特性和对算法的要求确定。

2.5 特赦准则

特赦准则也称为藐视准则、破禁准则、释放准则等。特赦准则保证了搜索过程在全部候选解被禁或是有优于当前最优解的候选解（或状态）被禁时，能够释放特定解（或状态），从而实现高效的全局优化搜索。

藐视准则的设置是算法避免遗失优良状态,激励对优良状态的局部搜索,进而实现全局优化的关键步骤。

2.6 终止准则

终止准则即停止准则，即算法在什么条件下停止搜索过程。实际应用中无法使用在禁忌长度充分大的条件下实现状态空间的遍历这一理论收敛条件，往往使用如下近似终止（收敛）准则：

（1）算法迭代次数达到指定最大次数停止。

（2）最优解的目标函数值小于指定误差。

（3）最优解的禁忌频率达到指定值。

2.7 解的评价函数

解的评价函数也就是我们经常说的适应度函数，对于禁忌搜索空间中的解，通过评价函数来计算其对应的评价函数值，评价函数值的大小代表了解的优劣程度。根据问题的特性，可能评价函数值越大越好，也可能越小越好，两种目标可以等价转换（取倒数）。

评价函数 ：（1）一种简单、直观的方法是直接把优化目标作为评价函数，同理任何与优化目标等价的变换函数也可以作为评价函数。（2）有时，目标函数的计算困难或是耗时较多，则可以取体现问题目标的特征值来替代计算，但必须要保证特征值与问题目标有一致的最优性。

在求解带有约束的优化问题时，可以将解违反约束的情况作为 惩罚因子 加入评价函数，从而规避传统启发式方法中对于约束的复杂处理。带有惩罚因子的评价函数基本形式如下：

其中P(Rj,X)表示第j个约束的惩罚值，当解满足约束时，惩罚值为0。

3 算法基本思想

TS算法的基本思想：给定一个当前解初始解和一种邻域,然后在当前解的邻域中确定若干候选解，若最佳候选解对应的目标值优于“best so far”状态,则忽视其禁忌特性,用其替代当前解和“best so far”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期若不存在上述候选解,则在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期如此重复上述迭代搜索过程,直至满足停止准则。

4 算法流程

TS算法的一般流程是：

（1）给定算法参数,随机产生初始解,置禁忌表为空。

（2）判断是否满足终止条件？若是，则结束算法，并输出结果；

（3）利用当前解的邻域函数产生其所有或若干邻域解,并从中确定若干候选解。

（4）对候选解判断是否满足藐视准则？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤（6）；否则，继续以下步骤

（5）判断候选解对应的各对象的禁忌情况，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象

（6）转到（2）

5 算法优缺点

优点 ：

（1）搜索过程中可以接受劣解,因此具有较强的“爬山”能力,搜索时能够跳出局部最优解,转向解空间的其他区域,从而增加获得更好的全局最优解的概率。

（2）新解不是在当前解的邻域中随机产生,而或是优于“best fso far”的解,或是非禁忌的最佳解,因此 选取优良解的概率远远大于其它解 。

缺点：

（1）初始值敏感，即 对初始解的依赖性较强 ,好的初始解有助于搜索很快的达到最优解,而较坏的初始解往往会使搜索很难或不能够达到最优解

（2）迭代搜索过程是串行的,仅是单一状态的移动,而非并行搜索

参考文献 ：

[1]董宗然,周慧.禁忌搜索算法评述[J].软件工程师,2010(Z1):96-98.

[2]王民生. 禁忌搜索算法及其混合策略的应用研究[D].大连交通大学,2005.