邢凯，肖洒，赖菲，王铁广，方赛银，李明

（西南林业大学机械与交通学院，昆明 650224）

0 引言

旅行商问题（Traveling Salesman Problem,TSP）属于NP难的组合优化问题，经典的规划算法在有限的时间内无法得到优化解，故采用群集智能优化算法来解决此问题，诸如遗传算法[1]、蚁群算法[2]、模拟退火算法[3]等。

遗传算法本身具有较强的鲁棒性，并且适用于求解各种复杂的优化问题，能够在理想的时间内求出全局最优解。Ahmed[4]对交叉算子深入研究，提出了一种新的顺序建设性交叉算子，能够高效精确地解决TSP问题。Liu[5]针对变异操作提出增强突变的改进，将交叉操作中随机选择用异构配对选择代替，最终在解决TSP问题时其效果明显优于传统GA算法。胡士娟等[6]提出将蚁群算法（Ant Clony Optimization, ACO）的反馈机制和GA算法的全局搜索能力相结合，并且通过TSP实例验证了其算法比ACO算法和传统GA算法具有更好的寻优能力。Deep 和Adane[7]对于顺序交叉算子，提出了一种改进的树形结构，有效地提高了传统GA算的效率。Kumar等[8]将TSP不同交叉算子进行比较分析，实验结果表明部分映射的交叉给出了最短的路径。葛耀宝[9]提出一种基于染色体择优选择的策略，大幅度地减少了算法早熟情况。Ma[10]在2-opt选择策略和GA算法框架的基础上，提出了一种新的混合遗传算法，仿真试验结果表明了该算法的有效性。对于小规模的路径优化问题，可以通过上述启发式GA算法获得最优解，然而对于大规模的路径优化问题，传统GA算法局限性就凸显出来了，不仅收敛速度慢，而且容易早熟收敛陷入局部最优化。

为此，本文提出一种分区协作遗传算法（Subpartition Cooperation Genetic Algorithm，SCGA），提高GA算法在求解大规模路径优化问题时的全局收敛能力。首先，基于距离聚类的方法将城市集划分为规模相当的分区，并通过传统GA算法获取分区不闭合的分区最优路径；其次根据分区之间的距离按照就近原则确定每个分区的首尾城市，根据各分区之间距离顺序连接各个分区路径获得全局最优路径；最后，从TSPLIB标准测试集选取若干实例进行试验，验证SCGA算法的可行性与有效性。

1 TSP描述

TSP问题是一个NP难问题[11-12]，可以描述为给定一系列城市坐标集, 一个旅行商从起点城市出发, 去往各个城市推销他的商品，如何经过各个城市一次并回到出发点的路径规划问题。其问题的解可以被描述为各个城市出现一次且仅出现一次构成的排列方案, 该排列方案代表着旅行商将第一个城市作为出发点, 依次按排列顺序对城市进行访问, 最后再回到第一个城市的路径规划方案。TSP问题的最优解就是旅行商所经历过的最短路径。

TSP的数学模型描述如下：

假设有n个城市，它们之间的距离矩阵为D=(dij)n×n，dij为城市i与城市j之间的距离(i≠j)；dij=M，M为足够大的数。

2 改进遗传算法求解TSP

本文设计一种距离聚类分区遗传操作机制：受有限元分析思想的影响，将一个难以解决的大问题转换成多个容易的小问题，在解决多个小问题的基础上得到整个大问题的近似解；基于此思想，在进行一系列遗传操作之前，将大规模城市群进行聚类分区优化操作，每个分区选取一个中心城市，当城市之间的“相近性”用欧氏距离来进行描述时，选择准则为各城市到其中心城市距离的平方和，可以表示为

式中：k为分区数目；Ci为第i中心城市；d（Ci，x）为城市x到中心城市Ci的距离。

在优化操作后期，将已经划分好的分区按照顺时针或逆时针的顺序，相邻两分区内的起始点与终点有优先的选择权，以此来提高算法的精确性。

在多个分区划分完成并且排序后，分别对每个分区采用传统GA算法得出分区相对最优解作为分区的最短路径，着重标记起始点以及终点[13]；根据相邻分区就近原则，选择与该分区起始点或终点最近的邻域内起始点或终点，最后将多个分区的路径按照相邻分区最短距离拼接起来，作为整个大规模TSP问题的最短路径。

2.1 聚类分区操作

对于大规模TSP，城市数目众多，遗传算法无法在短时间内得到令人满意的结果。本文采用聚类分区方法对大规模城市进行划分，综合考虑城市的布局、城市间距离以及城市的规模，将距离相近的城市划为一个分区，城市之间的“相近性”用欧氏距离来进行描述，可以表示为

式中：dij为城市Ci与Cj的相近性；p为城市属性的数量，本文中p取2（城市的横纵坐标）。

大规模城市总共被划分为多个分区，此后解决大规模旅行商问题即在多个已划分完成的分区上进行；对比分析将大规模旅行商问题分别划分为多个分区时，哪种划分方法所得旅行商最短路径最适宜。

2.2 遗传操作

对于分区完成的城市的路径进行编码，直接采用城市在路径中的位置来构造用于优化的状态。例如四分区时：第一分区有24个城市，路径为5-4-18-1-22-7-9-24-8-19-6-14-21-2-15-3-23-10-11-20-12-17-13-16，路径编码为（5-4-18-1-22-7-9-24-8-19-6-14-21-2-15-3-23-10-11-20-12-17-13-16）。

优质的初始种群往往能够得到理想的遗传算法结果，一个个体由该分区城市数目随机产生，随机生成N个个体作为初始群体popm[14]，随机选择一个种群，由于随机性较强，因而也较公正。

在进化搜索的过程中，遗传算法基本不利用外部信息，仅将适应度函数作为依据，利用种群中每个个体的适应度值来进行搜索。TSP的目标是路径总长度为最短，路径总长度的倒数就可以作为TSP的适应度函数：

式中：f为适应度；d为两城市之间距离。

一般来说，个体被选中的可能性大小与其适应度呈现出正相关的关系，适应度较大（优良）个体有较大的可能性被选中，而适应度较小（低劣）的个体被选中的可能性相对来说就较小，本文采用最简单的一种选择方法——轮盘赌选择法。具体操作如下。

1）计算出群体中每个个体的适应f（w1，w2…，wn）。

2）计算出每个个体被遗传到下一代群体中的概率：

4）在[0，1]区间内产生一个均匀分布的伪随机数r。

5）若r

交叉操作是产生新个体的操作之一，优良的交叉方式可以在一定程度上提高种群的多样性。为提高算法的搜索效率，本文采用多点交叉的方式[15]，对于多点交叉，m个交叉位置Ki可以随机无重复地选择，在交叉点之间的变量间续地相互交换，产生2个新的后代，但在第一位变量与第一个交叉点之间的一段不做交换，例如：

父个体1：1 4 7 2 5 8 3 6 9；

父个体2：2 5 8 3 6 9 1 4 7；

交叉点的位置选为：2 5 8。

子个体1：1 4 8 3 6 8 3 6 7；

子个体2：2 5 7 2 5 9 1 4 9。

变异操作本身是一种局部随机搜索，与选择、交叉算子结合在一起，确保了遗传算法的有效性，使得遗传算法具有局部的随机搜索能力，可以加速向最优解收敛；同时使得遗传算法保持种群的多样性，降低早熟收敛问题出现的可能性。本文采用倒置变异法，例如：假设当前个体X为(1 3 7 4 8 0 5 9 6 2 )，如果当前随机概率值小于变异概率，则随机选择来自同一个体的2个点，然后倒置该2个点的中间部分，产生新的个体[16]。例如，假设随机选择个体X的2个点“7”和“9”，则倒置该2个点的中间部分，即将“4805”变为“5084”，产生新的个体X为(1 3 7 5 0 8 4 9 6 2)。

算法流程如图1所示。

图1 算法流程图

3 大规模TSP仿真试验

仿真环境为Win10系统下的Matlab2016a，系统主要硬件为：CUP主频为2.7 GHz，内存为12 GB。

选取TSPLIB中若干实例进行试验，试验参数选取如下：初始种群大小为100；最大迭代次数为1000次；交叉概率为0.8；变异概率为0.1[17]。对多个分区分别采用普通遗传算法处理，计算分区最优路径，将首尾城市按照就近原则选择邻域内最近的首尾城市，领域的选择顺序按照顺时针或者逆时针，获取其全局最短路径。在多个分区内采用普通遗传算法中，根据算法的随机性，从中选出分区最短路径。

为了验证SCGA算法的性能，本文将大规模TSP问题划分为多个分区，对每种划分方式运用SCGA算法进行随机计算10次处理，以10次试验结果的平均值分析比较每种划分方式的差异。传统GA算法和SCGA算法所求最短距离如表1所示。

表1 算法分区对比

由表1试验结果可知，在迭代次数、交叉率、变异率等参数相同的情况下，分区GA算法对于大规模TSP问题的处理效果相较于传统GA算法最优解为原来的1/2以上；当分区数目相同时，对于规模越大的TSP问题，SCGA算法的处理效果越好。但是获得的最优解并不是因为分区数目越多越好，当分区数目过多时，获取的最优解并不是很理想；为解决此问题，选取Rat195TSP实例进行分区拟合，探究分区数与最优解的函数关系。

选取Rat195TSP 实例问题进行分区拟合，对Rat195TSP实例进行2分区、4分区、8分区、10分区、12分区、14分区、16分区、18分区处理，对各分区所得最优解进行拟合，拟合结果如图2所示。

图2 分区拟合图

由拟合图可知，对于Rat195TSP实例，分区数目与最优解之间的函数关系式可以表达为y=-0.028x3+20x2-410x+5200，当分区数目过多或是过少时，获得的最优解都不理想，分区数目过少时，单个分区内城市数目过多，容易陷入局部最优，造成早熟收敛现象，故不能获得理想的最优解；分区数目过多时，单个分区内城市数目过少，可以较早地获得分区最优解，但分区之间的距离随着分区的数目增加而增加，所以当分区数目过多时也不能获得理想的最优解；当分区数目为10时，Rat195TSP实例获得最优解，通过拟合结果可以看出，分区数与最优解之间具有一定的多项式关系，能够很好地反映出不同的分区数目之间仍存在一定差异，当分区数目在8～12时，分区城市数目在17～26之间，此时的分区数目与分区城市数目相比于其他分区数目与分区城市数目达到一个“平衡点”，获得的最优解比其他分区数目时的效果更加令人满意。

4 结论

传统GA算法在解决大规模路径优化问题时存在着“早熟”、收敛速度慢等问题，规模越大传统GA算法处理的性能也就越差，本文设计了一种改进遗传算法用于解决大规模路径优化问题，将处理一个大规模路径优化问题转化为处理多个小规模路径优化问题，可在一定程度上避免“早熟”现象的发生，加快收敛速度，使得算法性能得到较大的提升。仿真试验结果表明，SCGA算法可以在一定程度上抑制“早熟”现象的发生，并且能够较好地解决陷入局部最优的问题，但是分区数目与最优解之间存在一定的多项式关系，当分区数目在8～12，可以获得令人满意的最优解。本文提出的SCGA算法相较于传统GA算法虽然性能上得到了较大的提升，但是对于路径优化问题分区间的衔接还有很大的研究空间，接下来会在以后的工作中进一步研究。