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

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

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

中图分类号：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。