唐文秀

（华北电力大学,北京 102206）

1 概述

在数学领域中,TSP 问题(Traveling Salesman Problem,即旅行商问题),被广泛视作一个典型的组合优化问题[1]。该问题一般讲述的是为一个旅行商寻找最短路径,该商人计划在n 个不同的城市为产品作宣传,并且每个城市只能经过一次,从初始城市出发,遍历所有目的城市且不重复后,又回到初始城市。显然,该问题属于组合优化问题,在生活中非常普遍,很多实际工程应用问题的实质就是旅行商问题,例如某旗舰店的商品物流路线、物资分配、车辆调度、电路布线、产品生产安排问题等等[2-4]。因此,研究TSP 问题不仅具有重大的实际意义,也具有相当高的工程价值。

当城市数量较少时,理论上可以通过穷举法来列举出最优方案,然而当城市数量较多时,所有路线之和将呈指数增加,因此求解过程非常复杂而且很难找到最优解。目前,求解TSP 问题的算法大致可划分为两类,分别是确定性算法和智能优化算法[5]。确定性算法通常是指能利用数学公式解出具体的某个数值,且该结果即为最优解,例如线性规划、动态规划、完全枚举等方法,然而该类算法只适用于小规模算例求解,因此,考虑到现实应用情况,在规模较大时,人们常常选择目前广受关注的智能优化算法,例如遗传算法、粒子群算法、模拟退火算法、禁忌搜索算法、免疫算法以及人工神经网络[6-9]等等。本文主要通过遗传算法和禁忌搜索算法两种算法进行混合求解,结合两种算法的优势,对TSP 问题进行优化求解,提高解的质量。

2 改进禁忌搜索算法

1986 年,Fred Glover 教授提出了禁忌搜索算法（Tabu Search,简称TS 算法）[10],指出该算法的局部搜索能力非常强,并且也能避免算法陷入局部最优,从而找到全局最优解,是一种全局迭代寻优算法。多年来,该算法也以其灵活的记忆特性和特赦准则,受到了众多学者的青睐。

所谓禁忌,是指禁止重复操作,类似于模拟人的思维模式,如果该区域已经搜索过,则下次搜索时可以通过禁忌表来进行记录,避免重复低效搜索,但也并非完全隔绝,对于更优的解,也可以通过特赦准则对其进行释放,改善解的质量,避免遗漏。

在TS 算法中,关键的参数主要有禁忌表、禁忌长度、特赦准则、候选集、适配值函数、终止准则等。禁忌表是算法的核心所在,用来记录已经搜索过的地方,避免在搜索中陷入循环和局部最优。禁忌长度是指放置在禁忌表中的对象的禁忌周期,每进行一次迭代,周期就减少一次,直到周期为0 时即可解除禁忌。特赦准则是指在迭代过程中,出现了比历史最优还要更优的解,尽管此时该解对应的对象处于禁忌表中,且禁忌长度不为0,也可以将其特赦出来,解禁该禁忌对象。候选集主要从领域解中产生,可以随机选择几个领域解作为候选解,或者选择表现较好的作为候选解。适配值函数是指对当前搜索过程的评价,在TSP 问题中为总的行程距离大小。终止准则指算法的结束条件,通常设置为算法执行到某一个迭代次数,或者目标函数值小于某个误差。

TS 算法的主要搜索步骤如下所示：

（1）初始化禁忌表、禁忌长度,随机产生初始解,定义领域映射模式；

（2）判断初始解是否满足终止条件,若满足,则输出最优解,结束搜索；若不满足,则继续下一步；

（3）根据当前解的领域映射模式生成若干个邻域解,并从中选出若干候选解,计算适配值,保留较好的候选解进行下一步判断；

（4）判断候选解是否满足特赦准则,若满足,则将其特赦出来,并作为当前最优解,同时将对应的对象放入禁忌表,并修改表中各个对象的周期长度；若不满足,则选出在候选解中没有被禁忌的最优解作为当前最优解,对禁忌表进行重复前一步操作；

（5）当满足终止准则时,例如迭代次数已达到最大,此时结束搜索,输出最短路线。流程如图1 所示。

图1 禁忌搜索算法流程图

虽然TS 算法具备着强大的局部搜索能力和记忆功能,但是也存在一些不足,例如,该算法对初始解具有很大的依赖性,即当初始解较好时,能够迅速找到最优解,当初始解不好时,则直接制约了禁忌搜索的速度,因此,为了克服该问题,本文提出结合遗传算法进行改进,首先利用遗传算法产生较好的初始解之后,再把该解作为禁忌搜索算法的初始解来进行迭代寻优,而非随机产生初始解。

遗传算法的主要步骤为：第一步进行初始化操作,计算每条路线的适应度值及路径长度；第二步,以概率的方式来选择新的路线方案；第三步,对选择的路线进行交叉操作,随机交叉某两座城市的坐标,确保每个城市有且仅经过一次；第四步,进行变异操作,即随机交换某一条路线的一对城市坐标,得到新的路线,然后再进行下一次迭代寻优；最后判断是否满足终止条件,若满足则结束搜索,输出最优路径及最短距离,若不满足,则继续进行迭代寻优。遗传算法流程图如图2 所示。

图2 遗传算法流程图

3 算例仿真

3.1 改进前结果

假设城市规模N=31,每座城市坐标如表1 所示。设置禁忌长度L=22,候选解的个数M=200,求出任意两个城市的间隔矩阵,定义领域映射模式为2-opt,开始禁忌搜索操作,直到满足终止条件。

表1 31 座城市的坐标

图3 31 座城市分布

在该问题中,分别设置迭代次数为100、300、500、800 和1000,在不同的迭代次数下,重复运行5 次程序,得到的结果如表2 所示。

表2 不同迭代次数的实验结果

从仿真结果可以看到,当迭代次数逐渐增大时,计算的结果逐渐减小,并逐渐趋于优化最短距离,在该案例中,当未加入遗传算法进行改进时,在迭代次数为1000 时,优化最短距离为16126,最优路径和适应度进化曲线如图4、5 所示。

图4 改进前优化最短距离

图5 改进前适应度进化曲线

3.2 改进后结果

先通过遗传算法进行求解,设置群体数量NP=200,染色体基因维数N=31,最大进化迭代次数G=1000,产生初始种群,计算每个个体的适应度值和最短距离,再通过选择、交叉、变异操作进行下一次遗传,直到迭代次数达到最大值,将此时得到的最短路线方案作为初值传给禁忌搜索算法。在实验中,分别设置迭代次数为100、500 和1000,在不同的迭代次数下,重复运行5 次程序,得到的结果如表3 所示。

表3 改进后结果

在加入遗传算法后,可以看到,结果得到了极大的改善。当迭代次数为1000 时,此时遗传算法已经越来越接近最优值,再结合禁忌搜索算法进行寻优时,可以看到改进后的结果明显优于改进前的结果,此时得到的最短距离为15382,相比于改进前,缩短了744,路线方案如图6 所示,适应度进化曲线如图7 所示,蓝色的线条表示仅采用禁忌搜索算法求解的结果,红色的线条表示结合遗传算法进行改进后的结果,可以看出,改进后的适应度值明显低于改进前的值,说明了算法的有效性。

图6 改进后优化最短距离

图7 适应度进化曲线对比

4 结论

本文简要阐述了禁忌搜索算法的基本思想、求解步骤以及实现过程等,基于MATLAB 编程了改进前的禁忌搜索算法和改进后的禁忌搜索算法,并对比了两种方式对TSP 问题的求解的结果,实验结果表明,改进前的禁忌搜索算法能够找到相对最优解,但需要较大的迭代次数,且初始解较差时,求解速度缓慢,结果不够稳定。通过遗传算法进行改进后,结果有了较大的提高,从实验数据可以看出,在改进前,当迭代次数为1000 时,优化最短距离为16126,改进以后,优化最短距离为15382,缩短了总的行程距离,得到了更优的路线方案,实验结果得到了明显的改善,算法有效并且可行。