基于多策略融合改进粒子群算法的路径规划研究*

陈旭东,杨光永,徐天奇,樊康生

(云南民族大学电气信息工程学院,昆明 650000)

0 引言

机器人的路径规划问题在机器人导航领域的研究一直都是热点,而路径规划是指机器人根据地图信息寻找起点到终点的一条无碰撞且代价最小的路径。

针对路径规划问题,许多学者提出了众多智能算法应用在路径规划研究中,如蚁群算法、遗传算法、神经网络算法、粒子群算法等智能算法。杨北辰等[1]针对传统蚁群算法存在收敛速度慢、容易陷入局部最优等问题将一种自适应归档更新方法应用在蚁群算法中,根据路径信息建立了多目标性能评估模型,对路径进行多指标优化,提高算法的收敛速度。张毅等[2]将初始化成功的无碰撞路径转化为一连串的栅格地图中栅格序号,再将路径序号转化成路径进行优化,但是该算法中参数选择人需凭借经验选取,且对环境的依赖性强。魏冠伟等[3]利用人工神经网络优化路径,但是由于人工神经网络的局限性,该方法存在收敛速度慢、全局搜索能力差、易陷入局部最优等缺点。

而对于粒子群算法(particle swarm optimization)在路径规划中的应用,其具有收敛速度快,模型简单,待调参数少等特点。但是算法在后期由于种群多样性减少容易陷入局部最优值,使得优化效果并不理想。

国内外许多学者为提升粒子群算法的性能提出了许多改进方法。LIU等[4]在粒子群算法寻优过程中引入非线性惯性权重调整提高了算法性能。花赟昊等[5]通过在粒子群算法寻优过程中同步调整学习因子与惯性权重,提高了算法收敛速度以及收敛精度,并且为增强算法的全局寻优能力引入了变异机制扩大粒子搜索空间。朱任等[6]借鉴了小生境思想,基于粒子群算法基础上提出利用顺序聚类算法将不同的粒子划分到不同的小生境,并根据小生境的迭代数制定不同的搜索策略一次提升算法总体性能。杨妹兰等[7]采用比粒子自身适应值更好的邻近粒子为学习对象,并且分两个阶段用不同更新速度公式,提高了粒子间的信息交流,同时平衡了算法的局部开发性能与全局寻优能力。廖玮霖等[8]利用三黑洞系统捕获策略以及多维随机干扰策略,使算法提高了局部搜索能力同时还兼顾了全局开拓能力,并且通过协调因子从全局寻优转变维向局部搜索,进而提高收敛速度。

上述各改进方法均综合提高了粒子群算法的性能,然而目前改进的粒子群算法大多着重于平衡算法的收敛精度和收敛速度。虽具有一定的改善效果,但是由于两者的矛盾性,提升效果依旧具有局限性。针对所述问题,本文提出一种多策略融合改进粒子群算法应用在路径规划中,首先建立机器人路径规划所需的栅格地图模型,并对传统的粒子群算法作进一步的改进,利用中垂线算法的收敛策略加快算法的收敛速度;以最优粒子爆炸策略避免陷入局部最优解;采用自适应惯性权重更新方法进一步提升算法的性能;最后将全局最优解继续进行局部搜索,提高全局最优解适应度值。

1 多策略融合粒子群算法

1.1 粒子群算法

粒子群算法的核心是利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生问题的最优解。其数学模型为:

(1)

(2)

1.2 多策略融合粒子群算法

1.2.1 中垂线算法

中垂线算法的核心思想是:任意线段的中垂线上任意一点到该线段的两端点的距离相等。示意图如图1所示,假设在一个足够小的区域内(矩形区域)存在一个最优点P和两个随机点M和N,连接MN并作线段MN的中垂线L。由图1可知|PM|<|PN|,因中垂线L上任意点到M点与N点的距离相等,则P点必定位于L左侧M点的区域。在中垂线算法中,以最优点到该点的距离作为适应度,即在图1中M点适应度比N点适应度更好。

图1 算法原理图

以图1为例,中垂线算法的收敛过程为:判定线段|PM|是否小于|PN|,若小于,则判定最优值P必存在于矩形左侧网格区域;舍弃原N点,在矩形左侧网格区域随机生成N′点;作M和N′构成线段的中垂线L′,此时可知,N′点的适应度必定比M点的适应度更佳,由此可知最优值所在区域必存在于L′右侧区域(图1中阴影网格区域)。重复以上步骤可不断缩小最优点P的所处区域。

1.2.2 融合中垂线算法的粒子变化策略

若在图1中右侧区域随机加入粒子G,如图2所示。采用传统粒子群更新策略必然需要经多次更新才能使N点、G点的位置到达中垂线左侧区域。

图2 粒子变化原理图

针对传统粒子群更新速度慢的问题首先将粒子N和G的位置先移动到N′和G′的位置,由于传统粒子群的更新策略会使粒子回到中垂线左侧区域,因此本文采用改进粒子群更新策略更新粒子速度和位置。

粒子移动的实现方式为:首先判断粒子是否存在于最优点所在区域,设:

(3)

式中:d表示粒子维度,假设某粒子存在于最优点所在区域,则x满足:

(4)

式中:j表示x的第j维,

(5)

为减小算法的时间复杂度和增强算法全局寻优能力,判定仅需任意两维元素满足式(3)则位于中垂线左侧区域。

若该粒子位于中垂线右侧区域,则N点更新公式为:

(6)

(7)

为验证中垂线算法的性能,本文选取Rosenbrock函数作为实验函数,验证其全局寻优能力。图3和图4为融合中垂线算法的改进PSO算法寻找Rosenbrock函数最小值时粒子的变化。公式为:

(8)

图3 PSO算法粒子变化图

从图3和图4的粒子位置变化对比可看出,改进PSO算法能够更快收敛到最优值,而传统粒子群算法粒子位置变化太过分散。因此验证了中垂线算法具有很好的收敛能力。

1.2.3 最优粒子爆炸策略

在传统粒子群算法中,全局最佳粒子Gbest按常规更新公式更新时,下一代种群的粒子位置一般会比前一代的粒子位置更差,最优粒子的作用并没有显现出来。因此本文在最优粒子Gbest附近生成一定数量的爆炸粒子,生成方式为:

(9)

由式(9)生成的第n个爆炸粒子exn的j维变量,这些粒子生成于最优粒子的周围。

采用生成爆炸粒子的策略是为了算法更好的跳出局部最优,该策略依旧选取Rosenbrock函数作为实验函数,验证其该策略的可行性。由图5可知,传统PSO算法会陷入局部最优值,而采用最优爆炸粒子策略能够使算法更好的跳出局部最优值。

图5 适应度收敛对比

1.2.4 改进粒子速度更新

利用中垂线算法改进后,若依旧利用传统粒子群算法的粒子历史位置信息反而会导致粒子远离最优点。故粒子速度更新策略变为:

(10)

由于经过最优粒子爆炸策略后,若种群粒子总数为m,在最佳粒子周围生成了n个爆炸粒子,那么m-n个传统粒子按照式(10)更新,新生成的爆炸粒子按照式(11)更新。

(11)

1.2.5 线性动态惯性权重调整方法

在传统粒子群算法中,惯性权值是一个定值。如果取值太大虽然加快了搜索速度但是在算法后期不利于粒子后期小范围的搜索,若取值太小,虽然增加了局部搜索能力但是则不利于算法速度会锐减。针对以上问题,本文采用线性递减规律改变惯性权重。权重ω的变化式为:

(12)

式中:ωmax是最大权值,通常设为0.8;ωmin是最小权值,通常设为0.5;Tmax为最大迭代,t为粒子当前迭代。引入线性动态惯性权重调整方法是为了增加算法的全局搜索能力以及局部探索能力,本文采用Rosenbrock函数作为实验函数进行验证。由图6可看出引入线性动态惯性权重能够很好的提升算法的收敛速度以及搜索精度。

1.3 多策略融合粒子群算法求解流程

根据上述所提策略并将其融合而提出的多策略融合改进粒子群算法的具体步骤为:

步骤1:随机初始化各个参数,如学习因子,初始粒子速度位置,爆炸粒子数目,种群学习率;

步骤2:通过适应度函数计算适应度值;

步骤3:适应度最佳的粒子作为全局最优点M,适应度次优的粒子作为N点;

步骤4:利用式(12)求出粒子惯性权重;

步骤5:利用式(9)生成爆炸粒子;

步骤6:利用式(10)和式(11)更新粒子速度;再由式(2)更新粒子位置;

步骤7:计算所有更新后粒子的适应度值;

步骤8:更新Gbest(M点)和N点的值;

步骤9:结束条件达到则停止搜索,否则回到步骤2继续执行。

1.4 算法时间复杂度分析

假设粒子数为m,最大迭代次数为T,粒子维度为D,爆炸粒子数为e,粒子群算法的时间复杂度主要是粒子速度和位置更新,可知标准粒子群算法的时间复杂度为O(mDT)。由本文算法的步骤可知,在中垂线算法策略中,粒子每更新一次,本文的粒子位置更新策略增加的时间有判断粒子是否处于正确位置以及将粒子移动的时间都是O(mD),而确定两个最优粒子的位置,增加的时间为O(m),舍弃个体历史最优位置则减少的时间为O(m);最优粒子爆炸策略的时间为O(eD);而线性惯性权重调整是减小了算法的运行时间,因此该策略的增加的时间为O(0),则本文算法总的时间复杂度为O(2mDT+eDT),略去低阶项后可知本文算法时间复杂度比标准粒子群算法大致相同。

2 算法性能测试

为了验证多策略融合粒子群算法的可行性和优越性,将本文改进后的算法(MFPSO)与均值粒子群优化算法(MeanPSO)、线性递减惯性权重粒子群优化算法(LDWPSO)、基于终端交叉和转向扰动的粒子群优化算法(TCSPSO)以及文献[8]的多策略融合的粒子群优化算法(MSPSO)[8]在5个基准测试函数下进行对比实验。设置迭代次数为1000,种群数量为80,各算法其他参数设置如表1所示,5个测试函数的取值范围、最小值等信息如表2所示,其中F1～F3为单峰基准测试函数,F4、F5为多峰基准测试函数。本文实验平台为:MATLAB 2022(Intel Core i5,2.11 GHz CPU and 16 GB RAM)。

表1 各算法参数设置

表2 基准测试函数

为了验证本文算法的性能,本文使用两组基准函数进行测试并且从收敛速度和收敛精度两方面来对比,为了降低由于偶然性引起的实验误差,本文分别在5个测试函数中独立进行50次实验。测试函数的收敛曲线对比如图7所示,实验结果如表3所示。其中横坐标代表迭代次数,纵坐标代表适应度的对数值。

表3 实验数据

(a) F1测试函数收敛曲线对比 (b) F2测试函数收敛曲线对比

从图7a～图7e可以看出,本文算法相较于其它4种算法,在收敛速度以及收敛精度方面具有很大的提升。本文算法不仅寻优精度明显优于其他5种算法,同时在算法初期由于引入了中垂线算法增加了粒子的游离速度,使得算法前期收敛速度明显加快。并且能够在较少的迭代次数就能达到较好的寻优精度,这是因为在粒子速度更新阶段引入了线性递减规律惯性权重,使得算法能够更好的平衡全局搜索能力以及局部拓展能力,具有更好的搜索范围,而其余算法不同程度的出现了停滞过程,寻优精度较低等问题。由表3可以看出,测试函数为F1～F3和F5时无论是单峰或多峰基准测试函数,本文算法在独立实验结果的最小值和均值都是最小,而当测试函数为F4时,最小值虽与MeanPSO、TCSPSO、MSPSO相等,但是平均值相较于其余4种算法是最低的。综上所述,本文改进的MFPSO算法整体性能优于其他4种改进算法。

3 多策略融合粒子群算法在路径规划中的应用

3.1 全局最优解局部搜索策略

传统PSO算法的初始化策略通常为随机策略,在算法末期,可能得到的全局最优解并不是最优的解,针对此问题,本文在算法末期采取把全局最优解(最优路径)继续进行局部搜索,如果新的适应度值小于原先适应度值,则将新路径作为最优路径。效果对比图(以20×20为例)如图8～图10所示。

图8 传统PSO路径规划

图10 路径长度对比

从图8～图10可以看出,采取全局最优解局部搜索策略的粒子群路径规划能够将传统粒子群产生的最优路径继续搜索寻优得到更佳的规划路径。

3.2 适应度函数建立

机器人路径规划是根据地图信息寻找起点到终点的一条无碰撞且代价最小的路径。其代价函数是检验算法优化程度的重要指标。本文代价函数分成两部分,第一部分用来判断路径的长短,第二部分用来判断平滑程度。路径长度的计算公式为:

(13)

式中:fit1为相邻点的距离的和,d表示维度。

平滑度的计算公式为:

(14)

路径中机器人行进的角度有4种情况,分别为直线、钝角、直角和锐角,其中直线平滑度最好,钝角、直角次之。由于机器人行进中锐角是不允许的,所以对除直线外的另外3种情况给予惩罚,可以根据实际情况更改惩罚值大小。

fit2=1/(fit2+c)

(15)

适应度函数的两部分分别取一个权重值,则适应度函数公式如下:

f=a·fit1+b·fit2

(16)

式中:a、b分别为长度因子、平滑度因子,可根据路径长度和平滑度之间的权重选择参数a和b。

3.3 路径规划问题

为进一步验证本文提出的融合多策略改进的粒子群算法的实用性与可行性,本文采用传统栅格地图来模拟机器人的工作环境。黑色区域为障碍物,把白色区域为可行区域,其中深灰色点标志(左下角)为机器人的起始点,浅灰色点标志(右上角)为机器人的结束点;地图的边界是整个路径规划的最外围区域,当成障碍对待。

本文采用在20×20与30×30规模的简单栅格环境和20×20与30×30规模的复杂栅格环境,将本文改进粒子群算法用于栅格地图路径规划问题中,并与文献[8]算法(MSPSO)、传统粒子群算法(PSO)、麻雀搜索算法(SSA)、进行对比并记录平均路径长度、最优路径长度。本文粒子群初始参数设置为:迭代次数为500;种群数量设置为100;权重系数最大值ωmax为0.9;权重系数最小值ωmin为0.4;社会因子c2设为2。

3.3.1 简单环境

各算法在20×20栅格地图简单模型的最短规划路径对比如图11所示,在30×30栅格地图简单模型的最短规划路径对比如图12所示,简单环境的最优路径收敛曲线对比如图13所示,各算法实验数据统计如表4所示。

表4 简单环境各算法路径统计表

(a) MFPSO (b) MSPSO

(a) MFPSO (b) MSPSO

(a) 20×20简单路径收敛曲线 (b) 30×30简单路径收敛曲线

由图11和图12可得,本文算法在20×20、30×30的简单环境下找到的最优路径均优于其余3种算法;从表4可以看出在20×20栅格地图得到最优路径是27.649 2,比MSPSO减少了0.806 2,并且在30×30栅格地图下,得到的最优路径比MSPSO减少了2.474 3,由此可以说明MSPSO在较复杂的栅格地图环境的搜索精度会降低;从图13可以看出MSPSO虽然在算法初期能够快速的收敛到最优值,但是正在后期存在搜索能力不足,搜索精度不够。

3.3.2 复杂环境

各算法在20×20栅格地图复杂模型的最短规划路径对比如图14所示,在30×30栅格地图复杂模型的最短规划路径对比如图15所示,复杂环境的最优路径收敛曲线对比如图16所示,各算法实验数据统计如表5所示。

表5 复杂环境各算法路径统计表

(a) MFPSO (b) MSPSO

(a) MFPSO (b) MSPSO

由图14和图15最优路径对比图可知,算法都能够实现到达终点且寻找到了最优路径的目的。但是除了MFPSO和MSPSO,其它算法路径的波动性明显,并且路径会经过障碍点,生成的路径平滑度差、距离长、算法规划出的路径存在绕弯路甚至于规划出有障碍的路径等情况。而本文算法相对MSPSO,本文提出的改进粒子群算法在路径长度和路径平滑度上都优于MSPSO,能够迅速的找到路径最短且不经过障碍物的最优路径,且路径平滑度也适于机器人实际运动轨迹。

由图16最优路径收敛曲线反应的情况可知由于 MFPSO能迅速收敛至最小适应度值,这是由于通过中垂线算法(MA)优化粒子群算法的粒子位置变化,搜索前期加快了粒子群的收敛能力;搜索后期采用最有粒子爆炸策略与全局最优解局部搜索策略使算法不易陷入局部最优解,增强了全局搜索能力。综上所述,本文提出的多策略融合粒子群算法无论在收敛速度还是寻优能力都优于其它4种算法,因此将本文算法应用在机器人路径规划中能有效的减小机器人规划路径的长度。

由表5各算法的路径规划统计数据可知,可以清楚的看出MFPSO具有更好以及更稳定的最优路径规划能力。两种不同规格地图环境下MFPSO得到的最短路径长度分别为28.627 4和48.472 2,均小于其它算法得到的最短路径,且MFPSO的平均值也最小,由于最优路径长度反映了算法的有效性和优越性;而平均值则反映算法进行路径规划的稳定性。因此由结果可知把多策略融合改进的粒子群算法应用在移动机器人路径规划中具有一定的优势。

4 结论

针对传统的粒子群算法在移动机器人路径规划中存在惯性权值不适、迭代后期粒子群体多样性下降等问题,提出一种融合多策略的改进粒子群搜索算法(MFPSO)。改进后的粒子群算法具有更快的收敛速度和寻优能力,同时也加强了跳出局部最优解的能力。在算法初期,利用中垂线算法的收敛策略加快算法的收敛速度;采用自适应惯性权重更新方法进一步提升算法的性能,在算法后期以最优粒子爆炸策略使算法跳出局部最优值;再将全局最优解继续进行局部搜索提高机器人路径的规划能力。仿真结果表明,本文所提出的多策略融合改进粒子群算法在机器人路径规划中展现出更好的路径寻优能力。