基于适应度值优劣粒子群算法的无人机路径规划

王小璐，黄辰，于远航，陈福豪，胡蝶，陆琪，崔曦予

（沈阳航空航天大学民用航空学院，辽宁沈阳，110136）

0 引言

近年来，随着传感器技术和智能控制技术的发展，无人机已被广泛应用于军事和民用领域，如侦察[1]、监视[2]、目标检控[3]、无线通信[4]、油田检测[5]等。与载人飞机相比，无人机因为体积小、成本低、对使用环境要求低和具有较强的生存能力等优点而得到了广泛的应用，并正在逐渐取代传统的载人飞行器，无人机(Unmanned Aerial Vehicle, UAV)的研究对一个国家的经济与民生起着重要的作用。路径规划作为[6]无人机系统自主导航的基础技术，是保证飞行任务顺利完成的重要组成部分，因而受到越来越多的关注。无人机路径规划的主要目标是在规定的约束条件下，在任务空间中寻找从起始位置到目的位置的最优或接近最优的飞行路径。近年来，常用于解决路径规划问题的主要方法有启发式算法（例如，A*算法[7]、D*算法[8]）、进化算法（例如，蚁群算法[9]、粒子群算法[10]、人工蜂群算法[11]、遗传算法[12]）、人工势场法[13]等。

与传统方法相比，进化计算算法在路径上获得高质量解的能力很强。航迹规划问题通常被认为是一个非线性NPhard优化问题，通过进化算法进行求解。众所周知，进化算法已经取得了很大的进展，并得到了深入而广泛的研究。进化算法的灵感来自“自然生物进化”，通过将自然界各种事物的演化规律与解题过程相结合，从而得到实际问题的高精度近似解，并在生产实践中得到了广泛应用。进化算法已被成功应用于寻找全局或近似全局最优路径。Yang等[14]发现了在历史搜索中的高质量路径点难以得到进一步利用的缺点，提出了一种将路径点分别评估和演化的方法用于二维无人机路径规划。Huang等[15]提出了一种基于全局最优解竞争的改进PSO算法，并将路径规划器应用于三维无人机。Zhang[16]提出了一种改进的基于相位角编码并结合突变适应机制的果蝇优化算法，以解决无人机(UAV)路径规划问题。

粒子群优化算法(Particle Swarm Optimization, PSO)[17]基于一个简单的机制，通过模仿鸟类等群居动物的群体觅食行为。粒子群中包含有一群粒子，每个粒子表示优化问题的一个候选解，并且每个粒子都有一个在D维搜索空间中飞行的位置和速度。为了找到全局最优值，每个个体根据某些特定的适应值进行自我评估，在搜索过程中记住自己搜索到的最佳位置pbest以及全体的最佳位置gbest。利用这两个极值来调整飞行，最终找到食物的位置。与其他受生物种群行为特征启发的算法一样，优化问题从随机初始解开始，通过计算适应度值来评估解的质量，通过迭代进化的方式逐步找到最优解，反复迭代多次。

1 无人机路径规划问题描述

在搜索空间中，定义起始点为PS(x S,yT)，目标点为PT(xT,yT)，如图1所示。图1 描述无人机的飞行环境。飞行任务是根据目标函数下，在S和T之间生成最优路径。一条优化路径可以用一个集合C= {PS,P1,P2···,PD,PT}其中路径点PD= (x d,yd)来表示。然后通过连接各个路径点得到一条无人机的飞行路线。威胁的区域采用圆形来定义，如图1所示。

图1 环境描述

在进行路径规划之前，首先需要对运动空间进行离散化，使其成为对路径规划有意义的表示。这种表示与搜索算法密切相关，规划算法只有在与环境表示相配合的情况下才会有好的表现。令(x,y)表示任务空间中任意一点的坐标，任务空间可以被表示为：

其中，xmin，xmax，ymin，ymax分别定义为,x y的边界值。

当无人机执行飞行任务时，可能会面临敌方导弹攻击、雷达探测等高风险威胁。因为雷达和导弹的防御范围是全方位的，因此用圆来描述威胁源的数学模型。第i个雷达或导弹的数学模型可以被写成：

其中，(xk,yk)为第k个威胁源的中心坐标，rk是第k个威胁源的半径。

2 建立目标函数

无人机航迹的目标函数主要包括障碍危险成本和长度成本，所以目标函数是障碍威胁和长度的加权总和，可表示为：

其中，J1为长度成本，J2为障碍危险成本，w1、w2分别为障碍危险成本和长度成本的权重。

长度成本可通过下式来计算：

其中，i=D+1时，Pi表示目标点。i-1=0时代表起点。

规划路径的安全代价可计算为：

其中，Oj为第j个障碍物的圆心，rj为第j个障碍物的圆心。

3 改进粒子群算法

3.1 粒子群算法

粒子群优化算法通过将求解的问题看作是空间中的粒子，算法通过模仿昆虫，鸟类的觅食行为来解决各种工程最优化问题。鸟群中个体的飞行过程类比为单个粒子的运动过程，将其群体觅食行为的过程类比为寻找最优解的迭代过程。在该过程中基本无需外部信息，只通过群体内部的交流。在粒子群算法中，假设每个粒子都能记住历史上的最佳位置，也就是整个种群所发现的最佳位置，被称为全局最优解，以及每个粒子目前所发现的最佳位置，即个体最佳位置。每个粒子向个人最佳位置和全局最佳位置学习。该算法操作简单、实现容易、精度高、且具有优秀的收敛性。

设在D维空间搜索域中，群体中有N个粒子，N为种群规模，种群规模不宜过小，以保证种群多样性，提高算法性能；且不宜过大，致使收敛速度过于缓慢。

每个粒子i的位置表示为搜索域中的一个向量Xi=(xi1,xi2,···,xiD)，速度为Vi= (vi1,vi2,···,viD),i= 1,2,···,N。粒子个体的最优位置和粒子群体整体最优位置分别用pbest和gbest来表示，第k次迭代中粒子的位置及速度按照以下方程进行更新：

其中，ω为惯性权重，c1为个体加速系数，c2为群体加速系数，r1，r2为[0,1]上均匀分布的随机数。

个体加速系数c1表示粒子下一步运动受自己经验驱使所占的权重。即将粒子推向个体最优位置pbest的加速权重；群体加速系数c2表示粒子下一步运动受其它粒子经验影响所占的权重。即将粒子推向群体最优位置gbest的加速权重。c1的值过小会造成群体多样性降低，导致搜索局限。c2过小自会导致自我认知型粒子群算法，即社会共享信息少，致使收敛速度缓慢。

3.2 改进粒子群算法

惯性权重ω指粒子保持原有运动状态的能力，使其有能力在搜索域中对新控件进行探索。进而使得PSO在全局搜索和局部开发之间取得平衡。ω作为粒子群优化算法的关键参数之一，它的取值很大程度上决定了算法性能：在算法前期，ω值大有利于粒子搜索更大的范围，在算法后期，ω值较小则可以加快收敛速度。

当惯性权值ω较小时，算法的局部搜索能力较好。ω较大时，算法的全局搜索能力得到了提高，在接近最优位置时瞬间又飞越了最优位置，这样算法就很难收敛。一般选取惯性权重ω的值在[0.4, 0.9]范围内，惯性权重ω的值很严重影响算法的优化性能。根据种群中各粒子的适应度值，种群中的粒子将划分为“开发型”与“探索型”两种。“开发型”粒子主要任务是对已找到的优质解进行优化，而“探索型”粒子用于找到优质解的区域。针对不同的搜索类型，建立了分段非线性惯性权重函数, “开发型”惯性权重采用随机方法获得，粒子群算法中的惯性权值ω采用随机机制，随机机制有利于保持学习多样性和种群多样性可以避免过早收敛性和落入局部最优。而 “探索型”惯性权重收敛速度最慢，因此，通过分组的方式来调整惯性权重的大小可以有效提高算法的搜索效率。改进后的惯性权重ω描述为：

4 仿真实验与分析

为了研究算法对无人机路径规划的可行性和有效性，在MATLAB2016a仿真环境下进行实验，并与PSO算法进行了进一步的实验比较。环境1中设置起始点的坐标(0, 0)，目标点的坐标为(400, 600)。环境1中设置3个障碍物，其中心坐标分别为(150, 450)、(400, 300)和(120, 150)。 环境2中设置起点坐标为(200, 100)，目标点的坐标为(800, 800)。环境2中设置6个障碍物，其坐标为(300, 200)、(500, 400)、(600, 200)、(300, 500)、(700, 550)和(600, 750)。粒子个数N=100，最大迭代次数Tmax=100。

每个算法独立运行25次，采用两种算法进行路径规划，两种算法的适应度值的结果如表1所示。PSO和改进的PSO算法得到的规划路径在两种环境中的规划路径曲线分别如图2和4所示，适应度值变化曲线如图3和5所示。

表1 两种算法的适应度值结果

图2 环境1的规划路径

图3 环境1中适应度值变化曲线

比较表1中的两种算法的适应度值可以看出，在环境1和2中，FPSO算法的最优适应度值小于原PSO算法，FPSO算法的平均适应度值比PSO算法要小，平均适应度值表示算法在多次运行时的稳定性。对比实验结果在PSO和FPSO之间，可以得出PSO的参数更新策略具有更强大的寻优能力。这两种环境下的实验结果证明了FPSO算法的优越性，可以用于求解无人机航路规划问题。

图4 环境2的规划路径

图5 环境2中适应度值变化曲线

5 结论

在PSO算法用于处理无人机的路径规划问题中，由于传统PSO算法存在易陷入局部最优的缺陷，本文从整个种群粒子的适应度值出发，将种群划分为探索和开发两个子部分，在两个子部分中分别采用不同的惯性权重ω选择策略，以此来提高了算法的多样性和搜索寻优能力。通过对传统PSO算法和改进后的PSO算法进行路径规划仿真并对结果进行对比分析。与传统PSO算法相比，FPSO可以得到一条更平滑和路线较短的无人机飞行路线。