禁忌搜索（TS——Tabu Search）与邻域搜索基础知识

禁忌搜索，也是一种常见的邻域搜索算法。其实我觉得很多智能算法本质都是邻域搜索（本质是局部搜索）算法。只不过邻域的应用方式不同，是全局式的邻域搜索算法。比如，局部搜索中最经典的是“爬山算法”。但是会陷入局部最优。

禁忌搜索，比较适合解决大规模问题。本质思想是，在极值附近设置禁忌（暂时不许进入）的标识，以达到多多的遍历可行域，保证种群多样性的目的。由美国科罗拉多大学教授Fred Glover在1986年左右提出的，是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案；基于此，算法“移动”到一相邻的方案。经过许多连续的移动过程，提高解的质量。

主要特点：（1）基本思想——避免在搜索过程中的循环；（2）只进不退的原则，通过禁忌表实现；（3）不以局部最优作为停止准则；（4）邻域选优的规则模拟了人类的记忆功能。

禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。 禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌 对象、评价函数、特赦规则、记忆频率信息等概念。

下面这幅图比较形象：

1.邻域即我们常规理解的邻域；邻域移动又被称为“算子”。

2.候选解：即通过邻域生成一定数量的解，也就是一部分邻域，可以是选择最优的邻域，也可以是随机选择邻域；

3.评价函数：一般是目标函数

4.特赦/破禁规则（Aspiration Criterion）：为了避免陷入局部最优而特有的。迭代的某一步会出现候选集的某一个元素被禁止搜索，但是若解禁该元素，则会使评价函数有所改善，因此我们需要设置一个特赦规则，当满足该条件时该元素从禁忌表中跳出。

破禁准则是对于禁忌表的适度放松。当某个被禁忌的移动可得到优于未被禁忌的移动得到的最优邻域解和历史所得到的最优解时，算法应接受该移动，不受禁忌表的限制。

5.最最重要的：禁忌表，tabu_list，防止搜索出现循环。一般情况下是其过一段时间（禁忌长度）后自动消失，这里我们可以理解为“折旧“。

禁忌表的主要指标（两项指标）

（1）禁忌对象：禁忌表中被禁的对象/元素

（2）禁忌长度：禁忌的步数（对象的禁忌在多少次迭代后失效）。

禁忌表是禁忌搜索算法的核心，禁忌表的对象、步长及更新策略在很大程度上影响着搜索速度和解的质量。若禁忌对象不准确或者步长过小，算法避免陷入局部最优的能力会大打折扣；若禁忌表步长过大，搜索区域将会限制，好的解就可能被跳过。

6.邻居选择策略（Neighbor Selection Strategy）：选择最佳邻域移动的规则。

目前最广泛采用的是“最好解优先策略”及“第一个改进解优先策略”。前者需比较所有邻域，耗时较久，但解的收敛更有效；后者在发现第一个改进解就进行转移，耗时较少，但收敛效率弱于前者，对于邻域解空间较大的问题往往比较适合。

备注：

1.邻域的相关知识

邻域生成

邻域其实就是在邻域结构定义下的解的集合，比如在图2中s1-s6等构成的集合就是s的邻域。它是一个相对的概念，即邻域肯定是基于某个解（通常是初始解）产生的，比如当前解s的邻域，最优解s_b的邻域等。

邻居解是邻域内某个解的称呼。比如在图2中，解s1-s6及其该邻域中任意一个解都可以称为解s的邻居解。很好理解对吧~

邻域结构定义了一个解的邻域，就像图1中血缘关系定义了你的家人集合一样。可能大家对生活中的例子都有一个比较感性的认识，但对于启发式中的就觉得比较抽象。

启发式算法中常见的邻域结构是交换swap，插入insert...

邻域结构的设计在启发式算法中非常重要，它直接决定了搜索的范围，对最终的搜索结构有着重要的影响。邻域结构的设计直接决定了最终结果质量的好坏。

2.搜索过程

STEP1：初始解生成

因为邻域是基于一个解生成的，要想进行邻域搜索，得先有一个解。所以首先要做的，当然是生成初始解。

一般初始解都采用构造法进行生成，比如随机构造，之前讲的贪心构造等。

STEP2：邻域生成
有了初始解，接下来就可以根据所定义的邻域结构生成邻域。

STEP3：评价
有了邻域，即要搜索的局部已经确定下来，我们是就要开始进去寻找自己想要的东西了。

评价就是在解的邻域范围内对邻居解进行评价，然后选出需要的邻居解进行“移动”。一般而言，有两种评价的模式：

（1）first improve：首次提升原则，即在邻域内对解一一进行评价，一旦发现比当前解更优的邻居解立马进行“移动”。

（2）best improve：最优提升原则，遍历整个邻域，找出最好的邻居解进行“移动”。

STEP4：移动
移动就是当前解变换到刚刚评价选择的邻居解的过程。初始解在其邻域内找到了一个更好的邻居解，然后移动过去了，如下图所示：

STEP5：记录全局最优解
如果当前解比全局最优解还要优，那么更新全局最优解。

接下来就是不断重复STEP2-STEP5，直到满足终止条件，最后输出全局最优解。

（1）如果算法足够优秀加上运气好的话，最后找到全局最优是没有问题的。

（2）假如设计有问题，或者是问题结构原因，就会导致陷入局部最优。

3.假如已经是邻域最优

上述搜索过程中:STEP3：评价。当我们以first improve或者best improve对当前解的邻居进行评价时，通常的做法是找到比当前解要好的邻居解进行移动。

但往往出现的情况是当前解的邻域中并不存在更优的邻居解，如下图：

初始解即生成在了一个局部最优上面，这时候我们通常选择邻域中一个最好的邻居解进行移动（尽管它比当前解还要差），如果不这样做那就彻底陷入局部最优了。

但是这样做还有可能发生一个问题，它在兜兜转转移来移去结果又给移回去了：

这种情况也可以认为是陷入了局部最优，通常的判断条件就是经过多次邻域搜索依旧没有得到很好的improve。这种情况怎么办呢？当然是“跳一跳”（shake），如下：

这种“跳一跳”在启发式中被称为shake或者perturbation，中文称之为扰动。是跳出局部最优一个非常有效的做法。

通常的实现方式是利用随机或者其他方式，对当前解进行重组，使其结构发生较大的改变。或者直接抛弃当前解，重新生成一个解进行后续的邻域搜索。

4.随机因素

随机因素是启发式算法的一大特色。因为无法判断搜索“区域”的好坏，我们一般会随机进行选择搜索，比如初始解的生成就有很多种可能性。

每一个初始解对应的邻域不同，搜索的路径就不同。但通常经过优化，各个初始解基本都能收敛到一个比较接近的水平。

同时，shake也是一个随机过程：

5.基于邻域的局部搜索算法伪代码