基于优先权编码的改进禁忌搜索算法求解TSP问题

王宏斌++刘娜

摘 要：传统禁忌搜索算法对初始解的依赖性较强，且常根据经验确定候选解个数和禁忌表长度，对算法效率影响较大。文章以TSP问题求解为例，采用多初始解、优先权编码、候选解个数随机化及可变禁忌长度等方法对传统的禁忌搜索算法进行了改进，在提升解的多样性的同时，加快了算法收敛的速度。

關键词：最短路径；优先权；多初始解；禁忌搜索

中图分类号：F250 文献标识码：A

Abstract： The traditional tabu search algorithm has a strong dependence on the initial solution， and often determines the candidate solution number and the tabu table length according to the experience， which has a great influence on the efficiency of the algorithm. In this paper， TSP problem solving is used to improve the traditional tabu search algorithm by using multiple initial solutions， priority coding， random number of candidate solutions and variable tabu length. At the same time， the convergence rate of the algorithm.

Key words： shortest path； priority； multiple initial solutions； tabu search

在运筹学中，旅行商问题（Traveling Salesman Problem， TSP）是经典的组合优化问题，已被证明具有NP计算复杂性，求解多采用近似算法和启发式算法。禁忌搜索是模仿人类记忆功能的一种方法，通过禁忌表封锁刚搜索过的区域来避免迂回搜索，同时，在特殊情况下，对禁忌区域中的一些优良状态进行特赦，保证搜索的多样性，达到全局最优[1]。传统禁忌搜索算法对初始解具有很强的依赖性，初始解的好坏直接影响着禁忌搜索算法的效率[2]。本文采用多初始解、优先权编码、候选解个数随机化及可变禁忌长度的方法，旨在提升算法效率。

1 禁忌搜索算法的改进

1.1 基于优先权的编码和解码

（1）优先权编码

对于具有n个顶点的网络图，首先对顶点进行编号，确定顶点集合V ，V ，V ，…，V ，再由随机函数产生一个在1～n上服从均匀分布的由n个互不相同的正整数所组成的序列作为顶点优先权PV ，PV ，…，PV ，该优先权序列就构成了本次搜索路径所参照的标准。在后续操作中，只需对换顶点对应的优先权值，便可得到新的优先权序列，确定出新的路径。

（2）解码

本文依据优先权越大越优先的原则确定路径，具体操作如下：

给定一个网络GV，E，其中V=V ，V ，…，V 表示顶点集，E表示边集，假设N V表示所有到达顶点V的点的集合，N V表示所有从顶点V出发的点的集合，从原点s开始，找到N V中优先权最大且不在已知路径结点集合中的结点V 作为搜索结点的下一个结点，令V 为V，继续上述操作，直到V 到达汇点d为止。以此确定新的路径，并求得新路径长度。

1.2 初始解的确定

本文采用多初始解的方式，在算法开始的短期迭代内，对多个初始解进行搜索，并分阶段对当前最优解评价和筛选，最终得到一个相对较优的初始解，具体操作如下：

Step1：假设随机产生了6个初始解，记为X ，i=1，2，…，6，分别进行禁忌搜索，每个解迭代25次，得当前最优解为X ，i=1，2，…，6。转Step2。

Step2：对X ，i=1，2，…，6进行比较和筛选，选出较优的3个解，假设为X ，i=1，3，5，对这3个解分别迭代50次，得当前最优解为X ，i=1，3，5。转Step3。

Step3：对X ，i=1，3，5进行比较和筛选，确定最优解，假设为X ，则以X 为初始解继续迭代。

1.3 候选解的选择

候选解个数对搜索效率影响较大。候选解数量过少，当前最优解更新的几率就很低，会过早的陷入局部最优。候选解数量过多，计算内存和计算时间也跟着增加，不利于算法的快速实现[3]。尤其在顶点数目庞大时，过多的候选解会严重影响运算速度。

传统的禁忌搜索算法将候选解个数确定为一个固定值，很难保证其合理性。为了提升算法效果，在产生候选解时，本文采用以下方式：

（1）在每次迭代时，随机选择d个顶点，放在d个位置上，依次将顶点对应的优先权与后续位置上顶点对应的优先权对换，产生新的路径，并记录对换顶点的下标和新路径的长度，构成候选解集。

（2）为了保证候选解的多样性，在大规模TSP问题中还应做如下规定：假设在第t次迭代时随机选择的顶点集合为A，在第t+1次迭代时随机选择的顶点集合为B，必须保证B中所含A的元素不得超过A所有元素的50%，否则重新选择B中元素。这样可以扩大顶点选择的范围，有效降低相邻迭代中顶点重复选择的概率，提升候选解的多样性。

下面用5个城市的TSP问题来进一步说明上述改进：

已知起止点均为0，0，5个城市的坐标为1，2，7，5，3，3，4，7，2，6，顶点编号依次为V ，V ，V ，V ，V ，初始优先权序列为：4，2，5，1，3，那么，可确定初始路径为V -V -V -V -V ，初始解为X =46。

随机选择3个顶点放在3个位置上，如V ，V ，V ，则对应优先权为4，2，5，通过交换这3个点的优先权，可产生如下候选解：

如表1所示，分别对换顶点对应的优先权，通过产生新的优先权序列确定候选解，所得候选解集为48，34，44，取X

=34，因为X

1.4 可变禁忌表长度

禁忌表长度过短，会导致加速循环，在有限次迭代中难以跳出局部最优；禁忌表长度过长，会导致计算时间过长，降低运算速度[4]。传统的禁忌搜索算法，一般根据经验确定一个固定的禁忌长度值，很难保证其合理性。本文利用C++中vector函数动态改变数组长度的性能来控制禁忌表的长度，具体操作如下：

假设初始禁忌长度为M，当前最优解连续H次未更新则禁忌长度增加a。

Step1：当前最优解连续H次未更新，禁忌长度改为M+a后继续，若在接下来的H次迭代中当前最优解更新，禁忌长度改为M后继续迭代，否则转Step2；

Step2：若当前最优解连续H次未更新，禁忌长度改为M+2a后继续迭代，直到当前最优解更新后禁忌长度改为M。

这样做是为了在搜索陷入局部最优时，通过提升禁忌表的能力来提升“爬山”能力，突破局部最优的束缚。为了控制禁忌长度的增加对运算速度的影响，限定M最多增加2a，且当前最优解一旦更新，就立即释放最早进入禁忌表的那些禁忌对象，将禁忌长度恢复至M。

2 算法设计

2.1 算法步骤

采用改进的禁忌搜索算法求解TSP问题，算法步骤如下：

Step1：确定初始禁忌长度M、迭代终止长度T，初始解个数W，初始解筛选迭代次数S，设当前最优解连续H次未更新则禁忌长度增加a，计数器L=0。

Step2：分别产生W组1～n上的互不相同的n个随机数作为顶点V …V 的优先权PV ，PV ，…，PV ，确定W个初始解，记为X ， i=1，2，…，W，并在S次迭代内筛选出最好的初始解，记为X 。令best so far为X 对应状态，tabu_list=φ，t=0。

Step3：若t=T，stop，输出X ；否则，转Step4。

Step4：产生一个随机数k，随机选择满足规定的k个顶点，分别交换各顶点对应的优先权，计算新的优先权序列下的路径长度，构成候选解集Can_NX 。

Step5：若候选解集Can_NX 中评价值最小的候选解X 在禁忌表中不存在对应的禁忌元素，且FX

Step6：若候选解集Can_NX 中评价值最小的候选解X 在禁忌表中存在对应的禁忌元素，且FX

Step7：在不受禁忌的候选集Can_NX 中选一个评价值最佳的解X ，若FX

Step8：令迭代次数t=t+1，若X 更新，令禁忌长度为M，L=0，转Step3；否则，转Step9。

Step9：令L=L+1，若L=H且禁忌长度小于M+a，则禁忌长度增加a，L=0，转Step3；否则，转Step10。

Step10：若L=H且禁忌长度小于M+2a，则禁忌长度增加a，L=0，转Step3；否则，转Step11。

Step11：若禁忌长度为M+2a，转Step3。

2.2 算法流程图

改进后的算法步骤可用图1所示的流程图表示：

3 实例分析

以20个城市的TSP问题为例，城市编号1～20，坐标依次为：25，90， 54，40， 46，29， 31，26， 3，58， 74，77， 48，62， 83，77， 29，9， 89，88， 43，51， 62，20， 38，98， 62，3， 33，54， 88，7， 44，70， 79，40， 89，97， 18，38。设起止点0，0，编为0号。

确定初始条件：禁忌长度M=3，终止迭代步数T=1 000，每次迭代时，当前最优解未更新次数限制值H=100，禁忌长度增量a=2，候选解个数在10～20之间随机产生。初始解个数为6，初始解筛选迭代次数为300。

应用改进后的禁忌搜索算法求得的近似最优路径为：0-9-15-17-1-5-18-16-10-19-8-4-2-12-14-11-3-6-7-13-20-0。近似最优解为809。改进算法与经典禁忌搜索算法求解该TSP问题的收敛图如图2、图3所示：

在有限次迭代内当前最优解比较如表2所示：

图2与图3比较后可知，对传统禁忌搜索算法进行上述改进后，算法收敛速度及鲁棒性都得到了相应的提升，具有了更强地跳出局部搜索的能力。由表2可知，改进算法先于傳统算法达到全局最优，且在1 000次迭代中，改进算法用时相对较少，进一步说明了改进的可行性。

4 结 论

传统的禁忌搜索算法对初始解具有很强的依赖性，较差的初始解对算法的效率影响巨大。本文采用多初始解的方式，在短期迭代内对初始解进行筛选，获得较好的初始解后再继续迭代，降低了初始解的影响。其次，通过优先权编码、随机选择候选解及可变禁忌长度的方式对传统禁忌算法做了改进，在改进候选解生成方式的同时，让候选解个数与禁忌表长度在迭代过程中动态改变，参数设置更加合理。通过实例论证，可知改进后的禁忌搜索算法在求解TSP问题时收敛速度更快，具有更好的寻优能力，是一种有效的算法。

参考文献：

[1] 王凌. 智能优化算法及其应用[M]. 北京：清华大学出版社，2001：67-68.

[2] 贺一，刘光远. 禁忌搜索算法求解旅行商问题研究[J]. 西南师范大学学报，2002（3）：41-45.

[3] 任小康. 基于禁忌搜索算法的旅行售货员问题[J]. 佳木斯大学学报，2005（3）：343-345.

[4] 温万惠，刘光远. 一种基于可变禁忌长度的多用户检测方法[J]. 信号处理，2005（4）：389-391.

[5] 李国勇，李维民. 人工智能及其应用[M]. 北京：电子工业出版社，2009.

[6] F. Glover. Tabu Search： A Tutorial[J]. Special issue on the Practice of Mathematical Programming， 1990，20（1）：74-94.

[7] 张洪艳. 一种改进的多初始解禁忌搜索算法[J]. 科学信息（学术版），2008（34）：193.

[8] 徐英钟，高震，李波. 基于禁忌搜索的蚁群算法求解旅行商问题[C] // 第四届中国智能计算大会论文集，2010.

[9] 赵清江，邵之江，钱积新. 用蚁群算法求解类TSP问题的研究[J]. 铁道运输与经济，2003（2）：49-51.

[10] 彭茂. 一种求解TSP问题的改进禁忌搜索算法[J]. 计算技术与自动化，2012（1）：78-81.