改进快速单亲遗传算法解均衡多旅行商问题

朱红瑞 谭代伦*

（西华师范大学数学与信息学院，四川南充 637000）

多旅行商问题（Multiple Traveling Salesman Problem,MTSP）是经典旅行商问题（TSP）的一类重要扩展［1］，它是指有多个旅行商从某个指定的起点出发，去访问给定的一组城市，要求每个城市只被一个旅行商访问，且只访问一次，求使得总成本最低的最佳行走方案，其中成本可以是路程、时间等。MTSP问题有很多实际应用场景，比如印刷机的调度［2］、印刷前广告的调度［3］、银行工作人员的调度［4］、校车的路线［5］、卫星测量系统的设计［6］等现实问题。随着快递和外卖配送行业的不断发展，需要最小化各旅行商的最长路线，使其承担的工作任务尽量均衡，避免资源的浪费，所以，均衡多旅行商问题（Balanced Multiple Travelling Sales⁃man Problem,BMTSP）也逐渐得到广泛的关注与研究，如何快速且有效地解决该问题仍然具有很高的实际应用价值。

在求解多旅商问题时，大多数研究者常常只达到了总路程最短的目标，目前，在总路程最短的基础上使得每个旅行商的路程均衡的相关研究成果还不算丰富。刘伟民［7］以最小化各旅行商最长路线这一负载均衡为优化目标，提出了一种结合构造机制和局域搜索的改进蚁群算法，提高了算法性能，得到更优结果。文卡塔斯（Venkatesh）和辛格（Singh）［8］通过借鉴不同的生物智能，分别提出了不同程度上改进的蜂群算法和杂草入侵算法，并且在多数实例上得到了较优的计算结果。胡士娟［9］在遗传算法中利用繁殖机制来产生种群并进行遗传操作；同时提出一种混合局部优化算子来求解平衡的MTSP 问题，提高了算法的搜索效率和收敛精度。

在上述群智能算法中，由于遗传算法（GA）具有通用性高、鲁棒性强、求解性能稳定等优点，被广泛应用于求解MTSP 问题［10］，但为了避免不可行解的出现，常采用更复杂的部分映射交叉、顺序交叉、循环交叉［11］等特殊的交叉算子，导致遗传过程复杂，计算效率不高。而单亲遗传算法（PGA）取消了交叉算子，代之以仅在一条染色体上操作的基因重组等遗传算子，即通过单亲繁殖来产生后代，遗传操作得以简化，避免了“早熟”问题［12］，提高了计算效率。李茂军［13］等在2001 年也研究证明单亲遗传算法的基因重组算子隐含了交叉算子的功能。随着单亲遗传算法受到越来越多的关注，许多学者也将其应用于更多的实际生活中解决相关的组合优化问题［14-16］。

基于以上分析，本文提出一种改进的快速单亲遗传算法（Improved Fast Partheno-Genetic Algo⁃rithm,IFPGA）来求解BMTSP 问题，将已经被实验证明求解TSP问题有效的基因移位、倒序、交换等变异算子与单亲遗传策略相结合，增强种群寻优能力，同时引入最近邻点的局部优化策略，以加快种群的收敛。

1 BMTSP问题及数学模型

一般地，均衡多旅行商问题（BMTSP）可以描述为：有m 个旅行商，从某个指定起点出发，需要去访问给定的n 个城市并回到起点（城市之间的距离已知），每一个城市必须且只被一个旅行商访问一次，求使得路程最长的旅行商回路尽量短的均衡最佳行走路线。

基于图论知识，BMTSP 问题中所有旅行商访问全部城市构成一个图，记为

其中V为顶点集，v0为旅行商共同的起点、v1,…,vn为要访问的n个城市；E为边集，eij为城市vi到城市的边，记为。

则均衡多旅行商问题（BMTSP）的数学模型可表示为：

式（1）表示使个m旅行商的回路最大最小化；式（2）和式（3）表示m个旅行商都从指定的起点城市出发并回到起点，使得旅行路径成为闭回路；式（4）表示每个城市只被一个旅行商访问且只访问一次；式（5）用于约束每一个旅行商不产生子回路［17］；式（6）表示每一个旅行商至少访问D个城市，其中D为工作量均衡控制常量。

2 改进快速单亲遗传算法设计

本文IFPGA算法着重对单亲遗传策略进行了改进，并引入了最近邻点局部优化策略，使算法的收敛速度和求解精度得到了明显提升。下面简要说明IFPGA算法的各个步骤。

2.1 基因编码方案

基因编码方案是遗传算法的基础，决定了种群个体染色体基因的结构和表现形式，对遗传交叉与变异操作都有重要影响。

遗传算法求解旅行商问题（TSP）普遍采用以城市序号构成的路径节点序列编码。对多旅行商问题（MTSP），还需要将路径节点序列编码拆分为多个片段，以对应于多个旅行商各自的访问路径。拆分方法一般是随机生成多个断点。为此，本文算法也采用路径节点序列编码和断点相结合的两段式染色体编码。

染色体的第一部分称为路由编码段，是所访问的n个城市v1,…,vn的任意随机序列；第二部分称为断点编码段，其作用是将路由编码段随机划分为m个片段。这m个片段即是m个旅行商各自需要访问的城市序列，每个片段包含的城市数应不少于常量D，使得每个旅行商所访问的城市数大致相等，以体现工作量的均衡性。如图1所示，表示3个旅行商需要访问8个城市的两段式编码。

图1 两段式染色体编码示例

记旅行商的起点城市为0，则第一个旅行商的访问回路为（0-5-2-0），第二个旅行商的访问回路为（0-4-7-1-0），第三个旅行商的访问回路为（0-8-3-6-0）。

2.2 适应度函数

适应度函数用来评估种群个体在遗传进化过程中对生存环境的适应程度。适应度较高的个体，将获得更多的繁殖机会，遗传到下一代的概率较大，而适应度较低的个体，其繁殖机会相对较少，遗传到下一代的概率就相对小一些。

根据BMTSP问题的数学模型，其目标函数是使路程最长的旅行商回路最小化，为此本文算法的适应度函数取m个旅行商路程长度的最大者。设m个旅行商各自所访问的城市数（除起点城市外）分别为n1,n2,…,nm，第k个旅行商所访问的城市编码序列记为{0,1,2,…,nk}（0 是起点城市的编号），则适应度函数的计算公式为：

由适应度函数可知，当适应度值越小，意味着路程最长的旅行商回路越短，那么个体更优。

2.3 快速单亲变异策略

单亲遗传算法取消了交叉操作，因此如何基于父代个体进行单亲变异，是算法设计的关键。遗传算法求解TSP 问题时，被广泛采用的变异算子有“基因换位、倒序、左移、右移”等，其寻优能力较强。为此，本文算法将这四种变异算子与随机插入思想相结合，形成以下4 种新的快速单亲变异算子：

a.基因换位，随机产生两个基因点，将这两个基因点的基因进行交换，再将介于这两个基因点之间的基因片段剪切插入到染色体的另一个随机点位置；

b.基因倒序，随机产生两个基因点，将这两个基因点内的基因片段按位倒序，再将倒序后的基因片段剪切插入到染色体的另一个随机点位置；

c.基因左移，随机产生两个基因点，将这两个基因点内的基因片段按位循环左移一次，再将改变后的基因片段剪切插入到染色体的另一个随机点位置；

d.基因右移，随机产生两个基因点，将这两个基因点内的基因片段按位循环右移一次，再将改变后的基因片段剪切插入到染色体的另一个随机点位置。

对单个染色体随机执行其中之一的变异算子来进行变异操作。通过上述4种变异算子的单亲繁殖与变异，较大幅度增加了种群多样性，提升了种群全局寻优能力，也加快了进化速度。将变异片段剪切后进行随机插入，有利于迭代后期防止陷入局部最优。

2.4 选择策略

在遗传算法中，选择策略的作用是从种群中挑选出基因优良的个体，淘汰掉弱势个体，从而实现仿生学的“优胜劣汰、适者生存”机制。常用的选择策略包括轮盘赌策略、锦标赛策略、精英选择策略，以及一些演变和改进的新型选择策略，它们往往各有针对性，适用于不同的情形。

在本文算法中，通过执行快速单亲变异策略后，种群个体得到快速繁殖，种群多样性得到较大的丰富和提高，为此采用一种改进的精英选择策略，其方法是将父代种群和子代种群合并，再按个体适应度排序，最后选择适应度最好的前N个精英个体（N为种群规模），构成下一代种群。

精英选择策略只选择种群中的最优良个体，因此它可以大幅加快收敛速度，但是如果种群遗传进化的多样性不够，则该策略将导致算法早熟而陷入局部最优。

2.5 最近邻点局部优化策略

通过执行2.3节的快速单亲变异策略，种群规模得到快速扩大，全局寻优能力得到增强，但是在局部寻优能力上还有所欠缺，特别是在迭代的中后期，个体已经进化比较充分，如何进一步提高求解精度、逼近理论最优解，还可以设计新的辅助策略。

局部寻优能力的增强，意味着需要对旅行商路径中部分不优的节点序列进行调整，对此贪心思想［18］是一种常见的处理方法，即对旅行商路径的某部分节点序列，按一定的贪心规则进行重新排序，使旅行商的整个路径长度更短，对应个体的适应度更优。

为此，本文算法给出基于最近邻点的局部优化策略，其处理步骤如下：

Step1：对种群的每一个体，查找路径最大旅行商所对应的染色体，记为R；

Step2：对染色体R，随机生成两个基因点I1和，将从I1到I2所包含的基因片段记为；

Step3：对基因片段S，从基因 1Ir开始，在右侧节点集合中查找它的最近邻点（距离最近的节点），将其交换到该基因的后面；重复本操作，直到S中全部基因被处理完；

Step4：重新计算该个体的适应度，若比之前的适应度更优，则保持对基因片段S的局部优化，否则还原基因片段S；

Step5：返回Step1 处理下一个个体，直到种群个体全部处理完毕。

在Step4中，借鉴了自然界生物个体的竞争排斥思想［19］，对局部优化前后的个体按适应度优劣进行竞争，把适应度差的个体排斥掉，保留适应度优的个体，以此增强个体的局部寻优能力。

上述局部优化策略，只对每个个体中路径最大的旅行商路径进行基于最近邻点的贪心局部优化，既符合BMTSP问题对旅行商路径最大最小化的目标要求，又对算法的计算量进行了合理的控制，使得算法具有较快的运算速度。

2.6 算法流程图

根据单亲遗传算法的基本流程，本文设计的IFPGA 算法首先需要随机生成初始种群，并设置算法所需的有关参数，如城市坐标，旅行商人数，算法最大迭代次数等；然后对每个初始个体进行快速单亲变异操作繁殖后代，这样可以保证种群的多样性，扩大解空间的搜索范围；计算父代与子代的适应度值，利用精英策略选择出优良个体；对优良个体进一步局部优化，使每个旅行商所走路径更短，从而得到最优解。结合上述算法设计，算法具体流程图如图2所示。

图2 改进快速单亲遗传算法流程

3 仿真实验与结果分析

3.1 实验准备

实验环境为AMD A8-45000M CPU/8GB、操作系统为windows7、编程语言为matlab2019a。实验数据从TSPLIB中选取3组算例共12种情形，包括eil51 算例的三种情形（m=3、5、10），kroA100 算例的四种情形（m=3、5、10、20），kroB150算例的五种情形（m=3、5、10、20、30），后续计算时式（8）中的常量D取所有旅行商近似均分全部城市节点。

为了检验IFPGA 算法的性能与有效性，下面从3 个方面进行实验与分析。首先，分析IFPGA算法的求解性能，尤其是最近邻点局部优化策略和随机插入操作对性能的提升效果；其次，验证IFPGA 算法对所选取算例的求解能力；最后，将IFPGA算法与其他启发式算法对所选取算例的求解结果进行比较。

3.2 IFPGA算法的求解性能分析

以算例kroB150为例，旅行商人数为m=10，种群规模为N=400、迭代次数为G=1 200。用IFPGA算法求解该算例，分别测试基于最近邻点的局部优化策略起作用和不起作用时的求解性能，绘制遗传进化曲线如图3所示。

图3 最近邻点局部优化策略对算法性能的提升

从图3 可以看到，IFPGA 算法的收敛速度非常快，当迭代100 次左右就已经快速下降。当采用了最近邻点的局部优化策略时，遗传进化效果得到明显提升，求解精度更高。

为测试算法中单亲遗传算子与随机插入思想的融合效果，仍按上述算例及参数分别作有随机插入和无随机插入的单亲遗传操作，绘制求解过程的遗传进化曲线如图4所示。

图4 随机插入操作对算法性能的提升

从图4 可以看到，随机插入操作对迭代的中后期具有持续改进的能力，进一步提升了算法在进化后期的局部寻优能力，也能较好地避免陷入局部最优。

3.3 IFPGA算法对算例的求解能力

对上述选取的3 个算例（Example）12 种旅行商人数（m）的情形，选取适当的算法参数：种群规模（N）、迭代次数（G）。将IFPGA算法在相同环境和参数下独立运行30次，统计所求最优解的最大值（Max）、最小值（Min）、均值（Mean）、标准差（Std）、平均耗时（Times），结果如表1所示。

表1 IFPGA对3个算例12种情形的求解结果

从表1 可以看到，IFPGA 算法能以较小的种群规模和迭代次数在较少的时间内求得最优解。从求解稳定性上，对3 个算例12 种情形所求得最优解的最大值、最小值相对于均值都没有出现明显的偏离，标准差也较小，体现出算法较强的稳定性。从求解的平均耗时上，表现出旅行商人数少则耗时多，反之则耗时少的特点。例如，对算例kroB150，IFPGA 算法的平均耗时（Times）与旅行商人数（m）的变化趋势如图5所示。

图5 平均耗时－旅行商人数的变化关系

由于旅行商人数较少时，每个旅行商平均需要各自经过的城市数就更多，路径也更长，此时求解所花费的时间必然更多；随着旅行商人数增多，每个旅行商需要各自经过的城市数变少，此时IF⁃PGA 算法的求解性能明显提升，特别是平均耗时（Times）有明显下降。

记算法的平均耗时和旅行商人数分别为变量T,m，通过拟合可近似建立两者的变化关系式为

利用式（8）可以对IFPGA 算法求解kroB150算例在不同旅行商人数时的平均耗时进行大致估计。对其他算例或实例数据，也可以类似获得IF⁃PGA算法的平均耗时估计式，以此为算法的实用性进行更好的评估和控制。

3.4 IFPGA算法与其他算法的比较与分析

为进一步验证IFPGA 算法的性能，本节将其与其他文献中启发式算法的求解结果进行比较。与经典TSP不同，MTSP没有开放的指定算例用于算法测试。为保持公平性，并且更有效地测试本文所设计算法的改进效果，因此选取一些已有的采用同个测试算例的改进遗传算法和其他算法得到的实验数据（均来自相关文献）与之对比。参与比较的算法包括：利用两部分染色体交叉算子的改进遗传算法（TCX）［20］、稳态分组遗传算法（GGA-SS）［21］、入侵杂草优化算法（IWO）［19］、融合杂草算法繁殖机制和局部优化变异算子的改进遗传算法（RLGA）［9］，结果如表2所示。

表2 几种算法求解3个算例12种情形的结果比较

从表2 可以看到，与TCX、GGA-SS、IWO 和RLGA相比，IFPGA算法的求解结果都优于其余几种算法得到的结果。尤其是在算例kroB150中，当旅行商人数m为3、5时，与其他几种算法相比，求解精度的提高更为明显，表明IFPGA 算法对较大规模BMTSP 问题在较少旅行商人数时具有比其余几种算法更优良的求解能力。当旅行商人数较多时，虽然IFPGA算法的求解精度提升幅度不多，但是通过3.3 节的分析可知，其平均耗时下降很快，因此求解速度将会更快。

4 结语

针对均衡多旅行商问题（BMTSP），本文首先利用0-1变量添加了有工作量均衡要求的约束条件，完善了BMTSP 问题的数学模型，为后续在均衡条件下进行算法求解奠定了基础；其次，基于遗传算法的通用框架，提出了一种改进的快速单亲遗传算法，把加快速度的重点在于强化单亲变异策略上，将常用的四种基因变异算子与随机插入思想相结合，比较明显地改善了父代个体变异为子代个体的多样性，扩大了算法的搜索寻优范围；最后，受贪婪算法思想的启发，在算法中单独设置基于最近邻点的局部优化策略，以便对经过精英优选的子代个体再次进行局部改善，从而进一步增强种群个体的局部搜索寻优能力。实验仿真表明，本文的改进方法是可行且有效的。这些改进思路和方法对遗传算法的进一步运用和发展有较好的推动作用，也对多旅行商问题的深入研究甚至实用化提供更多的手段，为生产实践提供更多的决策分析依据。