加速度粒子群算法在多旅行商问题中的应用

强 宁，康凤举

（西北工业大学航海学院，陕西西安710072）

加速度粒子群算法在多旅行商问题中的应用

强 宁，康凤举

（西北工业大学航海学院，陕西西安710072）

标准粒子群算法（PSO）在求解多旅行商问题（MTSP）时易发生早熟收敛，为此提出一种新的加速度粒子群算法。借鉴力学思想将粒子的运动描述为受力以后在解空间中的搜索运动，粒子受个体最优、全局最优的牵引力，并受局部最优的排斥力，加速度由粒子所受的合力决定。通过审敛操作判断早熟收敛，当发生早熟时局部最优对所有粒子产生的排斥力使种群跳出局部最优继续搜索。为进一步提高算法效率，针对MTSP问题的特点设计了基于维度的粒子学习策略和编解码方法。仿真结果表明，该算法能够有效克服早熟收敛，从而提高解的收敛性和稳定性，为MTSP问题提供了一种可行的方法。

多旅行商问题；粒子群算法；学习策略；编解码方法

PACS：45.50.Dd

多旅行商问题（Multiple Traveling Salesman Problem，MTSP）是经典的旅行商问题（Traveling Salesman Problem，TSP）的扩展［1］。实际应用中的很多优化问题，例如网络优化、车辆路径规划、生产调度等都可以归纳为MTSP问题。针对MTSP问题，近年来很多学者都研究了采用智能启发式算法来求解此类问题［2－4］。但是由于MTSP问题本身的复杂性，现有的智能启发式算法在求解时一般都存在易早熟、解的质量不高等问题。

粒子群算法由于其结构简单、易实现、收敛速度快、调节参数少等优点，在优化领域得到了广泛的应用［57］。但是与其他智能启发式算法类似，现有的粒子群算法应用于MTSP仍然存在容易陷入局部最优的缺点，主要原因是随着算法的迭代，种群多样性快速降低，在求解MTSP这一类具有多个局部极值的问题时很难跳出局部最优。文献［8］提出了一种加速粒子群算法，该算法去除了速度公式只采用全局最优引导粒子进化，简洁高效。文献［9］提出了加速度粒子群算法的概念，这两种算法对于单极值问题都能起到加速收敛的作用，但并没有考虑多局部极值问题，因此并不适合求解MTSP。

本文设计了一种新的加速度粒子群算法，将粒子在解空间中的搜索行为看作受合力以后的加速运动，粒子受个体最优和全局最优的牵引力，并受局部最优的排斥力，通过审敛操作判断早熟收敛。利用外部存储保存所找到的局部最优解，当迭代结束时输出最好的局部最优作为全局最优解。为了进一步提高算法的性能，根据MTSP问题的特点设计了基于维度的粒子学习策略，在每次迭代时粒子的每一维向不同的粒子学习；针对闭合式MTSP问题设计了一种新的编解码方法；采用均匀变异和高斯变异混合的变异策略保持种群的多样性。数值仿真结果表明了本文算法求解MTSP问题时的有效性和优越性。

1 多旅行商问题模型

典型的MTSP问题描述如下：考虑完全图G（V，A），V是由n个城市构成的点的集合表示为V＝｛1，2，3，..，n｝，其中1为所有旅行商的出发点，其他点为需要旅行商拜访的城市。A是V中两点之间路径的集合，C＝（cij）为与A中路径对应的距离矩阵，cij表示城市之间的距离。需要指派m个旅行商访问所有n个城市，每个城市只被一个旅行商访问一次（除了出发点）。对问题加以不同的约束就可以得到几种MTSP问题的变型［10－11］。如果C是对称矩阵，代表两个城市之间的往返距离是相等的，即cij＝cji，此时问题为对称MTSP，否则为非对称MTSP。根据是否要求旅行商返回出发点分为开放路径MTSP和闭合路径MTSP。根据旅行商的出发城市是否相同分为单起点MTSP和多起点MTSP。如果对旅行商的能力和城市的能力需求加以约束，MTSP就转化为车辆路径问题（Vehicle Routing Problem，VRP）。本文在二维空间内研究单起点的闭合式MTSP问题，城市之间的距离为欧氏距离，并满足三角不等式cij+cjk≥cik。定义变量xij，当cij包含在路径中时xij为1，否则为0。定义变量ui，代表城市i（i不等于1）被旅行商访问的次序。综上得到以下模型：

约束条件：

式（1）为目标函数，代表所有旅行商路程之和最小。式（2）限定恰好有m个旅行商离开和回到出发点。式（3）限定每个城市（除了出发点）只有一条路径进入且只有一条路径离开。式（4）、（5）和（6）用来限定每个旅行商允许访问城市个数的上限（L）和下限（K），式（7）和式（8）为变量说明。

2 加速度粒子群算法

为了克服早熟收敛问题，本文提出了一种新的加速度粒子群算法（Acceleration Particle Swarm Optimization，APSO），由于粒子受局部最优排斥力，因此能够迅速跳出局部最优。另外，为MTSP问题设计了基于维度的粒子学习策略，并采用了一种均匀变异和高斯变异混合的变异策略。

2.1 粒子群算法概述

粒子群算法（Particle Swarm Optimization，PSO）是一种新兴的智能算法［12］，具有结构简单易实现、收敛速度快等优点，但存在易陷入局部最优的缺陷。基本PSO的表达式为

2.2 加速度粒子群算法描述

在基本的PSO算法中，当粒子陷入局部最优时，式（9）右端的第二项和第三项等于0或接近于0，第一项随着w的递减变得很小，粒子的速度几乎接近于0，很难跳出局部最优，导致算法早熟。

为了解决这一问题，本文设计了一种新的加速度粒子群算法，首先假想一群鸟的觅食行为：群体中的每一只鸟根据个体的经验和附近其他鸟的经验调整飞行的速度和方向不断向食物靠近。如果一只鸟发现了食物，附近的一些鸟将跟随这只鸟飞向食物，这些鸟在吃完食物后会继续搜索其他区域，并且会判定刚才找到食物的区域已不必再判定搜索。鸟群的行为可以看作粒子找到局部最优解后会存储并远离此区域，之后继续搜索其他区域，所以粒子不存在稳定状态。随着找到的局部最优解增加粒子搜索空间变得越来越小，种群更有机会找到全局最优解，最终的全局最优解就是鸟群记忆中最好的局部最优解。

为了模拟这种行为，首先给出运动规律

参数a、v和x分别代表加速度、速度和位移。将粒子在解空间中的搜索行为看作受力以后的加速运动，粒子受个体最优和群体最优的牵引力，并产生加速度向最优解方向搜索，当发生早熟收敛时，局部最优粒子对种群中的所有粒子产生排斥力，这个排斥力随着粒子远离局部最优将逐步减弱，以免对粒子将来的搜索造成影响，图1为粒子受力的示意图。综上，提出了一种新的加速度粒子群算法（APSO）如下

图1 粒子受力示意图Fig.1 Force diagram for a particle

式（14）为加速度公式，右端第1和第2项分别代表粒子受个体最优和全局最优粒子的牵引力所产生的加速度，参数的含义和式（9）相同。式（14）右端第3项代表粒子受当前所有局部最优粒子的排斥力所产生的加速度，加速度的方向由局部最优解指向当前粒子位置，加速度的大小与距离（－pj）成反比，当（－pj）从0到无穷变化时，排斥力所产生的加速度在［c3·R／c，0］之间变化，r3为［0，1］上均匀分布的随机数，k为当前所找到的局部最优解的个数，pj代表局部最优解的位置。参数c3、R和c决定排斥力的大小，参数b决定排斥力加速度随距离的变化率。在找到局部最优之前，式（14）右端第三项为0，当找到一个局部最优时，将它保存在一个外部存储中（为方便描述命名为集合G），集合G中的元素作为式（14）中的pj。

2.3 个体最优和全局最优的重新选择策略

当粒子陷入局部最优时，粒子的个体最优和全局最优一般也在局部最优附近，因此粒子所受的引力和排斥力方向相反，导致粒子在局部最优附近震荡。为了保证粒子不再飞回局部最优，当找到局部最优以后需要重新选择粒子的个体最优和全局最优。具体方法为：如果当前粒子迭代一次以后适应值和到局部最优的距离都减小，那么视为一次“危险飞行”，如果局部最优对粒子的排斥力大于个体最优和全局最优对粒子的引力，则从当前迭代向前剔除所有连续的“危险飞行”所对应的个体位置，并重新确定粒子的个体最优和全局最优。

该策略可以理解为鸟群可以记住通向局部最优的“通道”，如果鸟群发现一条“通道”通向局部最优，则在将来的搜索中，“通道”中的所有位置都不能再作为个体最优和全局最优。在编程时，保存每个粒子每一代的适应值和位置，当确认一组连续的“危险飞行”导致粒子飞回局部最优时，将所有连续的“危险飞行”所对应的适应值附加一个很大的值（保证他们不再被选中），再重新选择个体最优和全局最优。

2.4 基于维度的粒子学习策略

粒子的编码为n－1维，每一维代表一个城市的指派（详见本文第3部分）。标准的粒子群算法中粒子每一维的学习对象都是同一个粒子，这可能造成在一次迭代以后粒子的某些维度靠近全局最优解，而另一些维度却远离全局最优解。对于MTSP问题，若当前解向同一个最优解学习，可能导致部分城市的指派达到最优，而另一些城市的指派却远离最优。

因此，提出了基于维度的粒子学习策略，使粒子的每一维向不同的粒子学习。当前粒子每一维的学习样本应满足两个条件：（1）具有更好的适应值；（2）更接近当前粒子的维度。

定义约束量

则粒子个体认知学习策略为：在当前粒子的邻域范围内找到使得式（17）取最大值的粒子作为当前粒子第d维个体认知的学习对象。在初始化时按照欧氏距离取最近的k个粒子作为粒子的邻域，并且每隔T1代重建粒子的邻域。Fit代表粒子的适应值，即粒子位置代表的城市指派所对应的旅行商路程之和。

定义约束量

其中pgj代表群体中历史适应值最优的k个粒子。则粒子社会认知学习策略为：在其中找到使得式（18）取最大值的粒子作为当前粒子第d维社会认知的学习对象。

基于维度的粒子学习策略充分利用了邻域粒子和全局最优粒子每一维上的最优信息，针对实数编码的MTSP问题能够使得每个城市的指派都向当前该城市的最优指派学习，使得种群更有机会找到全局最优解。

2.5 审敛操作

本文提出的加速度粒子群算法能够克服早熟收敛，跳出局部最优，早熟收敛的判定依据是一个关键问题。根据前面的分析，当种群陷入局部最优时粒子的速度很小，种群聚集在局部最优位置附近，很难跳出局部最优。引入变异操作可以提高种群的多样性，但由于其随机性和盲目性，变异操作并不能确保种群跳出局部最优。种群陷入局部最优时具有两个基本特征：（1）全局最优连续多代没有更新；（2）粒子聚集导致种群多样性降低。首先定义种群的多样性测度为

其代表平均粒子间距，描述了种群中粒子间相互分布的离散程度，用来定义种群的多样性，Div越小表明种群越集中，多样性越小。N为种群规模，dn为粒子编码的维数，L为解空间的最大长度，代表第t次迭代时第i个粒子第d维的编码值代表所有粒子第d维编码的平均值。

审敛操作可描述为：如果全局最优连续T2代没有更新，且种群多样性Div小于ε（ε∈（0，1））则认为发生早熟收敛，将当前最优解记为局部最优，并存入外部档案集G。

2.6 变异操作

当算法发生早熟收敛时种群的多样性很低，局部最优粒子对种群的排斥力可以帮助粒子迅速跳出局部最优，一定程度上能够提高种群的多样性，但是当种群远离局部最优时仍可能发生聚集。为了进一步在整个迭代过程中提高种群的多样性，采取均匀变异和高斯变异结合的变异策略，具体方法为：在迭代初期以更大概率采用均匀变异策略，使得粒子有机会在整个解空间中搜索，而在迭代后期以更大概率采用高斯变异策略，提高粒子的局部搜索能力。均匀变异公式为

高斯变异的公式为

采用均匀变异策略时粒子的位置和速度均发生变异，而采用高斯变异策略时只有粒子的位置发生变异，速度不变。xmin，d、vmin，d和xmax，d、vmax，d代表粒子在第d维的位置和速度的最小值和最大值，R代表（0，1）上的均匀分布随机数，Gaussian（0，0.1）代表均值为0方差为0.1的高斯分布随机数。种群中的粒子以概率1／N发生变异，发生变异的粒子以概率（tmax－t）／tmax选择均匀变异策略，以概率1－（tmax－t）／tmax选择高斯变异策略。N为种群规模，t和tmax分别为当前迭代次数和最大迭代次数。

2.7 算法流程

APSO算法求解MTSP问题的步骤：

步骤1：初始化种群，确定粒子邻域。根据具体的MTSP问题，决定决策空间的维度和每一维的取值范围。

步骤2：进行解码操作，根据公式（1）计算粒子的适应值。

步骤3：根据公式（17）和（18）选择粒子每一维的个体和全局学习对象，根据公式（14）、（15）和（16）更新粒子位置、速度和加速度；每隔T1代重新计算粒子的邻域；如果G不为空集判断粒子是否经历“危险飞行”，如果是则重新选择粒子的个体和全局最优。

步骤4：执行变异操作，若发现更优解，则更新当前最优解。

步骤5：根据审敛操作判断是否找到最优解？若为是，则转到步骤6；否则转到步骤7。

步骤6：保存找到的最优解到集合G。

步骤7：判断迭代是否结束？若为否，则转到步骤2；若为是，则输出G中最好的解作为全局最优解。

3 编码和解码方法

编码是指将MTSP问题的解和粒子的位置之间建立一种合适的映射关系。编码和解码方法对算法的效率影响显著，本文参考文献［11］设计的实数编码方法并加以改进。

3.1 编码方法

假定城市个数为n，旅行商个数为m，则粒子编码为n－1维，每一维的整数部分代表城市指派的旅行商，而小数部分代表城市被访问的顺序。假定有8个城市（1为起点）3个旅行商，一个粒子的编码为

3.2 分组解码

上例中具有相同整数部分的城市分在同一组，被一个旅行商访问，分组结果为

第一个旅行商访问的城市：2，5；

第二个旅行商访问的城市：4，6，8；

第三个旅行商访问的城市：3，7。

粒子编码的整数部分只能在｛0，1，2｝中取值，代表3个旅行商，如果编码计算以后超出范围将自动调整在（0，3）上，例如计算结果为3.37则调整为0.37。

3.3 排序解码

假定一个旅行商所访问的城市顺序为｛1，3，2，6，5，4，1｝，考虑当前研究的MTSP问题是对称且闭合的，因此该访问顺序等同于｛1，4，5，6，2，3，1｝，而传统的解码方法认为这是两个不同的解。为了消除重复编码，提高算法效率，提出了解码方法为将分组中各城市编码的小数部分由小到大进行排序。为方便编写代码，定义了路径的左侧和右侧，在分组中选择编码值最小的两个城市加入路径，且其中较小的一个城市加入左侧，而另一个加入右侧。重复上述过程直到所有城市都加入了路径中。表1为一个分组中城市的编码排序，图2演示了排序解码的过程。

表1 分组中7个城市的编码排序Tab.1 The sequence of encoding values in a group with 7 cities

图2 组内排序解码过程Fig.2 The sequence decoding process within a group

4 仿真实验

算法通过Matlab编程在双核3.10GHz、4G内存的计算机上运行，选用标准TSPLIB库中的三组数据eil51、eil76和eil101做数值仿真实验。将APSO的运行结果与UPSO［13］、MPSO［14］和EDPACA［15］比较。UPSO为统一的PSO算法，是经典的PSO算法之一；MPSO是一种改进的多种群PSO算法；EDPACA是一种均分点蚁群算法，在处理MTSP时获得了良好的效果。APSO的参数设置为：种群规模N＝80，惯性因子w在［0.9，0.4］上随迭代次数线性递减，加速因子c1＝c2＝1.496，c3＝0.5，R＝1，b＝3，c＝0.5，ε＝0.05，T1＝T2＝20，邻域范围k＝10，最大迭代次数tmax＝1 000。UPSO和MPSO除种群规模和迭代次数统一设置为80和1 000，其他参数设置来自文献［13］和［14］。EDPACA的参数设置和结果均来自文献［15］，值得注意的是EDPACA结合了2－OPT算法进行局部路径优化，而UPSO、MPSO和APSO都没有采用局部优化。四种算法分别独立运行50次。

图3为m＝3时UPSO、MPSO和APSO求解eil51、eil76和eil101的进化图。可以看出UPSO算法易早熟、求解质量较差；MPSO算法采用了多种群结构搜索范围更广、多样性更好，因此具有一定的抑制早熟能力，求解质量优于UPSO；APSO算法引入了加速度策略，粒子始终受局部最优的排斥力，因此能够有效克服早熟收敛，求解质量最好。图4为m＝3时APSO求解eil51、eil76和eil101所得的最优路径。

表2为4种算法分别运行50次的统计结果。可以看出APSO算法效果最好，在9种测试情况下最优值和平均值都领先于其他3种算法，说明AP－SO的求解质量和稳定性都最好，结合局部路径优化的EAPACA算法性能次之，而采用多种群结构的MPSO算法性能超过了UPSO算法。

图3 UPSO、MPSO和APSO求解m＝3时的eil51、eil76和eil101的进化图Fig.3 Evolution of UPSO、MPSO and APSO on eil51、eil76 and eil101 while mis equal to 3

图4 APSO求解m＝3时的eil51、eil76和eil101的最优路径Fig.4 The optimal paths on eil51、eil76 and eil101 while mis equal to 3 using APSO

表2 4种算法的结果比较Tab.2 Comparison of the results solved by four algorithms

表3比较了当m＝3时3种PSO算法找到最优值时的平均迭代次数和运行时间，并且比较了采用新的编解码方法和文献［11］的编解码方法时3种PSO算法找到最优值时的平均迭代次数，t代表算法运行的平均时间。3种算法最大迭代次数设置为1 500，独立运行30次。c1和c2分别代表采用新的编解码方法和文献［11］的编解码方法时找到最优值的平均迭代次数，t代表算法运行的平均时间。采用两种不同编码方法时，每种PSO算法的运行时间均差别不大。可以看出UPSO找到最优值的平均迭代次数最小但最优值较大，说明UPSO易早熟收敛导致求解质量不高，而MPSO和APSO均能够较好的克服早熟收敛，求解质量较高，但由于具有更高的计算复杂度所以运行时间大于UPSO。当算法采用新的编解码方法时，UPSO找到最优值的平均迭代次数变化不大，这是因为UPSO易早熟，新的编解码方法没有充分发挥作用，而MPSO和APSO算法在找到相同最优值的情况下采用新的编解码方法比采用文献［11］的编解码方法时的平均迭代次数显著减少，这是因为新的编解码方法能够消除重复编码，提高了算法的效率。

表3 3种PSO算法比较Tab.3 Comparison of three PSO algorithms

5 结语

本文提出了一种新的加速度粒子群算法，种群中的粒子受局部最优的排斥力，能够迅速跳出局部最优，且在将来的搜索中不会重复搜素局部最优区域，使得种群有更大机会找到全局最优解。所提出的基于维度的粒子学习策略和新的编解码方法进一步提高了算法的性能。该算法能够有效克服早熟收敛，从而提高MTSP问题的求解质量和稳定性。算法在多模态函数优化以及多目标优化领域的应用还需进一步研究。

［1］Bellmore M.Transformation of multi－salesmen problem to the standard traveling salesman problem［J］.Journal of the Association Computer Machinery，1974，21（5）：500－504.

［2］Imdat Kara，Tolga Bektas.Integer linear programming formulations of multiple salesman problems and its variations［J］.European Journal of Operational Research，2006，174：1449－1458.

［3］Carter A E，Ragsdale C T.A new approach to solving the multiple traveling salesperson problem using genetic algorithms［J］.European Journal of Operational Research，2006，175：246－257.

［4］Chen A，Yang G.Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem［J］.Journal of Zhejiang University Science A， 2006，4247：158－165.

［5］吴晓军，杨战中，赵明.均匀搜索粒子群算法［J］.电子学报，2011，39（6）：1261－1266.

［6］张长胜，孙吉贵，欧阳丹彤，等.求解车间调度问题的自适应混合粒子群算法［J］.计算机学报，2009，32（11）：2137－2146.

［7］王静云，常安定，徐春龙，等.应用粒子群算法设计锥形孔微穿孔板结构［J］.陕西师范大学学报：自然科学版，2014，42（2）：37－41.

［8］Yang Xinshe，Suash Deb，Simon Fong.Accelerated particle swarm optimization and support vector machine for business optimization and applications［J］.Networked Digital Technologies，2011，136：53－66.

［9］陈彦宇.基于加速度粒子群算法的微控制器电磁抗扰度建模研究［D］.北京：华北电力大学电器工程学院，2013：13－20.

［10］马建华，房勇，袁杰.多车场多车型最快完成车辆路径问题的变异蚁群算法［J］.系统工程理论与实践，2011，31（8）：1508－1516.

［11］Marinakis Y，Iordanidou G，Marinaki M.Particle swarm optimization for the vehicle routing problem with stochastic demands［J］.Applied Soft Computing，2013，13：1693－1704.

［12］Kennedy J，Eberhart R.Particle swarm optimization［C］∥Proceedings of IEEE International Conference on Neural Networks.1995：1942－1948.

［13］Parsopoulos K E，Vrahatis M N.UPSO：A unified particle swarm optimization scheme［C］∥Proceedings of Conference of Computational Methods in Science and Engineering.2004：868－873.

［14］Chang Weide.A modified particle swarm optimization with multiple subpopulations for multimodal function optimization problems［J］.Applied Soft Computing，2015，33：170－182.

［15］余伶俐，蔡自兴.均分点蚁群算法在群集机器人任务规划中的应用研究［J］.高技术通讯，2009，19（10）：1054－1060.

〔责任编辑 李 博〕

Application of a new acceleration particle swarm optimization for solving multiple traveling salesman problems

QIANG Ning，KANG Fengju
（School of Marine，Northwestern Polytechnical University，Xi'an 710072，Shaanxi，China）

To overcome the premature convergence of the standard particle swarm optimization（PSO）in solving multiple travelling salesman problems（MTSP），a new acceleration particle swarm optimization is constructed.Rely on the idea of mechanics，the movement of particle is described as search motion driving by force in solution space.The particle is attracted by personal best force，global best force and repelled by local best force.Thus the acceleration of particle depends on the resultant of forces.Using convergence criterions to estimate premature convergence，the local best will repel all the particles when premature convergence occurs，so the particle swarm can jump out the local best and continue to search.In order to improve the efficiency of the algorithm，a dimensional learning strategy of particle and a new coding method are designed for MTSP.The simulation results show that the proposed algorithm can effectively overcome the premature convergence，and improve the quality and stability of solutions.Thus it provides a feasible method for MTSP.

multiple traveling salesman problems；particle swarm optimization；learning strategy；coding method

TP393

：A

1672－4291（2015）06－0036－07

10.15983／j.cnki.jsnu.2015.06.263

2015－05－13

船舶预研支撑技术基金（11J4.1.1）；水下信息处理与控制国家重点实验室基金（9140C2305041001）

强宁，男，讲师，博士研究生，研究方向为多Agent系统理论及应用。E－mail：qn315＠snnu.edu.cn