概述#

禁忌搜索算法的一个主要特点是算法具有记忆性，能够对已经搜索到的解进行维护和选择性回避。算法会维护一个禁忌表，通过不断地加入新的禁忌对象和解禁旧的禁忌对象，实现避免重复在一个局部最优解附近进行的过多的无意义操作，从而扩大搜索空间，找到全局最优解。

局部搜索#

邻域#

在函数型优化问题中，邻域被定义为以某点为中心的距离不超过一定阈值的球体。
在组合优化问题中，定义邻域映射为 $N: x\in D \rightarrow N(x) \in 2^D$ ，其中 $2^D$ 表示集合 $D$ 的全部子集做并集运算形成的集合，显然有 $x \in N(x)$ 。这里称 $N(x)$ 为 $x$ 的邻域，若 $y \in N(x)$ ，则 $y$ 为 $x$ 的一个邻居。

例如，TSP 问题中，定义邻域映射为一个排列 $x$ 的两个元素交换 (2-opt) 后的结果。比如，若 $x = (1, 2, 3, 4)$ ，则 $N(x) = \{(1, 2, 3, 4), (2, 1, 3, 4), (3, 2, 1, 4), (4, 2, 3, 1), (1, 3, 2, 4), (1, 4, 3, 2), (1, 2, 4, 3)\}$ 共 $C_4^2 = 6$ 个元素。此外，这个定义也可以推广，比如定义排列中的 $k$ 个元素进行重新排列 (k-opt) 后的结果形成的集合为排列 $x$ 的邻域 $N(x)$ .

局部搜索算法#

Algorithm Local Search


Input:	问题的解空间 $D$ ，初始解 $x_0 \in D$ ，目标函数 $f$
Output:	局部最优解 $x_{best}$
1:	选定一个可行解 $x_0$ , 记录当前的最优解为 $x_{best} = x_0, T = N(x_{best})$
2:	当终止条件未满足时：
3:	从 $T - \{x_{best}\}$ 中选择一个使目标函数值最好的解 $x'$
4:	如果在去心邻域中找不到比当前解更好的解（即对于最大化问题， $f(x') \leq f(x_{best})$ ），则终止算法
5:	否则，令 $x_{best} = x'$ ， $T = N(x_{best})$ ，继续下一次迭代
6:	返回局部最优解 $x_{best}$

一次的局部搜索算法无法保证全局最优性，特别依赖于初始点的选取和邻域的结构设置。当初始点选取的足够多时，倒也可以计算出全局最优解。

禁忌搜索#

禁忌搜索的核心机制在于记忆，体现在以下几个方面

禁忌对象（Tabu Object，TO）：禁忌表中记录的元素，可以是完整的解、解的特定属性或导致解变化的移动操作。在实际应用中，通常不会存储完整的解（因为存储开销大），而是记录解的某些关键属性或变换操作。
禁忌表（Tabu List，TL）：用来存放（记忆）禁忌对象的表，是禁忌搜索算法的基本前提。禁忌表有容量限制，其大小会影响存放禁忌对象的个数，从而影响算法性能。
特赦准则(Aspiration Criteria)：即使某个移动在禁忌表中，如果它能够带来比当前已知最优解更好的结果，也可以被接受。用于在所有对象都被禁忌时解禁性能最好的对象，或者当解禁某个对象会带来显著改进时使用。
禁忌长度：每个禁忌对象在禁忌表中停留的时间长度，表示该对象在多少次迭代内不能被重复选择。禁忌长度可以是固定的，也可以是动态调整的。禁忌长度短难以跳出局部最优，紧急长度过长会增加计算时间。

Algorithm Tabu Search


Input:	问题的解空间 $D$ ，初始解 $x_0 \in D$ ，目标函数 $f$ ，禁忌表大小 $L$ ，最大迭代次数 $MaxIter$
Output:	全局最优解 $x_{best}$
1:	初始化当前解 $x_{current} = x_0$ ，全局最优解 $x_{best} = x_0$ ，禁忌表 $TabuList = \emptyset$
2:	设置迭代计数器 $iter = 0$
3:	当 $iter < MaxIter$ 时执行以下操作：
4:	从 $N(x_{current})$ 中找出所有候选移动，构成候选集合 $C$
5:	从 $C$ 中选择一个解 $x'$ ，满足： $x'$ 不在禁忌表中，或者 $x'$ 满足特赦准则（ $f(x') > f(x_{best})$ ）
6:	更新当前解 $x_{current} = x'$
7:	如果 $f(x_{current}) > f(x_{best})$ ，则更新全局最优解 $x_{best} = x_{current}$
8:	将导致 $x_{current}$ 的移动或属性加入禁忌表，如果禁忌表长度超过 $L$ ，则移除最早加入的元素
9:	$iter = iter + 1$
10:	返回全局最优解 $x_{best}$

Tabu Search 求解 TSP 问题可视化结果 TSP-tabu