改进粒子群算法的机器人路径规划

盛雪松

摘 要：对于传统的粒子群算法在路径规划时，粒子容易陷入局部的最优解、路径质量较为差的问题，本文提出了相应的改进的粒子群算法。主要有线性惯性权重的粒子群算法，可以随着算法的迭代，惯性权重不断减小，使得后期的局部搜索能力增强在采用该算法之后。以及通过粒子群算法与生物地理学优化算法相结合，在路径寻优的过程中增加了迁移操作来帮助粒子脱离困境，从而避免了粒子陷入死循环或者局部最优的结果。

关键词：传统粒子群算法;线性惯性权重粒子群算法;迁移操作的粒子群算法

一、引 言

移动机器人路径的规划问题一直是机器人导航领域的研究的焦点，移动机器人的路径规划是指机器人在有障碍物的工作环境中根据起止点和终止点的信息坐标，搜索出一条能耗低、所用时间少、距离更短并且能避开所有障碍物的有效路径[1]。

近些年来，一些新兴的算法，比如遗传算法、蚁群算法、粒子群算法、蜂群算法等。相较于传统的一些算法，通過模拟大自然生物的一种或几种行为进而提出的一种智能仿生算法，为解决比较复杂的环境下的路径规划问题提供了新的思路[2]。本文在粒子群的基础上进行改进，弥补了传统粒子群算法在搜索过程中容易陷入局部最优的这种缺点[3]。

二、传统粒子群算法的路径规划

（一）传统的粒子群算法

通过对鸟群捕食行为研究，提出了粒子群算法，其在求解优化的问题时，问题的解对应于搜索空间中的一只鸟的飞行位置，这样成为一个“粒子”。每个粒子都通过跟踪群体所经过个体的最优解和整个种群的全局最优解的影响来不断更新自己，从而产生下一轮新的群体[4]。粒子的速度以及位置更新公式如下：

式中：表示第次迭代中的第维速度;表示第次迭代中的第维的位置;为惯性权值;和为学习因子;为分布在之间的随机数。

（二）算法的目标函数

粒子的路径规划就是搜索一条从起点到终点的无碰撞最短的路径，其目标函数可以表示为

三、改进的粒子群算法的路径规划

（一）线性惯性权重的粒子群算法

在基本的粒子群算法中惯性权值是一个固定的值，当较大的时候，粒子的全局搜索能力较强，但是局部的搜索能力比较的弱，可能会使粒子飞过最低点。当较小的时候，可以使得粒子的局部搜索能力变强，但这样粒子往往容易陷入局部最优解，而失去全局的寻优能力。通过改变权重对粒子群的搜索功能进行改进，即随着迭代的过程，不断的减少惯性权重的值，这样算法在初期的探索能力较为强，可以再比较大的空间范围内搜索，在后期，权值的减小，使得可以收敛到较好的区域，进行更为细致的搜索，权重变化式如下：

式中：为最大权值;为最小权值;为最大迭代次数;为粒子当前迭代次数。其算法流程和基本粒子群算法较为相似，只不过最后要进行判断算法是否满足终止条件，不满足的话，则调整值，重新更新粒子的速度与位置继续循环。不过随着优化问题的不同，线性惯性权重的调整策略也不相同，这就使得线性惯性权重的粒子群算法在应用中有很大的局限性。

（二）生物地理学优化算法

生物地理学优化算法，也常被称作BBO算法。在该算法中，我们用适用度指标（habitat suitability index，HSI）来具体量化所研究的地区物种的适应情况，如果计算显示的HSI指标较高，说明该地区物种种类比较丰富，处于相对稳定的状态，比较适合物种的生存;同样，当研究显示的HSI指标较低时，表明该地区物种种类比较匮乏，尚未饱和[5]。在生物地理学的理论中，该地区是否适合生存，必然会引起物种的迁移，即：HSI越高，说明该地区能容纳的外来物种相对有限，其对应的迁入率和迁出率都会比较小;当HSI越高，表明可容纳的物种比较充裕，对应的迁入率会比较大，而迁出率比较小。

针对上述物种数量和迁移的关系，总结如下：

（1）随着区域内物种数量的不断增加，外来物种的迁入会加剧拥挤程度，因此潜入率会逐渐减小，同时由于竞争关系，会导致一部分物种从该区域迁出，使得迁出率不断增加;

（2）当物种数量S增加至极限时，处于饱和状态，区域内的物种只能出不能进，对应的迁入率将至0，而迁出率会增长到最大，即最大迁出率;

（3）如果该区域内物种数量为0时，其迁出率必定为0。

（三）迁移操作

迁移操作是生物地理学优化算法的核心步骤，在优化的过程中，通过物种种群的不断迁入、迁出操作，可以不断的改变区域系统内的的适应度指标HSI。

如果将最大迁出率E、最大迁入率I设置为1，可容纳物种的区域数量用来表示，对应的某一个区域用表示，其对应的第维的适宜度分量用来表示。通过上述的分析可以看出，迁入和迁出操作实际上是通过区域间信息的不断交互实现对大面积区域的空间搜索。

迁出操作的更新过程需要借助随机数，可总结为：

对于区域，如果，则由迁入率决定将要被替换的区域，执行迁移操作.，并且。如果，则不执行迁移操作。如此循环，直到对所有的变量都执行完上述操作，就产生了一个新的区域。然后对下一个区域进行操作，如此循环，直到所有区域都完成此操作。利用迁入率的选择方法为：计算其余max-1个区域的迁入率，根据贪婪算法求出第一个满足的区域。

同样的迁入操作的更新过程与此相似

因此可以看出，当区域的适应度越大，表明所能接受的物种数量的总数就越高，当区域的适用度越小时，所能接受的物种数量的总数就越少。针对上述关系可以将物种数量用适应度函数值替换：

其中，和分别表示当前栖息地种群中适应度函数的最大值和最小值。

（四）基于迁移操作的改进粒子群算法

为了有效避免粒子群算法在迭代过程中容易陷入局部最优的缺点，充分提高粒子的全局以及局部的搜索能力，提高算法的收敛性能，将生物地理学优化算法与改进后的粒子群算法相结合，当粒子适应度较差时，通过对该粒子施加一定概率的迁移操作，增加粒子的迁入和迁出效果，使得该被困粒子可以顺利的离开被困区域，达到动态调整搜索步长和优化粒子的更新策略，从而避免了粒子陷入死循环或者局部最优的结果，使得算法性能更优[8]。

在粒子迭代的过程中，如果经过连续的三次更新后，该粒子的适应度值仍然小时，我们则定义该粒子陷入了死区，此时，需要外力强制介入迁移操作，帮助粒子脱离困境。因此，本文将判断粒子是否处于死区的方法设定为：对适宜度值的粒子，需要计算其最近三次迭代（包含本次）目标函数值的方差，若小于设定值，则认为该粒子陷入死区。

基于生物地理学优化的算法的原理，结合粒子群的特点，可将迁移操作定义如下：

其中：表示迁移操作的力度;表示当前迭代下的全局最优值;表示个体在当前迭代下该粒子的历史最优值;表示进行迁移操作的系数，其与粒子陷入死区的程度有关。

当粒子并未陷入死区时，，表示不进行迁移操作;而当系统判定粒子陷入死区时，参考，生物地理学的迁入率和迁出率，将定义为：

其中：表示当前粒子的适用度值;表示粒子种群中适应度最小值;表示粒子种群中平均适应度。

由上式可以看出，当粒子的适应度越差，即陷入死区的程度越深，迁移系数越大，即表示将要执行的迁移力度越大，通过较大的迁移来影响该粒子的速度和位置更新。

本文将在改进后的粒子群算法中加入迁移操作，将粒子群的迭代过程中增加了遷入、迁出操作，具体表现如下：置一个概率值，对于第个粒子，如果>，则对进行迁移操作，使用基于迁入率的迁移操作进行位置更新;如果，则进行迁移率的操作，执行基于迁出率的迁移操作进行位置更新;如果值相等，则进行到执行不进行迁移操作。其中randn（0，1）表示均值为0，方差为1的高斯分布。

通过上述改进之后，当经过三次判断该粒子陷入死区时，使用下式对粒子进行更新：

三、全局路径规划仿真和结果分析

应用栅格法建立环境地图，在环境中采用上述的粒子群算法、惯性权重粒子群算法、迁移操作的粒子群算法进行路径的规划并比较分析三种算法在简单以及复杂环境中的寻找最佳路径长度的能力。

进行了五次仿真，在复杂情况下，迁移操作的粒子群算法都可以得到更小的目标函数即路径长度。

由以上的仿真图还有收敛曲线可以得知：在复杂的环境下，基本粒子群算法迭代了182次之后陷入了局部最优解，其最优的路径适应度函数为72.8112。线性惯性权重的粒子群算法在21次迭代得到局部最优解，其路径的函数为69.98291。而采用了迁移操作的粒子群算法，在进行路径的规划时，当迭代了480次时跳出局部的最优解，在当前最大迭代次数下，最优最有效的路径适应度函数为64.3259。综上所述，迁移操作的粒子群算法在复杂的环境下所能得到的路径长度更短。

四、结束语

传统的粒子群算法对于机器人路径规划中具有建模简单、计算过程简单、收敛性速度快以及参数较少等优点，但是也较容易陷入局部的最优解，从而在一下复杂环境下得不到全局的最优解，使得优化结果不理想。因此结合了迁移操作的粒子群算法，能够弥补以上缺点。并通过计算机仿真验证了该算法的有效性，合理性，是优于传统的粒子群算法的。

参考文献

[1]张颖，吴成东，原宝龙.机器人路径规划方法综述[J].控制工程，2003，10（5）;152-155.

[2]孙波，陈卫东，席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策，2005，20（9）;1052-1055.

[3]李伟莉，赵东辉.基于栅格法与神经元的机器人全区域覆盖算法[J].机械设计与制造，2017（08）：232-238.

[4]刘旭.粒子群算法及其应用发展[J].科技经济导刊，2018，26（04）：138-139.

[5]秦树辉等著.生物地理学.北京：科学出版社，2010.