改进粒子群算法在移动机器人路径规划中的应用*

2018-03-06赵开新王东署

火力与指挥控制 2018年2期

魏勇，赵开新，王东署

（1.河南工学院，河南新乡 453002；2.郑州大学电气工程学院，郑州 450001）

0 引言

路径规划是移动机器人研究领域的首要问题之一，目前，国内外学者已经提出了许多研究方案，如蚁群算法［1］、模拟退火算法、遗传算法［2］、神经网络算法［3］、粒子群算法等智能算法。随着移动机器人的应用领域越来越广泛和应用环境的越来越复杂，基本的智能算法很难直接应用到移动机器人路径规划中，本文把差分进化算法引入到粒子群算法中，并通过动态调整差分进化算法的参数，来进一步改善粒子群算法的性能，通过仿真实验分析，验证了改进后粒子群算法在移动机器人路径规划中的效率。

1 粒子群算法

粒子群算法［4-5］（Particle swarm optimization algorithm，PSO）是由 Eberhart和 Kennedy在 1995年根据鸟群的捕食和返巢活动而提出的一种启发式算法。其基本思想是通过群体中个体的合作机制来迭代寻找鸟群移动过程中的最优路径。

1.1 粒子群算法的数学模型

在粒子群算法中假设种群粒子个数为N，维数为D，每个粒子在D维空间上t次迭代的位置为，每个粒子的速度为，其中，迭代中粒子i按式（1）更新粒子速度，按式（2）更新粒子位置［6-7］。

式（1）中，ω为惯性权重系数，c1和c2为个体和群体依赖因子，用于调节粒子对个体最优解位置和群体最优解位置的依赖程度，表示粒子i在d维的个体位置最优解，表示粒子群体d维的最优解，r1，r2为大于0，小于1的随机数。

1.2 粒子群算法存在的问题

粒子群算法虽然简单、收敛速度快，但是在搜索后期，会缺失粒子的多样性而出现算法停滞现象，容易陷入局部最优解，本文在算法搜索后期通过空间聚合度来计算各粒子和种群最优粒子的距离以及各粒子之间的距离，来确定粒子群算法是否出现停滞现象。

式（3）中，dmax为各粒子中与最优粒子之间的最大距离，式（4）中dave为各粒子与最优粒子之间的平均距离，当dmax与dave的值相差不大时，推测粒子群算法可能进入停滞状态。

2 差分进化算法的引入

差分进化算法［8］（Differential Evolution，DE）是由Storn和Price提出的一种群体智能优化算法。算法中通过个体间的差分量来扰动种群中的个体，达到种群个体的多样性。当粒子群算法后期出现停滞，可以引入差分算法，来避免粒子群算法搜索后期局部最优解的产生，算法的具体步骤如下。

2.1 变异操作

差分进化算法（Differential Evolution，DE）通过变异来实现对种群个体进行扰动，具体方法是从原种群中选取3个不同的个体，经过式（5）来产生新的个体。

式（6）中，CRmin为最小变异概率，CRmax为最大变异概率，式（7）中代表最优个体，代表最劣个体，Rmax为最大缩放因子，Rmin为最小缩放因子。

2.2 交叉操作

式（8）中，j表示第j个变量，CR是变异概率，由式（8）动态调整，x'ij是交叉后产生的实验变量。

2.3 个体的选择

如果试验个体的适应度值大于原个体的适应度值，则用试验个体代替种群中原来的个体，否则迭代中仍使用原个体。

3 改进的粒子群算法在移动机器人路径规划中的应用

把引入差分进化算法的粒子群算法（Particle swarm optimization based on Differential Evolution）称为PSOBDE算法，移动机器人路径规划的目的就是从起点到终点找到一条无碰撞的距离最短的一条路径，而PSOBDE算法可以使粒子快速地从源点到目的节点找到一条最优解路径，因此，可以把PSOBDE算法应用到移动机器人路径规划中，协助机器人高效地找到的路径。具体步骤如下：

步骤1：设置机器人运动的环境、起点和终点，初始化PSOBDE算法的各参数，设置粒子群的规模m、粒子群的初始速度；

步骤2：由适应度函数求出粒子群中各粒子适应度值；

步骤3：根据式（2）更新粒子的下一个时刻的位置和速度信息；

步骤4：如果达到迭代次数则结束程序，否则根据式（3）和式（4）计算 dmax与 dave，如果通过比较算法没有停滞，则转到步骤2，如果算法停滞则根据式（5）～式（8）进行变异交叉，通过式（9）选择出优秀个体转入步骤2。

4 仿真实验及分析

4.1 仿真环境

在 Intel i5-6500，内存 4 G，MATLAB 8.5平台上进行仿真实验，设定障碍物分布在已知的全局静态10×10的栅格矩阵环境中，机器人起点坐标为（1，2），终点坐标为（9，9），PSOBDE 算法各参数：种群规模N为30，维数D为8，最大迭代次数为60，适应度函数采用 Rosenbrock，Fmax=0.9，Fmin=0.3，CRmin=0.3，CRmax=0.9，图1中黑色填充单元格为障碍物。

4.2 实验结果分析

图1中虚线为基本粒子群算法找到的从起点（1，2）到终点（9，9）的路径，实线路径为由 PSOBDE算法找到的从起点（1，2）到终点（9，9）的路径，仿真结果表明在相同环境下，搜索初始阶段两种算法的搜索效率差别不大，而在搜索后期，基本粒子群算法存在了停滞现象，导致了次优解的形成并且最终没被修改，而PSOBDE算法在搜索后期出现停滞时，引入了差分进化算法，来重新产生新的个体，增加了种群中个体的多样性，这些新的个体接着执行粒子群算法，避免了局部最优路径的产生，最终找到了较优的搜索路径。验证了PSOBDE算法的有效性。

图2中当采用标准粒子群算法进行路径规划时迭代38次算法收敛，收敛路径长度为17.851，当采用PSOBDE算法进行路径规划时迭代20次算法收敛，收敛路径长度为15.981，可以看出本文中优化的粒子群算法收敛速度更快，收敛路径更短，效率更高。