改进灰狼算法的无人机路径规划_刘云平.pdf

书书书引用格式:刘云平，朱慧如，方卫华 改进灰狼算法的无人机路径规划J 电光与控制，2023，30(7):1-7 LIU Y P,ZHU H,FANG W H Pathplanning of UAV based on improved grey wolf optimizer algorithm J Electronics Optics Control,2023,30(7):1-7改进灰狼算法的无人机路径规划刘云平1，朱慧如1，方卫华2(1 南京信息工程大学，南京210000;2 水利部南京水利水文自动化研究所，南京210000)摘要:针对灰狼算法易陷入局部最优导致路径寻优精度低的问题，提出一种用于静态二维无人机路径规划研究的改进灰狼算法。首先，提出一种控制参数非线性调整策略，平衡算法的全局搜索与局部搜索;同时，将灰狼算法与Powell 算法结合，提高算法寻优效果及路径规划精度;最后，通过测试与仿真说明改进后的灰狼算法具有更好的寻优精度和路径规划效果。关键词:路径规划;灰狼算法;Powell 算法中图分类号:TP242 6文献标志码:Adoi:10 3969/j issn 1671 637X 2023 07 001Path Planning of UAV Based on ImprovedGrey Wolf Optimizer AlgorithmLIU Yunping1,ZHU Huiru1,FANG Weihua2(1 Nanjing University of Information Science Technology,Nanjing 210000,China;2 Nanjing Automation Institute of Water Conservancy and Hydrology,Ministry of Water esources,Nanjing 210000,China)Abstract:Aiming at the problem that the grey wolf algorithm is easy to fall into the local optimum,whichleads to the low precision of path optimization,an improved grey wolf algorithm is proposed and applied tothe static 2D UAV path planning research Firstly,a nonlinear adjustment strategy of control parameters isintroduced to balance the global search and local search of the algorithm At the same time,the grey wolfalgorithm is combined with Powell algorithm to improve the optimization effect and path planning accuracyFinally,the test and simulation show the optimization accuracy and path planning effect of the improved greywolf algorithmKey words:path planning;grey wolf optimizer algorithm;Powell algorithm0引言近年来，无人机因机动性强、灵活的优点，越来越多地被应用于军事、民用等各个领域，而路径规划是无人机顺利自主执行任务的前提。路径规划主要是指在满足无人机各种约束的条件下，找到一条从起始点到目标点、避开障碍物的路径1。在目前的研究中，常用的算法有人工势场法、启发式搜索算法、神经网络算法以及各种群智能算法，包括蚁群算法 2、粒子群算法3、蜂群算法4 等。蔺文轩等 5 设计了一种天牛粒子群混合算法，用于多约束、多目标的无人机集群任务分配，具有良好的稳定性及高精度，有一定的理论和实践意义;收稿日期:2022-05-28修回日期:2022-06-27基金项目:国家自然科学基金(51875293);江苏省水利科技项目(2021073)作者简介:刘云平(1979)，男，山东烟台人，博士，教授，博导。张玮等6 对演化算法加入先锋火花生成规则，增加了种群多样性，并将改进后算法得到的最短路径作为蚁群算法的初始信息素分布，为复杂环境下的路径规划及避障提供了新思路;刘洋等7 提出一种 Bezier 优化的遗传算法，利用 Bezier 曲线提高路径平滑性，并在遗传算法的适应度函数中增加自适应惩罚因子，保证路径规划的安全性;文献 8通过模拟植物生长机制，提出了一种仿生算法，用于未知环境下的无人机动态避障路径规划问题。这些算法都能在一定程度上提高路径规划的性能，但也都存在易陷入局部最优、参数多、收敛精度低等缺陷。灰狼算法作为新型群智能优化算法，相较于其他算法拥有结构简单、需要调节的参数少、容易实现的优点，同时拥有自适应调整的收敛因子和信息反馈机制，能在局部探索和全局搜索间取得平衡9，在故障诊断、优化调度、预测系统等领域已获得良好的应用效果10，第 30 卷第 7 期2023 年 7 月电光与控制Electronics Optics ControlVol 30No 7July 2023但在无人机路径规划领域的应用相对较少。文献 11在灰狼算法中引入差分进化算法的交叉、变异等操作，迫使灰狼优化(GWO)算法跳出停滞增强全局搜索能力，并用改进后的算法优化 SVM，将具有最优分类效果的 SVM 用于故障诊断;文献 12 通过改进狼群智能行为，引入个体编码与 POX 交叉操作，提高算法全局搜索能力，用于解决柔性作业车间多目标优化调度难题;文献 13 提出一种将极端学习机与灰狼优化算法结合的灰狼算法优化极限学习机(GWO-ELM)模型，以某基坑开挖工程为例，对地面沉降进行预测，并与其他模型对比说明优化后的 GWO-ELM 模型具有最强的预测效果;文献 14 为了解决复杂环境的路径规划问题，将简化的 GWO 算法和改进的共生生物搜索算法相结合，在保持搜索能力的同时能加快收敛速度，增强开发能力。为改善传统 GWO 算法的寻优性能，本文通过改变收敛因子，提出一种非线性自适应收敛因子策略，使搜索过程更符合寻优时逐渐收敛的规律，平衡算法全局搜索与局部搜索的能力，从而使系统逐渐向最优值收敛;引入 Powell 算法，利用 Powell 算法强大的局部搜索能力弥补 GWO 算法后期收敛精度不足的缺陷，并将改进后的灰狼算法应用于无人机路径规划的仿真。1改进的灰狼优化算法1 1灰狼算法原理灰狼算法是 MIJALILI 模仿灰狼的领导阶层和狩猎机制提出的一种新的启发式算法15。灰狼的社会等级是一个金字塔型，狼位于最高等级，负责决策等总体事务;狼位于第 2 级，协助 狼决策及指挥其他低等级狼;狼位于第 3 级，服从 狼、狼的命令，并负责侦察、放哨等事务;狼等级最低，负责平衡种群内部关系。在 GWO 算法中，每头灰狼代表种群中的一个候选解，那么根据灰狼的等级制度，为最优解，为次优解，为第三优解，其余解均称为。在灰狼狩猎的过程中，包围猎物的行为定义为D=CXP(t)X(t)(1)X(t+1)=XP(t)AD(2)式(1)是狼群个体与目标之间的距离算式，式(2)是灰狼的位置更新算式。其中:XP和X分别为目标与灰狼的位置向量;t 为迭代次数;A与C为系数向量，算式为A=2 ar1 a(3)C=2 r2(4)a=2 2ttmax(5)其中:参数a为收敛因子，随着迭代次数从 2 线性减少到 0;r1与r2为 0，1 之间的随机向量;tmax为最大迭代次数。在灰狼种群中，狼、狼、狼是最接近猎物、最能感知猎物信息的群体，其余的灰狼个体的位置都是根据这 3 种狼来确定的。在实际的路径规划中，是迄今为止获得的 3个最优解决方案，利用这三者的位置来判断下一个目标的位置，并强迫其余灰狼按最优灰狼的位置更新其位置，数学模型为D=C1X XD=C2X XD=C3X X(6)X1=X A1DX2=X A2DX3=X A3D(7)X(t+1)=X1+X2+X33。(8)式(6)定义了，与其他个体间的距离，X，X和X分别代表，的当前位置，X则是当前目标位置向量;式(7)定义了 向，移动的步长和距离;式(8)则为 的最终位置。1 2非线性收敛因子调整策略群智能算法在空间寻优的过程是全局搜索与局部寻优相结合的过程，全局搜索保证了种群的多样性，局部搜索则保证了收敛精度，而群智能算法都存在如何平衡二者的问题，在 GWO 算法中利用系数向量A来平衡全局搜索与局部搜索。在迭代过程中，收敛因子A从 2 线性下降到 0，而A的值就在 a，a之间变化，当 A1 时，灰狼种群离开当前的局部最优解，扩大全局搜索范围，以获得更优解;当 A1 时，灰狼种群局部精确搜索，攻击当前目标。然而，实际的搜索过程是非线性的，那么收敛因子a的线性变化就不符合实际的搜索过程，进而影响寻优效果，因此对a做出如下非线性调整策略，即a=ai+(af ai)1+k1tt()maxk21(9)式中:ai和af分别为参数a的初始值和终止值;k1，k2为调节系数。1 3改进的 PGWO 算法在灰狼算法中，尽管利用了参数A与C来平衡算法的搜索和开发能力，但仍存在后期收敛速度慢、收敛精度不足、易陷入局部最优的问题，因此利用 Powell 算法2第 30 卷电光与控制刘云平等:改进灰狼算法的无人机路径规划对其进行优化。Powell 算法是一种直接搜索法16，因其不计算函数导数的特点被认为是最有效的直接搜索法之一，具有计算简单、收敛速度快、精度高的特点，Powell 搜索法基本思想如下。1)选取初始数据。给定初始点 x(0)S 及 D 个线性无关的初始搜索方向 d(i)(i=0，1，D 1)，并给定允许误差。2)基本搜索过程。从 x(0)出发，沿着 d(0)，d(1)，d(D 1)进行一维搜索，得到 x(0)，x(1)，x(D)，令 k=0，即f(x(i)+id(i)=minSf(x(i)+d(i)(10)x(i+1)=x(i)+id(i)i=0，1，D(11)式中，i和 都为搜索步长，i为目标函数一维最优化问题的解。3)判断是否满足终止条件。令加速度方向 d(D)=x(D)x(0)。若 d(D)，则搜索停止，x(D)为问题最优解;否则，从 x(D)出发，沿着 d(D)进行精确的一维搜索，得到 x(D+1)。4)确定搜索方向。计算前一轮搜索中函数值下降最多的方向 i 及下降量 tl，即f(x(tl)f(x(tl+1)=max0iD(f(x(i)f(x(i+1)。(12)5)不调整搜索方向。若不等式f(x(0)2f(x(D)+f(2x(D)x(0)2(f(x(tl)f(x(tl+1)(13)成立，表明搜索方向仍然线性无关，那么下一轮搜索方向不变。令 x(0)=x(D+1)，k=k+1，返回 2)。6)调整搜索方向。若不等式(13)不成立，说明d(0)，d(1)，d(D 1)线性相关，需要调整搜索方向，令d(tl+i)=d(tl+i+1)，i=0，1，D tl1，产生一组新的线性无关的搜索方向。再令 x(0)=x(D+1)，k=k+1，返回2)。Powell 算法计算简单、精度高，不需要计算函数导数，局部搜索能力强，但对初始点的要求比较高17，算法是否能收敛到全局极小值很大程度上依赖于初始值的好坏，因此将 GWO 算法的全局搜索能力与 Powell 的局部寻优能力结合，同时提高了收敛速度与求解精度，最终改进后的 PGWO 算法步骤如下。1)参数初始化，包括 GWO 算法中狼群的初始位置X及数量 N，系数向量A和C及收敛因子a，Powell 算法搜索精度，混合算法最大迭代次数 tm