第7章 禁忌搜索算法
禁忌搜索算法模拟人脑的记忆功能，采用禁忌表技术标记并记忆已经搜索过的局部最优解，尽量避免重复进入同样的搜索，以利于快速扩大搜索空间寻找到全局最优解。禁忌算法是从过去的搜索历史中总结经验、获取知识，避免“犯错误”。因此，禁忌搜索是一种智能优化算法。本章介绍组合优化中的邻域概念，局部搜索算法，禁忌搜索算法的步骤、主要操作及参数等。
7.1 禁忌搜索算法的提出
禁忌搜索（Tabu Search或Taboo Search，TS）算法是由Glover在1986年提出的[29-31]。它的基本思想是通过对搜索历史的记录，使用一个禁忌表来记录陷入局部最优解，在下一次搜索中利用禁忌表中禁止重复选择局部极值点的搜索信息，跳出局部最优点，以利于获得全局最优解。禁忌算法在组合优化、生产调度、机器学习、神经网络、电路设计等领域获得了广泛应用。
7.2 组合优化中的邻域概念
函数优化问题的数学模型为
其中，f（x）为目标函数；g（x）为约束函数；x为决策变量；D为决策变量的定义域，是有限点组成的集合。
邻域是光滑函数极值求解中的重要概念，它是距离空间中以一点为中心的圆，如图7.1所示。通过在邻域中一点寻求光滑函数下降或上升方向的变化，以便对函数极值求解。邻域从一个当前解向一个新解的移动，称为邻域移动。邻域移动选择策略应使目标函数向有利于优化求解的方向移动。
组合优化问题可表示为一个三元组：
（D，F，f）（7.2）
其中，D为变量定义域；F为可行解区域，即
F=｛x|x∈D，g（x）≥0｝（7.3）
F中任何一个元素称为该问题的可行解，满足目标函数f（x）的最小可行解x∗称为最优解，即
f（x∗）=min｛f（x）|x∈F｝
显然，组合优化问题中可行解集合为一个有限点集，如图7.2所示。
图7.1 函数优化中的邻域
图7.2 组合优化中的邻域
组合优化问题求解的基本思想仍是在一点附近搜索另一个下降点，因为组合优化问题的可行解是一个有限的点集，所以连续函数中距离空间的邻域概念已不适用，需要从映射的角度给出新的定义。
【定义7.1】 对于组合优化问题（D，F，f），其中F为可行解区域，f为目标函数，定义域D上的一个映射
N：S∈D→N（S）∈2D（7.4）
式（7.4）称为一个邻域映射，其中2D为D的所有子集组成的集合，N（S）为S的邻域，S′∈N（S）为S的一个邻居。
7.3 局部搜索算法
因为禁忌搜索算法要利用局部搜索算法，所以先介绍一下局部搜索算法的步骤。
（1）设定一个初始可行解x0，记当前最优解xbest=x0，令P=N（xbest）（x0可根据经验或随机选取）。
（2）当满足终止运算准则时或P=∅时，输出结果，停止运算；否则从N（xbest）中选取一个集合S，得到当前的最优解xnow；若f（xnow）＜f（xbest），则xbest：=xnow，P：=N（xbest）；否则，P：=P-S；重复步骤（2）。
下面通过旅行商问题例子说明局部搜索算法。
【例7.1】 5个城市A、B、C、D、E对称TSP问题数据如图7.3所示。
解 与图7.3所对应的距离矩阵为
图7.3 5个城市对称TSP问题
（1）选定A城市为起点，令初始解xbest=（ABCDE），f（xbest）=10+8+20+5+2=45。
（2）将对换两个城市位置定义为邻域映射，记为2-opt。
情况1 采用全邻域搜索，即S：=N（xbest）。
第一循环，
N（xbest）=｛ABCDE，ACBDE，ADCBE，AECDB，ABDCE，ABEDC，ABCED｝
相对应的目标函数值为
f（x）=｛45，43，45，60，60，59，44｝
xbest=xnow=ACBDE
第二循环，
N（xbest）=｛ACBDE，ABCDE，ADBCE，AEBDC，ACDBE，ACEDB，ACBED｝
对应目标函数值为
f（x）=｛43，45，44，59，59，58，43｝
xbest=xnow=ACBDE
至此，P=N（xbest）-S已为空集，于是最优解为ADCBE，目标函数值为43。
情况2 采用一步随机搜索方法。
随机设计xbest=ABCDE，f（xbest）=45。
第一循环，采用N（xbest）中一步随机搜索，如xnow=ACBDE，因f（xnow）=43＜45，故xbest=ACBDE。
第二循环，从N（xbest）又随机选一点xnow=ADBCE，因f（xnow）=44＞43，故P=N（xbest）-｛xnow｝。
如此循环下去，最后得到最优解。综上不难看出，局部搜索算法具有容易理解、简单易行的优点，但缺点是难以保证获得全局最优解。
7.4 禁忌搜索算法
禁忌搜索算法是上述局部搜索算法的扩展，它的基本思想是，对已得到的局部最优解加以标记，以利于在下一步迭代中避开这些局部最优解。下面通过一个四城市非对称TSP问题的例子来理解禁忌搜索算法。
【例7.2】 4个城市A、B、C、D非对称TSP问题如图7.4所示。
解 设初始解x0=ABCD，邻域映射为两城市位置对换，始、终点均为A城市，目标值为f（x0）=4，城市之间的距离矩阵为
图7.4 四城市非对称TSP问题
（1）因为以A为始、终点，所以ABCD当前解中A不动，只能B、C、D之间的两两对换最多形成3个对换对，对换后按目标值从小到大排列，均大于当前解，表明当前的解已达到局部最优解而停止。
如果允许从候选解中选一个最好的对换，即CD城市位置对换，则解从ABCD变为ABDC，目标值上升，但此法可能跳出局部最优。
（2）由于在步骤（1）中选择了CD交换，于是希望这样的交换在下面的若干次迭代中不再循环出现，因此在禁忌表中限定在3次迭代中不允许CD或DC交换。
（3）因为BC在步骤（2）中对换，在此禁忌迭代3次的CD被禁一次后还有两次禁忌，只有选择BD对换。
（4）至此，所有候选解对换被禁忌，若把上述禁忌次数由3改为2，则再迭代一步，又回到ABCD初始解，出现循环。
由上面的例子不难看出，禁忌对象（指两个城市对换，即变化的状态）、被禁的长度（即禁止迭代的次数）、候选解、评价函数和停止规则等都对算法性能有影响。
7.5 禁忌搜索算法主要操作及参数
1. 评价函数
评价函数用以评价候选解的质量，评价函数可分为以下两种情况。
（1）用目标函数作为评价函数，即
p（x）=f（x）（7.5）
也可以用目标函数值与xnow目标值的差值或与当前最优解xbest目标值的差值做评价函数，即
p（x）=f（x）-f（xnow）， 或 p（x）=f（x）-f（xbest）（7.6）
（2）构造替代函数作为评价函数，以避免直接采用目标函数计算复杂或耗时。
2. 禁忌对象
禁忌对象是指禁忌表中被禁止的那些变化元素。解状态的变化分为简单变化、解向量分量变化、目标值变化3种。
（1）简单变化：设x，y∈D，D为优化问题的定义域，x→y，如例7.1中，ABCDE→ACBDE，可视为简单变化。
（2）向量分量变化：解向量中每一个分量变化为基本元素，如ABCDE→ACBDE，只是B和C的对换。
（3）目标值变化：与等位线道理一样，把处于等位线的解视为相同。例如，目标函数f（x）=x2的目标值从1变到4，隐含解空间中有4种变化的可能：-1→-2，1→-2，-1→2，1→2。
在上述3种形式中，解的简单变化比解的分量变化和目标值变化受禁忌的范围要小，能给出较大的搜索范围，但计算时间增加；解的分量变化和目标值变化的禁忌范围比解的简单变化的禁忌范围要大，这减少了计算时间，但可能导致陷于局部最优。因此在选择禁忌对象时，要根据实际问题采用适当的变化组合。
3. 禁忌长度
禁忌长度是指被禁对象不允许选取的迭代次数t，分为下面3种情况。
（1）t取常数。
（2）t∈［tmin，tmax］，t依据被禁对象的目标值和邻域的结构而变化。当函数值下降较大时，可能谷较深，欲跳出局部最优，t应取大些。
（3）tmin，tmax的动态选取。有的情况下用tmin，tmax的变化能获得更好的解。
禁忌长度选取同实际问题、实验和设计者经验有关。
4. 候选解集合的确定
由邻域中的邻居组成，一般从邻域中选择若干个目标值或评价值最佳的邻居入选，也可以随机选取部分邻居。
5. 特赦规则
在禁忌搜索算法的迭代过程中，会出现候选解集中所有对象被禁忌，或一对象被禁忌但其目标值非常大的情况。在上述情况下，为了实现全局最优，令一些禁忌对象重新可选，即为特赦，其相应规则称为特赦规则。常用的特赦规则有以下3种。
（1）基于评价值的规则。
（2）基于最小错误的规则：从候选解中选出一个评价值最小的状态解解禁。
（3）基于影响力的规则：使其影响力大的禁忌对象获得自由（解禁）。
6. 记忆频率信息
在计算过程中，记忆解集合、有序被禁对象组、目标值集合等出现的频率，有助于进一步加强禁忌搜索效率，以便动态控制禁忌长度。
7. 终止规则
（1）以一个充分大的迭代次数N终止。
（2）频率控制原则。
（3）目标变化控制规则。
（4）目标值偏离程度原则。