基于改进粒子群算法的路径规划研究与应用

董林威,高宏力,潘江

(西南交通大学 机械工程学院,四川 成都 610031)

0 引言

旅行商问题[1](travel salesman problem,TSP)是一个NP-hard优化问题,可被描述为求解一次性不重复地走过n个给定的城市且回到最初城市的最短闭环路径。针对旅行商问题的求解主要有启发式算法以及近似算法。其中标准粒子群算法基于群体和个体的适应度大小进行进化更新,用于求解TSP问题时具有整合参数少、迭代简单以及快速收敛等特点[2],但是又存在易陷入局部最优、收敛精度不高等问题。基于上述缺陷,近年来诸多学者基于优化的粒子群算法求解TSP问题进行了大量的研究。文献[3]根据粒子适应度值对群体中表现性能各异的粒子采取不同的惯性权重调整策略,保持种群发展过程中的惯性权重多样性,兼顾了全局和局部的搜索寻优能力。文献[4]基于灰狼算法的发展多样性,提出参数自适应的粒子群灰狼混合算法,引导粒子种群进化方向的准确性。文献[5]提出基于自适应动态优秀系数的粒子群算法(SECPSO),在粒子搜索的每条路径上设置权重系数,并且根据种群搜索解的能力进行自适应变化,基于3-opt局部搜索方式评价和共享粒子的位置信息,一定程度上加大了粒子群后期的收敛速度和精度。

但是SECPSO算法在针对中大规模数据的求解时,存在收敛速度较慢,精度不高的问题[5]。基于此,本文提出一种改进自适应杂交退火粒子群算法(improved adaptive hybrid annealing PSO,IAHAPSO),在寻优能力和求解效率上相较传统算法都有较大优势。另外搭建四轴裁剪系统与所提算法结合,以解决裁剪路径规划问题,进一步验证了所提算法的有效性。

1 旅行商问题的标准粒子群算法

1.1 旅行商问题

旅行商问题可被描述为:在给定城市距离的基础上,一次性不重复地走过n个给定的城市且回到最初城市的最短闭环路径,该路径又被称为最短Hamilton回路。其目标函数可表示为求解一段城市序列τ=(V1,V2,…,Vn)使得式(1)最小,其中Vn代表城市标号。

(1)

式中:Td为总距离;d(Vi,Vi+1)为顶点ci到顶点cj的距离,也称为费用矩阵。

1.2 应用粒子群算法的旅行商求解

1)交换子

定义粒子1位置向量:Xi=[xi1,xi2,xi3,…,xin],粒子2位置向量:Xj=[xj1,xj2,xj3,…,xjn],则有交换子vij=(xia,xja)表示对两个位置向量在序列a处的位置进行对调。

2)交换序列

对交换子组成的序列V=[v1,v2,v3,…,vn]称为交换序列。

3)速度定义

粒子的速度表示为对位置向量中城市的交换序列向量,是对位置向量的城市顺序进行调整。即速度向量Vi=[vi1,vi2,vi3,…,vin]中vin表示交换子vin=(xn,xv,in),将原位置向量中按向量顺序对索引为n处的城市与索引为vin的城市进行位置互换。

4)位置速度更新公式

在对速度位置重新定义后,用于求解旅行商问题的粒子群算法更新公式如下:

(2)

(3)

旅行商问题为离散问题,对位置的更新需要按照⨁运算符分步进行,即:

(4)

(5)

(6)

2 所提算法

因标准粒子群算法存在早熟停滞、极易陷入局部最优以及收敛精度低等问题[7],本文提出了改进自适应杂交退火粒子群算法(IAHAPSO),对标准粒子群算法的惯性权重采用分种群式调节,对群体极值的更新融入模拟退火机制引导粒子正确的进化方向,并且根据种群离散度大小引入杂交变异算子,以提高算法鲁棒性。

2.1 分种群自适应惯性权重

(7)

基于粒子适应度和种群离散度的惯性权重调整如下。

1)当fi优于fmax_avg时,该粒子寻优效果好,此时应该赋予该粒子较小的权重值,调整式为

(8)

2)当fi次于fmax_avg但优于fmin_avg时,该类粒子质量一般,搜索能力尚能在全局搜索和局部搜索之间调节,故不予改变此类粒子的惯性权重。

3)当fi次于fmin_avg时,该类粒子在种群中表现较差。引入种群离散度可接受值,记为σaccept,可认为当种群离散度σk<σaccept时,种群聚集程度高;相应的种群离散度σk>σaccept时,种群发散。并且引入迭代系数μ,当k<μKmax时认为种群处于发展前期。

a)σk≤σaccept时,种群聚集程度高,种群易陷入局部最优,此时表现“较差”的粒子应具有在全局最优解附近进行搜索的能力,故ω=ωmax加大其全局搜索的能力。

b)k<μKmax且σk>σaccept时,为平衡惯性权重值对种群在全局和局部范围内的搜索能力,综合考虑种群发展程度和种群离散度,采用的自适应惯性权重调整方式如下:

(9)

上式中参数k1控制ω的范围,考虑种群离散度和种群发展程度自适应调节。

c)k≥μKmax且σk>σaccept时,该种情况种群发展后期且尚未收敛,应降低惯性权重值,加大该类粒子局部搜索能力,加速收敛,故ω=ωmin。

2.2 基于模拟退火算子的群体极值更新

本文引入退火操作从诸多粒子pi中根据突跳概率更新群体极值gbest,提高算法避免陷入局部极小值的能力。种群中每个粒子按下式计算温度T下该粒子pi相对gbest的突跳概率P*:

(10)

式中:T(k)为退火温度,退火规律见式(11);ρ为降温系数;fg,best(1)为初始群体极值。

(11)

最后,采用轮盘赌策略及式(10)从粒子群中所有粒子确定群体极值的替代值p′i来替代gbest。

2.3 选择交叉变异算子

本文利用种群离散度判断种群发展的趋同程度,类似地,当σk≤σaccept时则进行遗传变异算子。

选择算子:本文采用基于比例选择和最优选择的策略,首先复制群体最优粒子到下一代,使其占下一代种群数量的M%,剩余1-M%的粒子采用轮盘比例策略进行选择,每个个体被选中的概率为

(12)

经过上述方式选出N个优秀粒子进行后续操作,使得粒子整体朝着种群最优的方向运动。

交叉算子:采用将选择算子得到的N个粒子随机进行两两匹配的方式,从而形成N/2组父代双亲Father,A,Father,B,以交叉概率Pc且随机产生一个交叉点位置α,将Father,A的序列1-α的元素作为子代Child,A的系列1-α,将Father,B中包含Father,A序列1-α的元素按照Father,B的顺序作为Child,B的系列1-α,将Father,A的α之后的元素作为Child,B的剩余元素值,而将Father,B中的剩余元素按序列作为Child,A的剩余元素值。例如,有两个父代序列,交叉点位置为3,则有:

Father,A=1,3,6,8,4,7,2,5
Father,B=2,4,3,5,1,7,6,8

交叉后子代为:

Child,A=1,3,6,2,4,5,1,8
Child,B=3,1,6,8,4,7,2,5

变异算子:针对种群中的每个粒子,随机产生交换序列对[β,γ],对该个体的序列位置β上的元素与序列位置γ上的元素进行互换,以此直至完成所有个体的变异。

2.4 算法流程

基于上述模块,本文所提IAHAPSO算法的具体流程如图1所示。

图1 IAHAPSO算法流程

3 仿真及应用

为验证所提算法的性能,本文首先选择3种标准TSPLIB测试集,以城市总距离的倒数为适应度值fi,并且将本文IAHAPSO算法同标准PSO算法以及SECPSO算法进行比较,验证算法的可行性。

3.1 TSP测试集及参数设置

本文选择TSPLIB测试集当中的Eil51、St70及Ch150 3种问题进行实验对比分析,设置相关参数如下:种群规模N=200,最大迭代次数Kmax=1 000,ωmax=0.8,ωmin=0.2,σaccept=5,Pc=0.6,M=20,μ=0.4,ρ=0.98,k1=50。SECPSO 算法中的相关参数与文献[5]相同;标准PSO算法取ω=0.8。针对3种测试集问题,采用PSO、SECPSO以及IAHAPSO算法的求解收敛曲线如图2—图4所示,表1给出了3种不同算法求解问题的性能比较。

表1 性能结果比较

图2 Eil51不同算法收敛速度

图3 St70不同算法收敛速度

图4 Ch150不同算法收敛速度

表1统计了本文所提算法与SECPSO算法的性能对比,其中平均值为各实例在各算法下迭代50次的平均结果。从表中可以看出,本文所提的算法在搜索能力上优于SECPSO算法。另外对于部分标准测试集,虽然IAHAPSO算法在平均值上略差于SECPSO算法,但是在最优值的求解上本文所提算法都优于SECPSO,整体求解能力有较大的优势。

3.2 四轴裁剪机试验系统

为验证所提算法在实际应用中的兼容性和有效性,搭建了如图5所示的四轴裁剪机试验系统,用于对排样固定的裁剪样片进行切割。整体装置由电机模组作为动力源搭建硬件框架,裁剪主体装置整体集成在一个运动方向上,由上位机发送指令给控制器,控制器解析运动指令后控制模组运动,从而实现任意排样裁剪形状的切割。

图5 四轴裁剪机试验系统

将所提IAHAPSO算法作为方法类写入上位机软件中,当上位机读取到可编译的DXF文件时,调用该方法,优化裁剪轨迹,并可在上位机中可视化路径,由人工确定满足工艺需求情况下,输出可供PLC运动控制器读取的运动G代码指令,从而驱动各轴进行运动裁剪。图6为应用该集成方法对某一排样图形的裁剪路径规划。相较于传统排样软件和人工排样方法,在针对中大型排样数量的裁剪路径优化时,本文所提方法运算时间可在0.5s以内,在一定程度上可有效提高生产效率。

图6 集成软件路径优化结果

4 结语

本文提出一种用于求解旅行商问题的改进自适应杂交退火粒子群算法(IAHAPSO),采用分种群自适应调整惯性权重,且基于模拟退火算子对群体极值进行更新,引入遗传变异算子加大种群发展后期的多样性。通过测试集仿真结果表明:IAHAPSO算法相较于其他改进PSO算法,在收敛速度和精度上都有较大提高,验证了所提算法的优越性。搭建四轴裁剪机实验系统,将所提算法用于解决裁剪样品路径规划过程,较传统求解过程和人工排样方式,求解效率更高,具有一定应用参考价值。