应用改进差分进化算法的三维路径规划

张宗豪， 徐 斌， 胡 铮

(上海工程技术大学机械与汽车工程学院，上海 201000)

0 引言

路径规划是无人机进行任务规划的基本问题。无人机路径规划是在考虑无人机周围的地貌环境约束、自身性能约束、威胁物等条件下，为无人机规划出一条从起点到目标点的最优安全路径。无人机路径规划算法主要分为两类:一是传统方法，如人工势场法、A*算法、动态规划法等；二是智能优化算法，如蚁群算法、粒子群算法、遗传算法、差分进化算法等[1]。差分进化(Differential Evolution,DE)算法[2]是由STORN和PRICE提出的一种机制简单的群体智能优化算法，核心机制是通过变异、交叉操作并在贪婪选择策略下实现种群空间的迭代更新，逐步靠向最优解，具有高效寻优的特点。近年来，差分进化算法在路径规划方面得到了广泛的应用，众多学者对其进行了大量研究。文献[3]引入广义反向学习机制初始化种群，以适应度值从原种群和反向种群中综合选取较优个体，提高算法搜索精度和收敛速度，并且得到了更短的路径；文献[4]提出混入分布估计算法对种群以随机的概率进行更新，扩大搜索范围并且缩短路径长度、减小威胁代价；文献[5]提出的差分进化算法将种群分为两部分，并为不同种群提供不同的变异策略，进行多无人机路径规划，成功缩减了路径的长度；文献[6]提出一种基于自适应变异算子的约束差分进化算法处理无人机路径规划问题。本文从差分策略和参数控制两个方面对算法进行改进，并通过测试函数核验改进算法的性能，应用于三维路径规划验证改进算法的可行性。

1 改进差分进化算法

本文提出的改进算法MSCADE借鉴正弦余弦算法局部搜索的优势，在DE算法基础上融入种群重心概念，基于正弦余弦算法搜索机制对变异策略进行改进，并设计新的自适应缩放因子，以增强种群多样性、提高搜索能力；引入扰动策略到交叉策略，利用优秀个体信息引导搜索方向，提高收敛速度。

1.1 基于正弦余弦的变异策略

差分进化算法随着迭代进行逐步向最优解靠近。

在算法的前期应该增强算法的全局搜索性能；在后期提高局部开采能力，加快收敛速度。DE/rand/1算法因良好的空间搜索能力得到广泛应用，但后期局部开发能力不足。因此，本文基于改进正弦余弦算法[7]的搜索机制构建一种新的变异策略，并加入种群空间重心调节搜索方向。表达式为

(1)

(2)

其中:xcenter为每代种群空间的重心;P*为前一代最优个体；NP为种群数量。式(1)前半部分利用正弦函数的性质可实现平衡全局探索和局部开发的能力，后半部分利用种群重心可以加快算法收敛速度。

1.2 引入扰动策略的交叉策略

差分进化算法一旦发生早熟现象，变异操作的搜索能力就会削弱。此时，基于目标个体和对应变异个体的交叉操作，不能使算法有效地跳出局部最优解。扰动策略作为一种有效的跳出局部最优解的方式而得到广泛应用。本文在每一代种群中的目标个体和与之对应的加入基于t分布概率密度函数扰动的变异个体间，构建新的交叉策略，具体表述如下

(3)

式中:t分布概率密度函数tpdf(G,γ)中自变量G是当前迭代数，γ是自由度参数;pt是[0,1]间的随机数。参数γ可调整t分布概率密度函数曲线的曲率，γ越大曲线下降越快，γ越小曲线下降越平缓。这里γ取1，可保证曲线平缓下降，后期保持较大扰动值，有利于跳出局部最优解。

在改进的交叉策略中，加入扰动策略增强了个体多样性，防止陷入局部最优；并且还使用了前一代最优个体的信息，根据生物界优胜劣汰的原则，最优个体的信息对于种群进化必然是有利的，可以提高算法局部开采能力，加快算法的收敛速度。

1.3 自适应缩放因子

在变异策略中，缩放因子F的取值对算法至关重要。取值较大易得到最优解,但是算法收敛速度会下降，取值较小可以加快收敛速度,但算法易出现停滞现象。综合考虑这种情况，缩放因子F在开始前期应该保持较大值，后期改为较小值。因此，缩放因子F的变化规律符合Logistic函数模型，考虑以上所述，本文基于Logistic函数设计了一种自适应缩放因子，具体算式为

(4)

式中:t′=G/Gmax;u可以控制缩放因子F曲线的曲率。如图1所示，u取值越小，F的曲线下降越缓慢，越有利于增强个体的多样性，避免停滞；u取值越大，下降越快,有利于加快收敛速度。综合考虑，此处u取为1。

图1 F变化曲线

MSCADE算法流程如图2所示。

图2 MSCADE算法流程图

2 仿真测试

为了核验MSCADE算法的性能，选取了16个典型的测试函数进行实验。所选测试函数的参数描述如表1所示，具体公式见文献[8-9]。其中，f1～f7属于单峰函数，其他函数均为多峰函数。

表1 测试函数

选择了4种较先进的DE，jDE[10]，JADE[11]和SCA[7]算法与MSCADE算法进行比较。MSCADE算法中，Fmax=0.9，Fmin=0.1，NP=50；DE算法中，F=0.5，交叉算子均为CR=0.9。测试函数维度均为30。为了保证比较公正性，jDE,JADE和SCA算法的参数设置与对应文献一致。最大函数评估次数为50 000。每个测试函数独立重复运行30次，选取平均值、标准差作为最终评价标准，结果见表2。其中，加粗的数据为最优数据，部分数据经过保留3位有效数字得到。

表2 5种算法仿真数据比较

从表2中可以看出，MSCADE算法在f1,f2,f3和f4等11个测试函数(加粗表示)上得到的结果要优于其他算法，并且在f4,f6,f8和f164个测试函数上能得到理论最优解。jDE在f9,f10,f12和f134个函数上表现要优于其他算法；JADE在f15上优于其余算法。从单峰函数上看，MSCADE算法明显可以获得精度更高的解，说明该改进算法具有较好的全局探测能力和局部开发能力；从多峰函数上看，MSCADE算法在f8和f16函数上可以获得全局最优解，在其余大部分多峰函数上表现要优于或近似于DE算法，说明本文改进的算法能在一定程度上跳出局部最优解，增强搜索能力。由于在变异操作中加入的正弦余弦算法搜索机制会使用到最优个体的信息，并且该算法主要进行局部搜索，因此会导致改进算法向最优个体靠拢，而多峰函数存在多个局部最优个体，所以算法在单峰函数问题方面的求解性能要优于多峰函数。

为了更直观地体现MSCADE算法的收敛性能，选取单峰函数f1和f7，多峰函数f11,f13,f15和f16等6个测试函数的收敛曲线图进行对比。如图3所示，图中数据是30次独立运行的平均值，其参数设置同上保持一致。

图3 5种算法平均收敛曲线

由图3可见，MSCADE算法与其余4种算法相比，不论是单峰函数f1，f7，还是多峰函数f11，f16，都是收敛速度最快、搜索精度最高，说明MSCADE算法可以有效地跳出局部最优解。而在多峰函数f13和f15上，虽然搜索精度不是最高的，但在算法前期其收敛速度比其他算法明显更快。由上可得，本文提出的MSCADE算法在收敛速度和精度方面均有较大提高。

3 建立数学模型

3.1 地形环境模型

在本文中，用数学函数模型模拟地貌环境并用圆柱体模拟威胁物[12-13]。其中，地貌函数模型为

(5)

式中，m=10,b=0.2,c=0.1,d=0.6,e=1,f=0.1,g=0.1，都是常数，可以控制地貌特征。

自然山峰用指数函数来表示，具体数学表达式为

(6)

式中：hj为第j座山峰的位置高度；(xj,yj)为第j座山峰的中心位置；(xsj，ysj)为第j座山峰的山体坡度参数。

3.2 适应度函数

为了确保规划出的无人机路径是最优且安全的，本文以路径长度代价、威胁代价、飞行高度代价等作为评价指标来构造适应度函数。

3.2.1 路径长度代价

路径长度是路径规划的关键指标，路径长度越短，耗能耗时越少。飞行距离用从起点到终点，各相邻点间的欧氏距离之和表示，路径长度代价为

(7)

式中,(xi,yi,zi)是各点坐标。

3.2.2 威胁代价

(8)

(9)

式中:K表示威胁物个数；R(k)表示第k个威胁物的半径；C是威胁惩罚因子，取值107。

3.2.3 飞行高度代价

无人机路径规划过程中应尽量控制高度不发生较大变化[15]，平稳高度飞行有利于减少耗能，降低飞行成本，高度代价为

(10)

式中：n为路径上导航点数；havg表示各点高度的平均值。

因此，无人机路径规划适应度函数为

f=λ1·Jl+λ2·Jd+λ3·Jh

(11)

式中，λ1，λ2，λ3为权重系数，需满足λ1+λ2+λ3=1。

无人机路径规划的最佳状况为在确保飞行安全的前提下路径最短，故λ2的取值应大于λ1，也大于λ3。综合考虑，在此次实验中，权重系数λ1，λ2，λ3分别取值为0.3，0.5，0.2。

由于每次生成的点是离散的，所以生成的路径是折线形式，为了保证路线适合实际飞行，还需对路径进行平滑处理[16]。本文采用引入三次方样条数据插值的策略，以保证生成的路径是适合飞行的光滑路径。

3.3 实验仿真与分析

开始起点设置为(15，85，1.248 5)，目标终点为(150，40，1.467)；圆柱体威胁物的中心坐标分别设置为(10，60)，(128，60)，(100，40)，半径分别为8，10，15。以上参数单位均为km。DE和MSCADE算法种群均为50，维度为15，其余参数设置同前一致，终止最大迭代次数为200。

三维路径规划图见图4。

图4 三维路径规划图

路径规划俯视图见图5。

图5 路径规划俯视图

从图4和图5中可看到，MSCADE算法可以生成一条可行的安全路径，而DE算法规划出的路径更长，而且并不是每次都可以避开山峰和威胁区域;同时，可以看出MSCADE算法规划出的路径长度和平滑度都要优于DE算法。

图6是两种算法路径规划的适应度值收敛曲线。从图6中可以看出，DE算法规划出路径的适应度值为46.34，而MSCADE算法适应度值为42.35，具有更好的适应度值，收敛性也更好。

图6 适应度收敛曲线

综上所述，与DE算法相比，使用MSCADE算法规划出的路径不仅满足最短路径需求，而且还能有效地避开地形障碍物和威胁区域，从而验证了改进算法的有效性与实用性。

4 结束语

本文基于正弦余弦算法提出一种改进差分进化算法，用来解决无人机的三维路径规划问题。基本差分进化算法因为存在早熟现象问题，致使三维路径规划效果不佳。本文在基本差分进化算法的基础上融入正弦余弦算法搜索机制和扰动策略，可以防止陷入局部最优解，提升算法搜索和收敛性能。仿真结果表明，改进算法规划出的无人机路径更短且更安全。