邓 健

（湖南科技学院 电子与信息工程学院，湖南 永州 425199）

1 意义和目标

在组合优化算法上，禁忌算法在解决问题的效果上是比较优秀的。当然，禁忌搜索（Tabu Search，TS）算法在很多方面都取得了巨大的成功，包括神经网络、电路设计、组合优化、机器学习、生产调度等应用。另外，禁忌算法在调度问题中，其组合优化问题至今仍是其应用最广泛而成功的一个领域。TS具有相比遗传算法（Genetic Algorithm，GA），模拟退火（Simulated Algorithm，SA）等优化算法更强的局部搜索能力，但它对初始解具有较强的依赖性，近年来仍有许多有关TS算法的改进方法相继提出，因而对基于TS的TSP问题的研究仍然有一定的意义。

本文利用启发式信息求得一个较好的初始解，然后实现基本的TS算法，加深对TS算法的理解，并对其改进方向进行探讨。

2 算法理论分析

2.1 局部邻域搜索

局部搜索算法的提出，最基本的思想是在贪心算法的基础上，采用爬山启发式的思想。使用局部搜索算法解决问题，一般具有一个原始的解，从这个原始的解开始，可以把领域函数放到所谓的领域中进行不断地查询，直到查询到比当前的解更好或更优的解，那么就替换当前的解。这个过程是一个循环的过程，当要结束当下循环的时候，就以当下的解作为最后的解。由此可以看出，容易上手及容易推广是局部搜索算法的最大的优势，而它最大的劣势在于，求解的过程完全依赖于解的领域情况及其解的原始值，所以，一旦当领域情况失真或者原始的值出问题了，局部搜索算法为了实现获得最终的解，必须采用TS的方式从而逃离局部最优获得全局的最优解。

2.2 TS原理

TS的基本原理需要从几个基本文字出发进行理解，这些基本文字主要是指：原始值、破禁算法、邻域、禁忌表、选择策略、候选解、适配值算法等。禁忌搜索方法是从一个问题的最上层的解决方案出发提出的，用什么样的参数是由场景决定的。

2.2.1 初始解和适值函数的构造

初始解可以随机给出，也可以事先使用其他启发式等算法给出一个较好的初始解，由于禁忌搜索算法主要是基于邻域搜索的，初始解的好坏对搜索的性能影响很大，所以应该采用启发式信息或其他方法找出一个可行解作为初始解。本文中采用启发式算法求得较好的初始解，即从第一个城市出发找与其距离最短的城市，然后继续找与第二个城市距离最短的城市，依此寻找下去且满足各城市只寻访一遍，最终回到城市1。

2.2.2 邻域函数和邻域移动

邻域移动是从一个解产生另一个解的途径。它是保证产生好的解和算法搜索速度的最重要因素之一。邻域移动定义的方法很多，适当的移动规则的设计，是取得高效的搜索算法的关键，对于不同的问题应采用不同的定义方法。通过移动，目标函数值将产生变化，移动前后的目标函数值之差，称之为移动值。在本文中使用的邻域函数是交换两个城市的位置得到交换后路径长度，移动值是负的，则称此移动为改进移动，否则称作非改进移动。最好的移动不一定是改进移动，也可能是非改进移动，这一点就保证搜索陷入局部最优时，禁忌搜索算法能自动把它跳出局部最优。

2.2.3 禁忌表

禁忌表在记录位置变化的方法上，一般来说，有3种形式：首先，状态的基本参数和状态的前后规律是需要记录下来的；其次，位置的状态分量及其状态分量的变化也是需要记录下来的；最后禁忌表中的最后终值也是需要记录下来的。

禁忌表另一个作用是通过调整禁忌表的大小使搜索发散或收敛。初始搜索时，为提高解的分散性，扩大搜索区域，使搜索路径多样化，经常希望禁忌表长度小。相反当搜索过程接近最优解时，为提离解的集中性，减少分散，缩小搜索区域，这时通常希望禁忌表长度大。为达到这样的目的，最近越来越多的人允许禁忌表的大小和结构随搜索过程发生改变，即使用动态禁忌表，实验结果表明了动态禁忌表往往比固定禁忌表能获得更好的解。本文仍然使用长度固定不变的禁忌表。

3 算法设计

3.1 初始化

城市数量N，随机给出一个初始解或者利用其他启发式算法求得一个较好的初始解，本文利用后者，从距离矩阵左上角第一个城市出发选择最短距离的城市，然后以该城市为出发点继续寻找距离该城市最短的城市，直到所有城市都寻访一遍后回到第一个城市，初始化禁忌表为空。

3.2 选择和破禁

IF 候选解中最好解＞历史最优解

更新历史最优解和当前解；

更新禁忌表；

ELSEIF 候选解中最好解在禁忌表中且不满足破禁函数

找不在禁忌表中的最优解；

ELSE 不在禁忌表中且不满足破禁函数

更新当前解； \跳出局部搜索

END

4 实验分析

4.1 相关工作简介

有学者提出C-TSP组合优化问题，即我国31个省、市、自治区首府间的距离表和归一化距离表后，国内外学者对该问题进行了大量的研究。由于该问题属于中大规模的组合优化问题，因此，都用对该问题的解的情况来分析说明自己所提出的组合优化方法的有效性，目前一些改进的算法求得的最优解是15 404，以下列出几种其他算法获得的解以作对比：

（1）贪心算法最短巡回距离为17 102；（2）在Hopfield神经网络方法之上，加上三角形两边用一边代替的约束条件，求得最短巡回距离为16 262；（3）几何算法，最短巡回距离为15 492。

4.2 实验结果

实验的运行环境为:操作系统Windows XP，CPU为Intel（R）Pentium（R） 4 2.40 GHZ，1.00 GB内存。

首先利用启发式信息求得的初始解为：1→3→4→5→6→24→25→26→28→29→30→22→21→20→19→14→18→12→1 1→13→2→15→16→17→10→23→7→8→9→27→31→1，其标号代表的具体城市见文献，初始距离为19 616.01。

其次对禁忌表长度和迭代次数两参数的变化进行探讨得到如表1所示的结果。

从表1中可以看出，当禁忌表长度不变时，一开始，随着迭代次数的增加，最优解有所改进，当迭代次数达到某一值后，解就基本不变了，若继续迭代下去解不变，这说明此时要么已经达到最优解，要么陷入了局部最优而未能跳出局部邻域。从表1中看出，当禁忌表的长度过短时，波动性较大，较难形成稳定的最优解，因而，开始时，随着禁忌表的长度的增加可以改进解，但是到达一定值后过大则容易陷入局部最优。

表1 禁忌表变化

通过上面的实验深刻地体会到禁忌搜索算法对初始解的依赖性，禁忌表和迭代次数的调整都极为关键，本文算法最终获得的最优解值是15 497.54，显然比以上所列的贪婪算法等要优，最优结果如下所示。

最优路径标号：1→6→24→23→25→26→27→31→28→3 0→29→22→21→20→19→18→14→15→16→13→2→11→12→17→5→4→10→3→7→8→9→1。

最优路径为：

北京→呼和浩特→银川→西安→兰州→西宁→乌鲁木齐→拉萨→成都→昆明→贵阳→南宁→海口→广州→长沙→武汉→南昌→福州→台北→杭州→上海→南京→合肥→郑州→太原→石家庄→济南→天津→沈阳→长春→哈尔滨→北京。

5 结语

本文旨在理解基本禁忌搜索算法，在基本禁忌搜索算法上作了简单的改进，利用启发式信息得到一个较好的初始解，在候选解的产生上考虑到全部交换，对禁忌表长度和迭代次数的变化进行讨论等，由于未作更大的改进，进而未能得到目前的最优解，但是比传统的一些基本算法要优，后续工作笔者将对其进行改进，譬如利用启发式信息获得一个更好的初始解，利用更好的邻域函数，限定迭代多少次解未得到改进便输出等。另外，虽然禁忌搜索算法较为稳定了，但是在面对大规模的数据集之下，运行效率低，这将是笔者下一步进行的研究工作。

[参考文献]

[1]宁桂英，曹敦虔，周永权.求解TSP问题的离散型差分进化算法[J].计算机与数学工程，2017（11）：2136-2142.

[2]曹思聪，夏辉，孙可.基于蚁群算法的TSP问题分析[J].鞍山师范学院学报，2017（2）：49-53.

[3]汪定伟，王俊伟，王洪峰，等.智能优化方法[M].北京：高等教育出版社，2008.