ABSTRACT

Aiming at the shortcomings of traditional intelligent algorithms in robot path planning, based on the hybrid differential evolution algorithm and particle swarm optimization algorithm, the mutation rules of the two algorithms are modified, and multiple group mechanisms are added to maintain the diversity of the algorithm. Therefore, an improved DEPSO algorithm (pDEPSO) is proposed to solve the robot path planning problem. This new algorithm uses a variety of group techniques and dual mutation mechanisms to guide particles in exploring the unknown space in the optimization process. The algorithm improves the convergence speed without sacrificing diversity, which is worthy of study.

Keywords:Path Planning, Differential Evolution Algorithm, Particle Swarm Algorithm, Bimutation Mechanism, Multiple Population Mechanism

融合的差分进化和粒子群算法的 改进及应用

宋丽娜¹，何茂伟¹，陈瀚宁¹，赵建军²，孙丽玲¹

¹天津工业大学计算机科学与软件学院，天津

²矿冶过程自动控制技术国家重点实验室，北京

收稿日期：2018年10月1日；录用日期：2018年10月15日；发布日期：2018年10月23日

摘 要

针对传统的智能算法在机器人路径规划中的弊端，在混合的差分进化算法和粒子群算法的基础上，修改两种算法的变异规则，并加入多种群机制保持算法的多样性。因此，提出了改进的DEPSO算法(pDEPSO)，并以此来解决机器人路径规划问题。这种新算法采用的多种群技术和双变异机制，以指导粒子在优化过程中探索未知空间。该算法在不牺牲多样性的基础上，提高了收敛速度，从而值得研究。

关键词 :路径规划，差分进化算法，粒子群算法，双变异机制，多种群机制

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着二十一世纪电子、计算机、机械以及人工智能等多门科学技术的发展，研究者们在机器人领域也有了重大的突破，与原先的功能单一的机器人相比，现如今的机器人具有决策、自主感知和执行功能等。移动机器人的路径规划问题一直是移动机器人的一个重要组成部分，是当下研究的重点和热点。路径规划问题是指在特定约束条件下，可以找到一条从初始位置到目的地的最佳或者接近最佳性能的路径，是机器人可以无碰撞地，更快地到达目的地。

路径规划的核心是算法的选择和设计。常用的解决算法有人工势场法 [1] 、图形学算法 [2] 、PRM (Probabilistic Roadmaps概率路线图)算法 [3] 和RRT (Rapidly-exploring random tree)算法 [4] 等。

人工势场法是将机器人看作是人工受力场中的质点 [5] ，运动方向为人工受力场中合力的作用方向；目标点会对机器人产生吸引力，障碍物会对机器人产生排斥力，吸引力和排斥力的合力决定机器人的运动速度，以此得出机器人的移动位置；图形学算法，其是以图论为基础构建环境模型的一种方法。用具体的图来表示机器人运动的环境状态空间，然后在该图中查询最优路径；PRM是一种多查询的方法，基本思想是在给定图的自由空间里随机撒点(自定义个数)，构建一个路径网络图，从而查询到一条起点到终点的路径；RRT方法，是一种基于采样的单查询方法，以起始点和目标点为根，两个树相向生长，直到合并在一起，以找到一条从起始点到目标点之间的路径。

近年来随着智能仿生学算法 [6] 的发展，粒子群算法 [7] 、蚁群算法 [8] 、蜂群算法 [9] 等也应用于机器人路径规划中，梁晓丹 [10] 提出了自适应觅食策略，最终不但有效避开障碍而且找到目标地点；同时能有效地节约行走时间，从而减少能量的损耗、节约成本。陈刚 [11] 等人在遗传路径规划的基础上，提出了一种新的度量路径规划的个体适应度值的计算方法，在复杂环境下，该算法有很强的鲁棒性。

每种算法都有一定的局限性，传统的人工势场法和图形学算法容易陷入局部最优。PRM算法和RRE算法虽然计算速度较快，但路径搜索具有随机性，往往得不到最佳路径。智能算法需要多次迭代后才能形成规则。

本文针对智能算法收敛速度慢的缺点，拟融合差分进化算法和粒子群算法，并加以改进变异规则，在不牺牲多样性的情况下，提高全局搜索能力，增加算法的收敛速度，使移动机器人可以获得性能更佳的路径。

本文结构如下：第二节基本算法介绍，第三节改进的算法介绍，第四节为改进算法的基础函数测试，第五节为应用于路径规划的仿真实验介绍，第六节总结全文。

2. 基本算法介绍

2.1. 差分进化算法

差分进化算法是一种新兴的优化技术，是由Storn和Price于1995年提出 [12] ，是一类基于群体的自适应全局优化算法，英文简称为DE算法。DE算法能够有效地解决复杂优化问题，被广泛地应用关于工业设计、信号处理、人工神经网络及机器人等领域中。DE算法有变异、交叉、选择三个步骤：

变异：DE算法通过差分策略实现变异，在DE中常见的差分策略是从种群中随机选取两个个体，将其向量差进行缩放，再与待变异个体进行向量合成。变异完成后，得到一个中间个体v_i = (g + 1)，如式1所示：

$v_i\left(g+1\right)=x_{r1}\left(g\right)+F\left(x_{r2}\left(g\right)-x_{r3}\left(g\right)\right),i\ne r1\ne r2\ne r3$ (1)

其中，F为缩放因子，x_i(g)为第g代种群的第i个个体。变异过程中，需要判断合成向量的有效性，不可以超过边界范围。如果不满足边界条件，则将其删除，使用初始化的方法得到新的个体。

交叉：交叉的两个初始个体为，第G代种群中的个体x_ij和其变异的中间体v_i = (g + 1)，如式2所示：

$u_{ij}\left(g+1\right)=\{\begin{array}{l}{v}_{ij}\left(g+1\right),\text{if}rand\left(0,1\right)\le CR\text{or}j=j_{rand}\hfill \\ x_{ij}\left(g\right),\text{othersize}\hfill \end{array}$ (2)

其中，CR为交叉概率，j_rand为随机整数，v_ij则就表示第i个个体的第j维。为了确保中间体至少有一个基因遗传给下一代，第一个交叉基因从中间体随机选出，作为新个体的等位基因。后续的交叉过程，通过公式产生，通过随机数与交叉概率CR的比较，判断选取x还是中间体v，遗传给下一代。

选择：在DE算法中通常采用贪婪算法来选择个体，如式3所示：

$x_i\left(g+1\right)=\{\begin{array}{l}{u}_i\left(g+1\right),\text{if}f\left(u_i\left(g+1\right)\right)\le f\left(x_i\left(g\right)\right)\hfill \\ x_i\left(g\right),\text{othersize}\hfill \end{array}$ (3)

通过比较变异后的个体u_i(g + 1)与x_i(g)的适应度函数值，选择适应度优秀的个体遗传到下一代。

2.2. 粒子群算法

粒子群算法(Particle Swarm Optimization)，简称PSO，是由Kenned和Eberhart于1995年提出的 [7] 。比较特别地是，PSO算法没有交叉和变异算子，而是根据当前粒子群中的最优解来更新。

更新：粒子在N维空间的位置为矢量x_i，飞行速度表示为矢量v_i。PSO的目标函数将决定粒子的适应度值，同时记录每个粒子目前为止发现的最好位置pbest，pbest中的最佳值为gbest，gbest则为整个种群中粒子发现的最好位置。

最基本的PSO的更新规则如式4所示：

$\begin{array}{l}{v}_i=c_1\ast rand\left(\right)\ast \left(pbest-x_i\right)+c_2\ast rand\left(\right)\ast \left(gbest-x_i\right)\\ x_i=x_i+v_i\end{array}$ (4)

其中，v_i是粒子的当前速度，rand()表示0~1之间的随机数，x_i表示粒子的当前位置，c₁、c₂是学习因子，通常c₁、c₂为0~2之间的数。v_i的最大值为V_max，如果v_i > V_max，则v_i = V_max。v_i的第一项称为自身认识项，第二项称为群体认识项。其中，pbest反映粒子可以通过自身经验学习，gbest表明粒子间的协同合作。由此可以得出，PSO是通过经验学习来决定下一代的位置。

3. 改进的差分进化和粒子群算法的算法

基于前面提到的DE和PSO 算法，我们提出一种新的算法。它融合并改进DE算法和PSO算法，称为改进的DEPSO (pDEPSO)，旨在进一步加强这两种算法的全局搜索能力并加快收敛速度。

改进的算法主要包括两个阶段。第一阶段为PSO算法的更新，第二阶段为DE算法的更新。

3.1. 改进的PSO算法

本文采用自适应性权重PSO算法 [13] 。当粒子的目标趋于一致局部最优时，将惯性权重增大；而粒子的目标值比较分散时，将惯性的权重减少，同时对于目标函数优于平均目标值的函数，其对应的惯性权重因子较小，从而保存了改粒子，反之，低于平均适应度的粒子，其对应的惯性权重较大，使得该区域向较好的区域靠拢。

常用的PSO更新公式增加了改进，在当前粒子速度项中加入了惯性因子，更新后如式5所示：

$\begin{array}{l}{v}_i=c_1\ast rand\left(\right)\ast \left(pbest-x_i\right)+c_2\ast rand\left(\right)\ast \left(gbest-x_i\right)\\ x_i=x_i+{\omega }_i\ast v_i\end{array}$ (5)

相比较式4而言，新增加的动态ω能获得更好的寻优结果。动态的ω在PSO搜索过程中线性变化，采用线性递减权值策略，如式6所示：

${\omega }_i^{\left(t\right)}=\left({\omega }_{ini}-{\omega }_{end}\right)\left(G_k-g\right)/G_k+{\omega }_{end}$ (6)

其中，G_k代表最大迭代次数，ω_ini表示初始惯性权值，ω_end表示迭代至最大进化代数时的惯性权值。

3.2. 改进的DE算法

3.2.1. 基于K均值聚类的多种群策略

多种群技术被认为是一种很有前途的方式，可以促进子种群的开发，而不需要牺牲种群的多样性。聚类是根据数据的属性，把相似的数据进行分类在组合的过程。K均值聚类 [14] ，是一种经典的聚类方法，以欧式距离作为相似度评价指标，即两个粒子的距离越近，相似度也就越大。根据需要认为的确定K个点作为初始聚类中心，然后计算每个粒子都中心的距离，粒子将划分给距离它最近的中心点Ci。K均值算法伪代码如表1。

如果第i类包含n_i个个体，这些个体在这里设定为x₁，x₂，x_ni，这时聚类中心Cen(i)的计算公式为：

表1. K均值聚类的伪代码

$cen\left(i\right)=\frac{{\displaystyle \underset{i=1}{\overset{n_i}{\sum }}{x}_i}}{n_i}$ (7)

算法没隔T代进行重新聚类，为了增强算法的开发能力，前期T的值设定较小；在算法后期，需要算法有较强的探索能力，T的值设定较大。

$T=\{\begin{array}{l}floor\left(0.02\ast ite{r}_{\max }\right)\text{if}iter\le \text{0}\text{.5}\ast ite{r}_{\max }\\ floor\left(0.05\ast ite{r}_{\max }\right)\text{if}iter>\text{0}\text{.5}\ast ite{r}_{\max }\end{array}$ (8)

3.2.2. 变异：双变异规则

考虑到利用优秀的个体来交换信息的方式是一种很有前途的方法，我们提出来了一种新的变异机制。一方面旨在加强每个多种群之间的信息交流，另一方面加快收敛速度。变异机制如下：

$\begin{array}{l}{t}_{i,j}=\frac{F_{best}\cdot x_{1best,j}+F_{k1}\cdot x_{k,j}}{F_{lbest}+F_{k1}}\\ v_{i,j}=t_{i,j}+{\varphi }_{i,j}\left(t_{i,j}-x_{k2,j}\right)\end{array}$ (9)

$\begin{array}{l}{t}_{i,j}=\frac{F_{best}\cdot x_{gbest,j}+F_{k1}\cdot x_{k,j}}{F_{gbest}+F_{k1}}\\ v_{i,j}=t_{i,j}+{\varphi }_{i,j}\left(t_{i,j}-x_{k2,j}\right)\end{array}$ (10)

其中 $j\in \left\{1,2,\cdots ,NP\right\}$ ，NP为整个种群的大小φ_i,j是[−1，1]的随机数，k₁和k₂是[1，M]中的随机数，其中M为子种数大小且 $k_1\ne k_2\ne i$ ，lbest是当前子种群的最佳个体索引值，gbest是所有种群中最佳个体的索引值，T_i是中间向量，F_ki是第i个个体在当前个体在种群中从最差到最优的排序值。

从式9和式10中可以看出，两个变异机制的主要区别是：式9包含的是子种群中的最优个体，式10包含的是整个种群中的最优个体，这两种变异规则的主要差别就是中间向量。

一方面，通过这种方式将最优个体的信息加入到变异规则中，可以引导该区域其他粒子的搜索，加快收敛速度。另一方面，在邻近区域选择个体出入到中间向量中，可以保持种群的多样性，避免陷入局部最优，因此，这种变异机制比原始的DE算法和PSO算法更优。

本文将DE算法和PSO算法 [15] 结合在一块，使得算法更新种群时，从理论上讲，DE算法的性能通过结合PSO算法而得到改善，pDEPSO的算法性能可能比PSO算法和DE算法要更优秀。

总而言之，这种变异机制结合的DE算法和PSO算法的优点，改善了容易陷入局部最优的缺点，提高了收敛速度，是一种值得深入研究的方法。

3.3. 算法整体流程介绍

pDEPSO算法的运行该过程如下：

1) 初始化粒子；

2) 计算每个粒子的适应度值，使用公式(5) (6)更新粒子；

3) 重新评估每个粒子的适应度值；

4) 更新个体最佳pbest和全局最佳gbest；

5) 采用K均值聚类方法，分为N个子种群，参照表1、公式(7) (8)；

6) 使用公式(9) (10)对粒子进行变异，交叉、选择按照公式(2) (4)更新；

7) 重新更新pbest和gbest；

8) 重复进行(2)~(7)，直到达到迭代次数。

4. 算法性能测试

4.1. 函数测试

为了测试改进算法的性能，这里选取了五个测试函数，见表2。四个测试函数都选自基本测试函数，其中F1、F2为单峰函数函数，F3、F4为多峰函数。测试维度都选为30维。

4.2. 参数设置

为了公平比较，所有算法都使用相同的固定数量的函数评估作为停止条件；每个实验运行5000次目标函数评估，相当于使用群体大小为50的100次迭代；对于每个算法，运行十次求得平均值和方差。

为了测试函数性能，这里选择典型的DE算法、PSO算法与本文所提出的pDEPSO进行比较，DE算法的参数包括：F = 0.3，Cr = 0.8；PSO算法的参数包括：c₁ = c₂ = 1.5，ω_ini = 0.9，ω_end = 0.7；pDEPSO算法设置为：c₁ = c₂ = 1.5，ω_ini = 0.9，ω_end = 0.7，F = 0.3，Cr = 0.8，M = 3。

4.3. 分析与讨论

图1给出了DE算法、PSO算法和pDEPSO算法对于测试函数F₁-F₄的收敛曲线。其中a线代表pDEPSO算法，b线代表PSO算法，c线代表DE算法。

从图中可以明显看出，pDEPSO算法的收敛速度明显快于DE算法和PSO算法，收敛结果也优于DE算法和PSO算法。这主要是因为多种群策略的效果。而表3也给出了各算法对于函数测试的静态统计结果。统计结果为十次运算结果平均是。从结果可以看出，pDEPSO算法的搜索精度明显高于其它两个算法，且鲁棒性较好，这主要是因为双变异策略可以很好的控制种群多样性，而且同时很好的避免了种群陷入局部最优。

表2. 基准函数测试

表3. 各算法的测试效果

图1. 不同测试函数下的收敛图。(a) Sphere测试函数的收敛图；(b) Rosenbrock测试函数的收敛图；(c) Rastrigrin测试函数的收敛图；(d) Griewank测试函数的收敛图

5. pDEPSO算法在机器人路径规划中的应用

5.1. 仿真实验设置

本实验是在二维空间中进行，目标地点定为坐标[10, 10]处，采用Sphere函数作为目标函数：

$f_g\left(x,y\right)={\left(x-10\right)}^2+{\left(y-10\right)}^{2}x,y\in \left[0,10\right]$ (11)

障碍物越多则环境越复杂，本文采用3个障碍物(简单环境)，5个障碍物(复杂环境)、10个障碍物(困难环境)来测试算法。图2为障碍物图形。

5.2. 运行结果

pDEPSO算法的参数设定如下：NP = 80, c₁ = c₂ = 1.5，ω_ini = 0.9，ω_end = 0.7，F = 0.3，Cr = 0.8，M = 3，最大迭代次数为2000。对于不同障碍的环境，基于提出pDEPSO算法，优化的路径图和函数收敛曲线如图3，我们可以看出pDEPSO算法的区域搜索和自适应搜索机制可以使机器人避开障碍并且朝目标方向前进。同时，该算法能够使机器人更快地到达目的地，从而能有效的节省时间。

6. 结论

智能算法在路径规划中有广泛应用，经典的算法存在收敛速度慢、适应性差的特点。本文在DE算法和PSO算法的基础上，提出了一种新型的优化算法(pDEPSO)，该算法融合了DE算法和PSO算法的优点，并针对收敛速度慢提出了改进。同时，应用经典测试函数，验证了pDEPSO算法在收敛速度和鲁棒性两个测试标准上性能突出，具备优化能力。此外，应用pDEPSO算法求解了机器人路径规划问题。

图2. 障碍物示意图

图3. 模拟结果。(a₁) 简单环境–机器人避障路线；(b₁) 简单环境–收敛曲线图；(a₂) 复杂环境–机器人避障路线；(b₂) 复杂环境–收敛曲线图；(a₃) 困难环境–机器人避障路线；(b₃) 困难环境–收敛曲线图

在将Sphere函数作为机器人路径寻优环境的仿真研究中，该算法能够使机器人大范围搜索周围环境，最终不但能有效避开障碍而且找到目标地点；同时新算法能有效地节约行走时间，从而节约成本。

基金项目

国家自然基金–青年基金项目3D电子打印喷头状态优化模型与智能算法研究(61802280)；基于生命周期模型的多智能算法融合优化方法研究(2017KJ092)；国家自然基金-青年基金项目多智能算法生命周期融合优化模型与方法研究及在微波滤波器优化设计中的应用(61806143)；天津市自然金-青年基金项目 3D电子打印喷头智能优化模型与算法研究(17JCQNJC04500)；矿冶过程自动控制技术国家重点实验室开放基金资助(BGRIMM-KZSKL-2017-01)。

文章引用

宋丽娜,何茂伟,陈瀚宁,赵建军,孙丽玲. 融合的差分进化和粒子群算法的改进及应用
Improvement and Application of Fusion Differential Evolution and Particle Swarm Algorithm[J]. 计算机科学与应用, 2018, 08(10): 1518-1526. https://doi.org/10.12677/CSA.2018.810165

参考文献