3 禁忌搜索算法

3.1 禁忌搜索算法简介

禁忌搜索算法是组合优化算法的一种，是局部搜索算法的扩展。禁忌搜索算法是人工智能在组合优化算法中的一个成功应用。禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌就是禁止重复前面的工作。 禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点。

禁忌搜索算法实现的技术问题是算法的关键。禁忌搜索算法涉及侯选集合、禁忌对象、评价函数、特赦规则、记忆频率信息等概念。

（1）邻域

在组合优化中，距离的概念通常不再适用，但是在一点附近搜索另一个下降的点仍然是组合优化数值求解的基本思想。因此需要重新定义邻域的概念。

一个组合优化问题可以用三参数$(D,F,f)$表示，其中$D$表示决策变量的定义域，$F$表示可行解区域，$F$中的任何一个元素称为该问题的可行解，$f$表示目标函数。满足$f(x^*)=\min\left\{f(x)|x \in F\right\}$的可行解$x^*$称为该问题的最优解。

定义1 对于组合优化问题$(D,F,f)$，$D$上的一个映射：

$$ N：S \in D \to N(S) \in 2^D $$

称为一个邻域映射，其中$2^D$表示$D$的所有子集组成的集合，$N(S)$称为$S$的邻域，$S' \in N(S)$称为$S$的一个邻居。

（2）候选集合

候选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价值最佳的邻居入选。

（3）禁忌对象和禁忌长度

禁忌表中的两个主要指标是禁忌对象和禁忌长度。禁忌算法中，由于我们要避免一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作，这些元素就是我们指的禁忌对象。禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象 $x$一个数（禁忌长度）$t$，要求对象$x$在$t$步迭代内被禁，在禁忌表中采用$tabu(x)=t$记忆，每迭代一步，该项指标做运算$tabu(x)=t-1$，直到$tabu(x)=0$时解禁。于是，我们可将所有元素分成两类，被禁元素和自由元素。禁忌长度$t$的选取可以有多种方法，例如$t=$常数，或$t=[\sqrt{n}]$，其中$n$为邻域中邻居的个数；这种规则容易在算法中实现。

（4）评价函数

评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标，但有时为了方便或易于计算，会采用其他函数来取代目标函数。

（5）特赦规则

在禁忌搜索算法的迭代过程中，会出现侯选集中的全部对象都被禁忌，或有一对象被禁，但若解禁则其目标值将有非常大的下降情况。在这样的情况下，为了达到全局最优， 我们会让一些禁忌对象重新可选。 这种方法称为特赦， 相应的规则称为特赦规则。

（6）记忆频率信息

在计算的过程中，记忆一些信息对解决问题是有利的。如一个最好的目标值出现的频率很高，这使我们有理由推测：现有参数的算法可能无法再得到更好的解。根据解
决问题的需要，我们可以记忆解集合、被禁对象组、目标值集合等的出现频率。
频率信息有助于进一步加强禁忌搜索的效率。我们可以根据频率信息动态控制禁忌的长度。 一个最佳的目标值出现的频率很高， 有理由终止计算而将此值认为是最优值。

3.2 模型及其求解

我们用禁忌搜索算法研究如下问题：

（1）之前的飞机问题

（2）我方有三个基地，经度、纬度分别为（70，40），（72，45），（68，48）。假设我方所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标，怎样划分任务，才能使时间最短，且任务比较均衡。

3.2.1 问题（1）的求解

求解的禁忌搜索算法描述如下：

（1）解空间

解空间$S$可以表示为{1,2,...,101,102}的所有固定起点和终点的循环排列集合，即$S=\left\{\pi_1,\cdots,\pi_{102}|\pi_1=1,(\pi_2,\cdots,\pi_{101})\right\}$为$\left\{2,3,\cdots,101\right\}$的循环排列，$\pi_{102}=102$,其中每一个循环表示侦察100个目标的一个回路，$\pi_i=j$表示在第$i$次侦察$j$点。

（2）目标函数

目标函数为侦察所有目标的路径长度。我们要求：

$$ \min f(\pi_1,\pi_2,\cdots,\pi_{102})=\sum^101_{i=1}d_{\pi_i\pi_{i+1}}\\ $$

（3）候选集合

定义2 对于路径$\pi_1\cdots\pi_{u-1}\pi_u\pi_{u+1}\cdots\pi_{v-1}\pi_v\pi_{v+1}\cdots\pi_{102}\\$ ，交换$u$与$v$之间的顺序，得到的新路径为：

$$ \pi_1\cdots\pi_{u-1}\pi_v\pi_{v+1}\cdots\pi_{u+1}\pi_u\pi_{v+1}\cdots\pi_{102}\\ $$

称为原路径二邻域的一个邻居。

如果考虑当前解的全部二邻域（或三邻域）的邻居，将面临着太大的工作量。因此我们用随机选取的方法每次选取 50 个邻居组成的集合作为侯选集合。而将省下的时间作更多次搜索， 这样做同样可以保证较高的精确度， 同时可以大大提高算法的效率。

（4）禁忌长度及禁忌对象

对于上述定义的二邻域中的邻居总数为$C^2_{100}$，我们的禁忌长度取为$t=70 \approx \sqrt{C^2_{100}}$

我们把禁忌表设计成一个循环队列，初始化禁忌表$H=\Phi$。从候选集合$C$中选出一个向量$x$，如果$x \notin H$，并且$H$不满，则把向量$x$添加到禁忌表中；如果$H$已满，则最早进入禁忌表的向量出列，向量$x$进入到出列的位置。

（5）评价函数

可以用目标函数作为评价函数，但是这样每选取一个新的路径都得去计算总时间，计算量比较大。对于上述二邻域中的邻居作为侯选集合，每一个新路径中只有两条边发
生了变化，因此将目标函数的差值作为评价函数可以极大地提高算法的效率。评价函数取为：

$$ \Delta f=(\omega_{\pi_{u-1}\pi_v}+\omega_{\pi_u\pi_{v+1}})-(\omega_{\pi_{u-1}\pi_u}+\omega_{\pi_v\pi_{v+1}}) $$

禁忌搜索算法的流程如下：

STEP1 选定一个初始解$x^{now}$以及给以禁忌表$H=\Phi$；

STEP2 若满足停止条件，停止计算；否则，在$x^{now}$的邻域$N(H,x^{now})$中选出满足禁忌要求的候选集$Can\_N(x^{now})$，在$Can\_N(x^{now})$中选一个评价值最佳的解$x^{next},x^{now}:=x^{next}$，更新禁忌表$H$，重复STEP2

3.2.2 问题（2）的求解

对于这个问题，我们的基本想法是，先根据敌方基地的分布特点将敌方的基地大体划分在三个区域之内，并使三架侦察机分别对这三个区域的敌军基地进行侦察，求取各
自的最短时间。然后对任务不均衡区域之中的点做适当调整。

我们解决问题的步骤如下：

（1）划分子图。要达到比较均衡 ，应使每架飞机的巡航时间基本相同，由于敌方目标的分布较均匀，可以将敌方目标的地理位置图分成面积基本相同的三部分。如过点（70，40）以斜率$k_1=\frac{4}{5}$作一条斜线，过点（68，48）以斜率$k_2=\frac{43}{68}$作一条斜线，并把基地所在的地区划分为三部分$G_1,G_2,G_3$。

（2）再对每个子图$G_i(i=1,2,3)$分别运用禁忌搜索算法求得其最短侦察路径$\Psi _i$，和最短侦察时间$t(\Psi _i)(i=1,2,3)$

（3）均衡任务。定义均衡率

$$ \eta=\frac{min\left\{t(\Psi_1),t(\Psi_2),t(\Psi_3)\right\}}{max\left\{t(\Psi_1),t(\Psi_2),t(\Psi_3)\right\}}*100\% \\ $$

若$\eta$接近于1，则上面划分的任务就可以接受。否则的话，根据$t(\Psi_i)(i=1,2,3)$的大小用局部搜索算法，调整$k_1,k_2$的斜率，从而调整各分区内点的个数，直至任务达到均衡。

最后的计算结果如下

两直线的斜率分别为$k_1$= 0.68 ，$k_2$ = 0.6484 。

均衡率$\eta $ = 97.57% 。
三架飞机侦察完所有目标所用的时间分别为
$t(\Psi_1)$= 20.401 小时，$t(\Psi_2)$= 20.910 小时，$t(\Psi_3)$= 20.729 小时。

​