基于改进离散粒子群优化算法的路径规划

张红柱，蒋 奇

(山东大学控制科学与工程学院，山东 济南 250061)

1 引言

路径规划在机器人的生产实践中占据着重要地位，其目的是在复杂工作环境中规划出一条从初始点运动到工作点的最短路径，确保机器人在无碰撞条件下安全到达工作地点。目前已存在的机器人路径规划算法主要有两种：一种是传统算法，如栅格法和人工势场法等。另一种是智能仿生算法，如蚁群算法、遗传算法和粒子群算法(Particle swarm optimization，PSO)等，智能仿生算法为解决复杂环境下路径规划问题提供了新思路。

粒子群算法一经提出，得到广大学术界的关注。文献[7]对传统PSO进行改进，使用自适应惯性权重因子更新公式，加快算法的收敛速度。文献[8]对线性变化的加速因子进行扰动，有效改善粒子的早熟现象。文献[9]提出一种双向学习粒子群改进算法，利用典型函数进行测试，结果表明改进算法明显提高了粒子的收敛速度和寻优能力。文献[10]采用余弦变化公式更新惯性权重因子和加速因子，算法在运行过程中达到更佳的配合效果，收敛速度有所提高。文献[11]将莱维飞行加入到离散粒子群算法，并成功求解出点焊机器人较优的工作路径。文献[12]采用二进制粒子群优化算法实现了机器人在栅格地图中的路径规划。

受文献[9-12]的启发，本文提出一种基于反向学习机制的离散粒子群优化算法。算法初始化阶段对全部粒子引入反向学习机制，选择距离目标点更近的粒子作为初始种群。迭代过程中以概率α保留反向粒子与原始粒子交换序中的交换子，采用文献[9]中惯性权重更新公式，并提出一种新型自适应余弦变化的学习因子更新公式，使算法在运行过程中达到更佳的配合效果，提高收敛速度和精度。

2 模型建立与问题描述

在建立机器人工作空间运动模型时，便于将机器人看成一个尺寸可以忽略不计的质点，作如下假设：1)机器人在有限的二维空间内进行运动；2)机器人工作空间中存在已知的静态障碍物，且忽略障碍物的高度；3)在障碍物原有边界四周添加安全裕度和机器人本体长宽方向最大尺寸的1/2。建立单个障碍物模型，如图1所示。

图1 单个障碍物模型

机器人的工作空间由障碍物区域和可行域组成，本文采用优化后的栅格建立机器人的工作空间，用1表示黑色障碍物区域，0表示机器人的可行域。当障碍物未填满一个栅格时，按一个栅格计算。假设图2a为机器人的实际工作空间，进行障碍物处理后的工作空间为图2b，多个障碍物处理过程，如图2所示。

图2 多个障碍物处理过程

建立上述工作空间模型后，可将机器人的路径规划转换为在栅格地图中寻找初始位置运动到目标位置经过点集合的问题。假设是机器人的初始位置，是目标位置，算法为机器人规划出的一条路径为：[，，，…，，]，其中，，，…，为机器人在栅格地图中运动时经过的点，且任意一点均处于可行域空间，相邻两点之间的连线不存在障碍点。将机器人运动过程中的路径长度作为适应度函数，数学表达式如下：

(1)

式中，和分别为机器人在栅格地图当前位置的横坐标和纵坐标，+1和+1分别为机器人移动到下一位置的横坐标和纵坐标，为机器人运动过程中历经的总点数。

3 粒子群算法及反向学习算法

3.1 基本粒子群算法

1995年，Kennedy和Eberhart首次提出粒子群算法，每个粒子通过自我学习和群体学习向空间中的最优点运动，通过不断迭代搜索到最优解。数学理论如下：在维空间中，第个粒子的速度为=(1，2…，)，位置为=(1，2…，)，粒子经过的最优点为=(1，2…，)，种群经过的最优点为=(1，2…，)，粒子的速度和位置更新公式如下

(+1)=()+(()-())+

(()-())

(2)

(+1)=(+1)+()

(3)

式中，为惯性权重，为自我学习因子，为社会学习因子，和分别为[0，1]区间内的随机数。

3.2 离散粒子群算法

1997年，Kennedy等提出离散二进制粒子群算法。为了将离散粒子群算法应用到本文的机器人路径规划中，引入交换子和交换序的概念，并重新定义相关的操作运算符。

1) 交换子：解序列为=()，(=1，2，…，)，将交换子(，)定义为交换序列中第个和第个位置的元素。

2) 交换序：一个或多个交换子的有序序列。

3) 乘法算子(·)：序列中各元素的值以常量概率保留。

4) 减法算子(-)：求解两个序列的差集，生成一个交换序。假设序列为(1，3，5，7，9)，序列为(3，1，5，7，9)，则序列与序列的差集可以表示为-=(1，2)，其目的是计算两个粒子位置的转换式。

5) 合并算子(⊕)：表示将两个交换序合并，将后一个置换序列加入前一个序列的末尾，组成一个新的交换序。

6) 加法算子(+)：执行交换序，得到新解。

3.3 反向学习算法

2005年，Tizhoosh首次提出反向学习算法，基本思想是比较变量当前点和反向点的估计值，进而确定最优值，相关定义如下。

4 基于反向学习的离散粒子群优化算法

改进算法分两阶段对粒子引入反向学习机制：第一次在种群初始化时，目的是提高初始解精度；第二次在迭代过程中，目的是增加种群多样性，改善粒子的早熟问题。采用改进惯性权重和新型学习因子更新公式，在迭代过程中达到更佳的配合效果。

4.1 种群初始化

算法的搜索性能很大程度上取决于初始种群的分布情况。传统PSO的初始种群是随机生成的，本文改进算法的初始化阶段在随机生成初始群体的基础上对全部粒子引入反向学习机制，并比较反向粒子与当前粒子的适应度值，选择适应度值较小的粒子作为最终初始种群。故初始化阶段选择距离目标点较近的粒子作为初始种群，提高初始解的精度，加快算法的收敛速度。

4.2 参数改进

4.2.1 迭代过程引入反向学习机制

传统PSO后期种群多样性急剧下降，容易导致粒子陷入局部最优难以跳出。改进算法在迭代过程中以概率对粒子种群引入反向学习机制，即以概率保留反向粒子与原始粒子交换序的交换子，增加种群的多样性，在一定程度上改善粒子的早熟问题，本文设置的保留概率为=01。

422 改进惯性权重

算法的全局和局部搜索能力很大程度上取决于惯性权重的大小。当较大时，具有较强的全局搜索能力；当较小时，具有较强的局部搜索能力。在迭代过程中，从大到小变化有助于算法达到更佳的搜索效果。本文采用文献[16]惯性权重更新公式，迭代过程中惯性权重的变化曲线如图3所示。

(4)

式中，和分别为惯性权重的最大值和最小值，为本次迭代次数，T为最大迭代次数，()为第次迭代时的惯性权重。

图3 ω变化曲线

423 改进学习因子

自我学习因子影响粒子的个体学习，当较大时，粒子具有较强的探索能力，有助于搜索到全局最优位置。社会学习因子影响粒子群之间的相互学习，当较大时，粒子具有较强的开发能力，有助于收敛到全局最优位置。为保持良好的搜索性能，迭代过程中应逐渐减小，增加。本文提出一种新型自适应余弦变化公式更新和，数学表达式如下

(5)

(6)

式中，和为的最大值和最小值，和为的最大值和最小值。

根据式(5)画出迭代过程中自我学习因子的变化曲线，如图4所示。

图4 c1变化曲线

根据式(6)画出迭代过程中社会学习因子的变化曲线，如图5所示。

图5 c2变化曲线

本文的改进算法引入交换子和交换序的概念，加入反向学习机制，改进惯性权重，采用新型自适应余弦变化公式更新学习因子，将粒子的速度和位置更新公式改写成以下形式：

·(()-())⊕·(()-())

(7)

(+1)=()+(+1)

(8)

4.3 算法流程

本文算法的实现流程如下所示：

1) 种群初始化分以下四步。

a) 设置初始种群数量为20，初始迭代次数=0，=09，=04，=02，=05，=04，=07。

b) 随机生成初始种群，计算每个粒子的适应度值，确定粒子个体最优位置和最优适应度。

c) 对全部粒子执行反向学习算法，计算反向粒子的适应度值，并与当前粒子适应度值比较，选择适应度值较小的粒子作为初始种群。

d) 比较并确定当前粒子个体最优位置、个体最优适应度值、全局最优位置及全局最优适应度值。

2) 进入迭代机制，根据式(4)，式(5)和式(6)分别更新，和。

3) 根据式(7)和式(8)更新粒子的速度和位置。

4) 根据式(1)计算当前粒子适应度值，并与更新前的值进行比较。若适应度值较小，则更新个体最优位置和最优适应度，否则保持不变。

5) 更新当前的全局最优适应度值，将其与更新前的值进行比较。若适应度值较小，则更新种群的全局最优位置和最优适应度，否则保持不变。

6) 迭代次数加1，判断是否达到最大迭代次数。若是则输出最优结果，结束迭代。否则返回2)继续迭代，直至达到终止条件。

改进算法流程图，如图6所示。

图6 改进算法流程图

5 仿真及结果分析

为验证改进离散粒子群优化算法的性能，本文利用Matlab R2014a作为仿真平台，将20×20的栅格地图作为仿真环境，进行机器人的路径规划实验。设置机器人初始点坐标为(05，05)，目标点坐标为(195，195)，粒子种群数量为20，最大迭代次数为200。为保证算法的可靠性，将本文改进算法、基本离散粒子群算法(设置其中参数=05，=05，=05)和文献[17]中的改进离散粒子群算法(线性变化，且∈[04，09]，=05，=07)独立运行20次，对比指标选取算法搜索到最短路径的成功率，搜索到路径的平均值及平均误差率。成功率和平均误差率的数学表达式如下

(9)

(10)

假设算法搜索到的路径长度为L，收敛代数为t，对比数据如表1所示。

表1 算法对比数据

表1对比数据看出，本文改进算法搜索到最优路径的成功率远高于其它两种算法，显示了改进算法在寻优精度方面的优势。在算法搜索路径的平均值和平均收敛代数指标上，改进算法也有一定程度的提高。算法平均误差率更低，算法较稳定，验证了改进算法的有效性。

算法规划出的最优路线，如图7所示。

图7 最优路线

最优路线对应的收敛曲线，如图8所示。

图8 收敛曲线

6 结论

本文针对已知环境下机器人的路径规划问题，提出一种基于反向学习机制的改进离散粒子群优化算法。仿真结果表明，改进算法能够规划出使机器人在无碰撞条件下由初始点运动到目标点的最短路径，增加了算法搜索到最短路径的成功率，且加快了算法的收敛速度，提高了算法的寻优能力。说明改进算法在求解机器人路径规划问题时具有可行性和有效性，可以为后续机器人路径规划的具体实现提供借鉴意义。