动态扩散粒子群算法及在机器人路径规划上的应用

李文元 李岚

【摘 要】针对粒子群算法对高维函数优化性能不佳问题，提出了一种动态扩散粒子群算法，并将其应用于移动机器人路径规划中。该算法通过引进动态调节数，动态的选择粒子的运行轨迹，阻止种群在演化过程中搜索效率降低的缺陷，提高算法的寻优性能，在处理大规模函数优化及移动机器人路径规划方面具有更强的寻优能力及更高的搜索精度。

【关键词】粒子群算法；大规模函数优化；动态调节数；路径规划

1.引言

粒子群算法（ Particle Swarm Optimization， PSO）是基于一定假设条件下源于对鸟类捕食行为模拟的一种新型的仿生优化算法。该算法以其结构简单、计算速度快受到国内外众多学者的广泛关注并成功地应用于函数优化，神经网络训练[3]等领域。近年来随着科学技术的不断发展，面对复杂程度越来越高的优化问题，PSO算法在求解质量和优化速度上显得“不尽人意”。尽管国内外学者提出了各式各样的改进方案提高PSO算法性能，但其理论及应用研究还有待进一步的扩展。

本文提出一种动态扩散粒子群算法（A dynamic diffusion particle swarm optimization algorithm，DDPSO）。该算法在演化过程中通过有选择的动态的调整粒子的飞行轨迹，加强对种群信息的利用，增强种群的多样性，从而提高算法的性能。实验结果表明该方法在处理高维函数优化问题及机器人路径规划问题时效果理想。

2.粒子群算法

PSO算法中的每个个体我们称它为一个粒子，每个粒子模仿鸟的寻食行为，通过跟踪两个“极值”来搜索解空间的最优值：一个是每个粒子当前已搜索到的极值，称为个体极值；另一个是整个群体当前已搜索到的极值，称为全局极值。

设函数优化问题描述为

（1）

其中：为目标函数，为自变量的维数，为的搜索区间。

PSO算法是基于群体智能的迭代演化技术，群中的每个粒子代表了目标函数的一种可能解。粒子速度位置更新公式如下：

（2）

（3）

其中为粒子的速度；是粒子的当前位置；为迄今搜索到的个体最优解；为整个群体迄今搜索到的最优解；是保持原来速度的系数，称为惯性权重；和被称为学习因子； 、是[0，1]区间内均匀分布的随机数。群体在演化过程中，粒子每一维上的速度不超过最大运行值，粒子的位置也限制在一定的范围内。同时，与在演化过程中不断更新，最终输出的即为算法得到的最优解。

3.动态扩散粒子群算法

粒子在复杂环境中搜索能力的强弱决定算法性能的好坏。从粒子群算法的基本公式我们可以看出，群体在演变过程中对周围环境的利用能力变的越来越弱，表现为在演变末期粒子几乎处于停滞不动，这说明了群体对信息交流并不十分明锐，限制了粒子群优化算法的搜索能力，使粒子群优化算法容易陷入局部最优，即存在早熟收敛的问题。本文为了提高粒子在复杂环境中的搜索能力，提出了一种动态扩散粒子群算法，该算法通过动态调节粒子的运动轨迹来增强算法的搜索性能。

3.1动态调节粒子运动轨迹

粒子群算法中代表了粒子现在位置与其下一步目标位置之间的距离，值的合理选择有利于群体在演化过程中寻找最佳位置，为了更好的寻找合适的值，本文提出了动态调节粒子运动轨迹的策略，以此调节粒子在演化过程的速度，提高算法动态搜索能力。其数学表达方式如下：

（4）

式中是[0，1]区间内均匀分布的随机数，为最大粒子速度， 称之为动态调节数，其值为[0， 1]，其具体描述如下：

（5）

其中，为最大动态调节数，为最小动态调节数，表示当前的迭代次数，表示最大迭代次数。这一做法在保持粒子运动惯性的前提下，动态的调节粒子的运动轨迹，促使粒子在小范围内有更大的几率搜索到最佳位置，同时随着群体演化的进行，阻止了粒子搜索效率的降低，使得算法在演化过程中始终处于高效运行。

3.2 动态调节引导极值变化

为了提高算法的收敛速度，利用自然界中生物逃逸的行为规律，引入如下公式：

（6）

式（6）代表的意义为生物在逃逸过程中往往忘记自身的历史最好位置，而仅记住种群中的最好位置，实验结果表明，式（6）的引入显著提高了算法的收敛速度。

3.3算法流程

DDPSO基本步骤如下所示。

DDPSO算法流程：

输入：待优化问题

输出：群体的全局最优粒子和适应度

过程：

3.3.1初始化

3.3.1.1初始化种群数量，问题规模和最大迭代次数。

3.3.1.2确定动态调节数、，惯性权重和学习因子、。

3.3.1.3在问题的解空间中随机初始化初始种群。

3.3.1.4确定最大粒子速度及初始化粒子的速度。

3.3.2如果停止条件满足（足够好的位置或最大迭代次数），则退出，否则迭代执行以下步骤

3.3.2.1对全体粒子进行适应度评价。

3.3.2.2计算群体的全局最优粒子和适应度。

3.3.2.3计算每个粒子的历史最优粒子和适应度。

3.3.2.4根据公式（5）确定动态调节数。

3.3.2.5 循环：对每一个粒子执行以下步骤

3.3.2.5.1 根据公式（3），（4）对粒子位置及速度进行更新。

3.3.2.5.2 根据公式（6）对粒子个体极值进行更新。

3.3.2.5.3 判断粒子飞行速度与飞行区域，如果超过最大速度和搜索范围，调整粒子速度和搜索范围。

4.仿真实验

为了验证DDPSO算法性能，本文从两个方面对其性能进行测试：一是选用4个经典测试函数对算法进行测试；二是将其应用到移动机器人路径问题上。在DDPSO算法中，惯性权重采用线性递减调整策略，其取值范围为[0.95，0.4]，，最大动态调节数，最小动态调节数，在处理高维函数优化问题时的种群规模为20，迭代次数为2000次；对移动机器人路径寻优时的种群规模为4，迭代次数为20次。

4.1在高维函数优化问题上的应用

本节选取基本粒子群算法（PSO）及耗散粒子群算法（DPSO）[7]作为评估本文提出算法性能的参照。利用上述Rosenbrock、Griewank、Rastrigin、Quadric 4个标准测试函数测试其在维数为30维、100维和500维时算法寻优情况，具体情况如表1所示。

由表1可知，随着函数维数的增加，即加大问题复杂性的情况下，本文设计的算法其寻优结果是令人鼓舞的。具体表现为在对30维、100维及500维上述4个函数寻优时，DDPSO算法寻优效果明显优于上述两种PSO算法，并且随着维数的增加，其优势更加明显。为了能够更深入的观察本算法的性能，本文利用作为测试函数，测试其均值及方差随维数从1维变化到1000维时，函数均值及方差变化情况如图1、图2。

图1均值随维数变化情况 图2方差随维数变化情况

由图1、图2发现，虽然函数维数的增加加大了问题的复杂性，但本文设计的算法依然表现出很强的寻优效果。具体表现为当维数从1维变化到1000维时，DDPSO算法均值变化不到0.16，方差变化不到0.09，这充分说明了本文算法设计的稳定性。

4.2在移动机器人路径规划上的应用

在机器人相关技术研究中，路径规划技术是一个重要的研究领域。所谓机器人的最优路径规划问题，是指依据某个或某些评价准则（如危险系数最小、工作代价最小、行走路线最短、行走时间最短等），在其工作空间中找到一条从起始状态到目标状态的无碰撞运动序列。机器人路径规划问题可以建模为一个有约束的函数优化问题。设机器人在二维平面上的运动区域为A，其内有n个障碍物，且。机器人在A中运动序列为，其坐标为。则其适应度函数可表示为：

（7）

其中

， （8）

仿真试验放在12×12单位区域的环境中进行。机器人起点（start）设在（0，0），目标点（goal）设在（9，7.5）。为了方便对规划过程的处理，把障碍物边界向外拓展机器人长、宽最大尺寸的1/2，则机器人可看作质点，从而简化对问题的描述。以人工势场法为基础应用PSO算法及DDPSO-LFO算法对机器人路径进行寻优，重复运行30次得到的结果如表2所示。图3显示的是DDPSO算法得到的路径图。由表2可知，本文提出的DDPSO算法在对移动机器人路径规划寻优时，无论其最小路径还是路径的均值或者方差都小于基本PSO算法。

表2两种算法寻优结果

Algorithm Min Mean Max Deviation

PSO 14.3995 17.3611 21.3963 1.8243

DDPSO 13.9289 15.1091 17.3973 1.0334

图3 路径规划图

5.结论

本文针对粒子群算法对高维函数优化效果不佳问题，提出一种动态扩散粒子群算法（DDPSO）。该算法通过引入动态调节数，对粒子的速度更新方式重新进行定义，提高算法的运行速率，同时通过动态调节引导极值变化来增强群体对信息的利用能力，提高了算法的收敛速度。实验结果表明该算法在处理高维函数优化问题及移动机器人路径规划问题时性能优越。

参考文献：

[1]Kennedy J， Eberhart R C. Particle Swarm Optimization[C]//Proceedings of the IEEE International Conference on Neural Networks. Perth， USA： IEEE Press， 1995：1942- 1948.

[2]Hsieh S T， Sun T Y， Liu C C， etc. Efficient population ntilization strategy for particle swarm optimizer[J]. IEEE Transactions on Systems， Man， and Cybernetics，2009，39（2）：444-456.

[3]Bergh F， Engelbrecht A P. Cooperative learning in neural networks using particle swarm optimizers[J]. South African Computer Journal，2000，11（6）：84-90.

[4]赫然，王永吉，王青.一种改进的自适应逃逸微粒群算法及实验分析[J].软件学报，2005，16（12）：2037-2045.

[5]Shelokar P S， Siarry P， Jayaraman V K， et al. Particle Swarm and ant colony algorithms hybridized for improved continuous optimization [J]. Applied Mathematics and Computation， 2007， 188（1）：129-142.

[6]张勇， 巩敦卫， 张婉秋. 一种基于单纯形法的改进微粒群优化算法及其收敛性分析[J]. 自动化学报， 2009，35（3）：289-298.

[7]Xiao-Feng Xie， Wen-Jun Zhang， Zhi-Lian Yang. A Dissipative Particle Swarm Optimization[C]. The IEEE Congress on Evolutionary Computation，Hawaii，USA，2002： 1456 -1461.