贪婪随机自适应灰狼优化算法求解TSP问题

高珊 孟亮

关键词： GRAGWO算法; 贪婪随机自适应算法; 灰狼优化算法; 群体智能; 旅行商问题; 组合优化

中图分类号： TN911?34; TP393                 文献标识码： A                    文章编号： 1004?373X（2019）14?0046?05

Greedy randomized adaptive grey wolf optimization algorithm for solving TSP difficulty

GAO Shan， MENG Liang

（College of Information and Computer， Taiyuan University of Technology， Taiyuan 030024， China）

Abstract： A greedy randomized adaptive grey wolf optimization （GRAGWO） algorithm is proposed to solve TSP difficulty. GRAGWO algorithm is based on the greedy randomized adaptive search procedures （GRASP）， which adopts construction phase of GRASP to generate the initial solution and the grey wolf optimization （GWO） algorithm is used in the local search phase to optimize its searched result. GWO algorithm cannot be directly used to solve discrete problems because it is easy to fall into local optimum， resulting in lower convergence rate in the later period. According to the characteristics of TSP， the grey wolf coding mode is redefined to solve the TSP problem， which is easy to form a local optimal path and leads to the decline of population diversity with the increase of iterations. Several groups of TSP problems in different scales in TSPLIB database were used as experimental cases. The GRAGWO algorithm is compared with other bionic algorithms in this paper. The results show that GRAGWO algorithm has relative advantages in the aspects of solving accuracy， stability and large?scale urban problems.

Keywords： GRAGWO algorithm; greedy randomized adaptive search procedure; grey wolf optimization algorithm; swarm intelligence; traveling salesman problem; combination optimization

0  引  言

旅行商問题是一个典型的组合优化问题，该问题假设一位旅行商需访问n个城市，城市之间的间距是固定的，旅行商从一指定的城市出发，且不重复的访问剩余城市，最后回到起始城市，在所有的回路中求出最短路径[1?2]。TSP问题应用非常广泛，例如绘制基因组图谱、望远镜、X射线、操控工业机械、安排生产作业任务等。TSP问题是著名的NP完全问题，求解TSP问题有精确算法和启发式算法两种。精确算法能保证在指数级次数中找到最好结果，但其本身非常复杂，且对计算机要求较高;启发式算法普遍简单，运行时间短，例如模拟退火算法、遗传算法、局部搜索算法等，但易陷入局部最优。

贪婪随机自适应搜索算法（Greedy Randomized Adaptive Search Procedures，GRASP）是一种求解组合优化问题的启发式算法[3]。灰狼优化算法是2014年由Mirjalili等人提出的启发式智能算法。该算法模拟自然界灰狼等级制度和狼群搜索猎物过程，利用灰狼种群内部等级制度，实现对目标猎物函数的优化过程[4]。该算法具有优良的收敛稳定性与较强的全局探索能力。本文利用GRASP算法寻求初始解，从而加速灰狼算法的收敛速度，且提高其局部搜索能力。实验表明，两种算法的结合可以高效提高求解速度与解的质量。

1  算法原理

1.1 贪婪随机自适应搜索算法

GRASP算法分两个阶段，构造阶段和局部搜索阶段[3]。在构造阶段，初始化可行解S和候选集C，并对候选集的每一个元素进行评估，判断是否可加入限制候选列表（Restricted Candidate List，RCL）。每次从RCL中随机选取一个值与可行解S进行比对，更新RCL的元素，并对包含的所有元素进行再次评估，直到满足条件时结束。

RCL规模大小也会影响此算法性能，规模过大会生成很多差别的解。RCL通常采用静态固定法和动态调整法来调整列表规模，体现了GRASP算法自适应功能。

在第一阶段会得到质量不高的可行解，因此在第二阶段，可行解需要以持续不断的迭代方式进行局部搜索，以求得最优解。若局部新优解S比目前的优解S*更优的话，就更换S*，直到找到最优解。选择相邻解在局部搜索阶段有两种方法：最优适应和首次适应。最优适应在所有相邻解被搜寻后，将更优相邻解替换为可行解;首次适应是当搜索到比可行解更优相邻解时进行替换后再次局部搜索，当循环达到满足给定的迭代次数时终止。

1.2  灰狼优化算法

GWO算法模仿灰狼的社会等级制度和猎食行为，并控制搜索方位。灰狼优化算法已被广泛应用并不断改进，主要体现在约束函数优化、多级阈值图像分割、路径优化等领域[4]。灰狼等级从高到低为α，β，δ，ω这四种等级，每一个等级表示一个可能解。α狼是狼群头领，拥有最高决策权，代表最优解;β，δ，ω狼分别代表优解、次优解、候选解。狼群每次捕猎过程是由各等级的相互协作完成，由搜寻、包围、攻击3个步骤组成。

1.2.1  搜寻过程

该算法通过随机数扰乱判断与猎物之间的距离，以此初始化种群。

[D=C?Xp（t）-X（t）] （1）

[C=2r] （2）

[r=rand（0，1）] （3）

式中：t为当下迭代次数;X（t）为灰狼的位置;[Xp]（t）为第t次迭代中猎物位置;D为灰狼与猎物的间距;r为0～1之间的任意随机数。

1.2.2  包围过程

在灰狼包围猎物的过程中，通过狼之间不同距离和猎物距离，建立灰狼与猎物的关系模型。

[X（t+1）=Xp（t）-AiDi] （4）

[A=2ar-a] （5）

[a=2-ttmax] （6）

式中：A表示包围步长;[tmax]表示最大迭代次数，控制参数a随着算法迭代次数的增加而线性递减。其中，当[A]≥1时，表示灰狼会进行全局搜索;而[A]<1时，意味灰狼将在附近搜索。A，C的随机初始化保证了灰狼在搜索过程中易达到全局最优位置。

1.2.3  位置更新（攻击）

通过α，β，δ，ω更新位置信息，判断目标猎物位置并对猎物攻击。产生新位置关系后，对狼群中的元素进行边界控制，完成一次迭代。此阶段狼群位置更新如图1所示。

[Dα=C1Xα-XDβ=C2Xβ-XDδ=C3Xδ-X] （7）

[X1=Xα-A1DαX2=Xβ-A2DβX3=Xδ-A3Dδ] （8）

[X（t+1）=（X1+X2+X3）3] （9）

式中：[X1]，[X2]，[X3]表示α，β，δ狼的位置;[A1]，[A2]，[A3]表示3个随机数;X表示灰狼攻击猎物的最终位置。灰狼通过速度变异、搜索半径变化、位置更新等策略，并借助参数A和C的随机变化、较强的全局能力，使得灰狼在全局范围亦可搜寻到最优解或次最优解。重复进行上述步骤，直到达到终止条件输出最优解。综述，灰狼捕食过程是可以抽象成连续空间上的组合优化模型。

2  改进策略

GWO循环初期具有较快的收敛速度，狼群位置变化较大，全局搜索能力较强，但随迭代次数的增多后，位置变化波动渐少，易导致局部最优。本文提出的改进算法是将GRASP和GWO相结合，通过GRASP算法中构造阶段的贪婪性与随机性得到初始解来得到GWO中质量较高的初始群体，再通过GWO对其进行第二阶段操作，搜索并逐步替换最优解。

2.1 GRASP算法初始化种群

作为改进算法的第一阶段，随机贪婪方法能够得出可行初始解。在构造阶段的每一次迭代生成的RCL大小和表内元素分别被参数α和贪婪函数决定，其中α∈{0，1}。参数α决定算法的贪婪程度，当α=0时是完全贪婪搜索过程，而α=1时是简单的随机过程。在贪婪随机构造阶段每一次迭代过程中，从RCL列表中随机选择一个元素加入当前局部解中，随后更新RCL列表，重复该过程，直到满足贪婪随机构造阶段可行解的值，该值为改进算法初始解。随着构造阶段的迭代，所有元素之间的关系结构不断优化，得到更优解。

2.2 目标函数构造

作为改进算法的第二阶段，灰狼优化算法的求解范围是一个二维的连续空间，需界定自变量的取值范围与目标函数表达式。TSP问题引入灰狼优化算法后，假设灰狼的种群规模为N，城市个数为D。在D维的城市搜寻空间中，第i（i∈N）只灰狼的位置[Xi]被定义为一组正整数序列，N只灰狼在D维空间中搜寻猎物，即搜索空间域P是一个矩阵：

[P=X11    X21    …    Xj1    …    XD1X12    X22    …    Xj2    …    XD2?    ?     ?   ?     ?    ?X1i    X2i    …    Xji    …    XDi?      ?       ?    ?      ?   ?X1N    X2N    …    XjN    …    XDN] （10）

式中，[Xji]（i≤N，j≤D）指在搜索空间P中，第i只灰狼在第j维度上的位置，矩阵首行为第一只灰狼在搜索空间中的位置序列，尾行表示第N只灰狼的位置序列。

TSP问题中实际距离矩阵W可表示为：

[W=d（1，1）…d（1，N）???d（N，1）…d（N，N）] （11）

式中：N指城市数量;[d（i，j）]指第i个到第j个城市之间的距离，其中[d（i，i）]（1≤i≤N）均为0。

当求解城市数量为D，狼群数量为N时，TSP问题求解目的为求取一个最优狼群位置P，使得目标数值f最小：

[f=min Pd（i，j）， （i，j）≤D，（i，j）∈N，i≠j]

式中：i和j表示城市序号;[min P]表示最优的种群位置;[d（i，j）]表示距离矩阵和。

该函数读取每个灰狼位置矩阵P中，对位置序列与相对应距离矩阵W的距离累加求和。例如，从第1个城市前往第6个城市，假设位置为P=[1，4，6，2，3，5]，则表示为从1号城市出发，依次经过4，6，2，3，5号城市，最终回到1号城市。此时灰狼种群从距离矩阵W读取距离进行目标函数值的计算，在距离矩阵W中对应的距离分别为[d1，4]，[d4，6]，[d6，2]，[d2，3]，[d3，5，d（5，1）]，对于P=[1，4，6，2，3，5]顺序下的目标函数值f的计算方法为：

[f=sumd1，4，d4，6，d6，2，d2，3，d3，5，d5，1]

不同的灰狼随机初始化会产生不同的解向量，通过函数判定其目标函数优化状况，若解比之前解更优则替换为更优解，并作为本只灰狼当前迭代最优解;反之保持不变，继续进行下一行判断，直到所有灰狼解向量优化全部完成。

随后保存所有行中目标函数值最小值，此为一次完整循环，当所有完成循环次数，即可输出所有循环之后的最优解。

3  实验结果

本算法在TSPLIB中38个欧几里得样本问题上进行测试，问题范围内拥有大量城市节点（16～2 392个），例如表1中的第2个实例为Eil51，表示有51个节点。将RCL的长度设置为30，50，100，150，且灰狼的个数根据城市数变化。

例如：当城市数量小于100，那灰狼个数需设置为城市数量的[12];当城市数量在100～1 000，灰狼个数设置为城市数量的[13];当城市规模大于1 000，将灰狼个数设置为城市数量的[14]。当城市节点数少于1 000，迭代次数根据城市数设置在10～100之间;当城市节点数超过1 000的实例，该算法只测试100次迭代;当城市节点数大于1 200的实例，该算法运行200次迭代。

表1第4列表示修改过的GRASP算法所找到的最佳解决方案，第5列显示了本文算法产生解的偏差，第6列显示本文算法所得到解的平均值。相对偏差，即p=100[c-coptcopt]，其中c表示通过本文算法找到最优解路径长度，[copt]是已知最优解。

对表1分析，在大多数情况下，当该算法节点数量达到299个时即可获得已知最优解;当实例在节点数量为299～2 392个之间时，解决方案的偏差在0.01%～1.0%之间。根据这38个实例测试，得出已知最优解共有22个，其中14个解的偏差在0.01%～0.65%之间（占总测试数比的36.8%），实例中只有一个产生解的偏差为1.00%。

表2显示了在RCL不同长度（30，50，100，150）从51～442个节点的10个实例实验中，分别得出的最优解。不同长度的RCL会影响结果，在Rand75实例中全为最优解。在D198实例中，不同长度的RCL生成了不同最终解。当RCL长度为30时，所求得最优解与已知的最优解的差距随着节点数增大而增大，当节点数小于100情况下均找到最优值。随着节点数增大，RCL长度在100和150找到最优解;当RCL长度为100时，其中40%达到已知最优解;其余与已知最优解最大偏差为2.7%;当RCL长度为150时，其中也有40%能达到已知最优解，与已知最优最大解偏差为2.6%。随着节点数的增多，总体上RCL的长度较长易找到最优路径;而节点数较少，RCL的长度较短时，更易在更短的时间与更少的迭代内找到最优路径。

表3显示了TSPLIB中的实例在4种不同算法下的求解结果：蚁群算法（Ant Colony Optimization，ACO）[5]，自适应离散型布谷鸟算法（Adaptive Discrete Cuckoo Search，ADCS）[6]，遗传算法（Genetic Algorithm，GA）[7]，以及本文所改进的算法对节点数量在51～150之间的实例进行实验。通过对结果分析，正如预期，相较于另外3种启发式算法，所得的结果仍存在一定差距，但运用本文改进算法能得到更好的最优解。

4  结  语

本文改进算法是利用GRASP与GWO相结合的一种相对其他算法精度更高、搜索性能更好、更易克服陷入局部优化的求解TSP的新算法。在多数情况下，利用本文改进算法通过对TSPLIB数据库中多个实例研究，证明其结果等同于已知最優解;有时所得解不是最优解，但相对同条件下其他算法所得到的解更近乎为最优解。虽然本文改进算法在一定条件下显得相对高效，但还存在许多问题，尤其在处理大型TSP问题时，会出现运行效率较低的情况。今后将继续改进算法以解决以上问题。

参考文献

[1] NENAD M， RACA T， DRAGAN U. An efficient general variable neighborhood search for large travelling salesman problem with time windows [J]. Yugoslav journal of operations research， 2013， 1（23）： 19?30.