Tabu Search（禁忌搜索算法）

禁忌搜索算法

1.1 算法思想

禁忌搜索(Tabu Search, TS)也是属于模拟[人类智能]的一种优化算法。

上图涉及到了禁忌搜索中的一些基本概念，现在来对这些概念作解释。

禁忌表（Tabu List，TL）
是用来存放（记忆）禁忌对象的表。它是禁忌搜索得以进行的基本前提。禁忌表本身是有容量限制的，它的大小对存放禁忌对象的个数有影响，会影响算法的性能。

禁忌对象（Tabu Object，TO）
是指禁忌表中被禁的那些变化元素。禁忌对象的选择可以根据具体问题而制定。例如在[旅行商问题]（Traveling Salesman Problem，TSP）中可以将交换的城市对作为禁忌对象，也可以将总[路径长度]作为禁忌对象。

禁忌期限（Tabu Tenure，TT）
也叫禁忌长度，指的是禁忌对象不能被选取的周期。禁忌期限过短容易出现循环，跳不出局部最优，长度过长会造成计算时间过长。

渴望准则（Aspiration Criteria，AC）
也称为特赦规则。当所有的对象都被禁忌之后，可以让其中性能最好的被禁忌对象解禁，或者当某个对象解禁会带来目标值的很大改进时，也可以使用特赦规则。

1.2 基本流程

禁忌搜索算法在初始化的时候，在搜索空间随机生成一个初始解 i，禁忌表H置空，当前解i记为历史最优解 s，然后进入迭代的搜索过程。在每一次迭代中，都从当前的解i出发，在当前禁忌表H的限制下，构造出解i的邻域A，然后从A中选出[适应值]最好的解 j 来替换解 i，同时更新禁忌表H。在解 j 替换解 i 之后，如果解 i 的质量得到改善，那么历史最优的解 s 将被解 i 替换；否则，s 保持不变，即使解 i 虽然暂时变差了，但是由于扩大了搜索空间，仍有利于跳出局部最优。得到了新的当前解 i 之后，算法返回迭代的开始继续进行，直到找到最优解或者运行了一定的迭代次数等终止条件的时候结束算法。

基本流程图和伪代码如下：

1.3 应用举例

啥？上面听不懂？那麻烦给我点个赞，然后看一看下面的内容哈哈。

问题：已知一个旅行商问题为四城市（a，b，c，d）问题，城市间的距离如[矩阵]D所示，为方便起见，假设邻域映射定义为两个城市位置对换，而始点和终点城市都是a。请分析使用禁忌搜索算法求解该问题的前面三代的过程与主要步骤。

在开始求解之前我们先分析一下问题。

分析：这是一个简单的问题,利用枚举的方法也可以找到最优的答案，但是，找到答案不是我们的目的，我们主要是想通过一一个简单的例子来理解禁忌搜索是如何进行工作的。从[距离矩阵]D可以看到，这是一个**[非对称]**的TSP问题，但是这并不影响算法的执行。由于题目假设了邻域构造的方式，而且规定了始点和终点都是城市a，因此，在以下的求解过程中，我们不使用城市a和其他城市进行交换，这样的操作并不会影响[全局寻优]的能力。

求解：