一种改进的粒子群优化算法及其在无人机航路规划中的应用

李 鹏，李兵舰，亓 亮，陈凯翔，李 迪

(中国船舶重工集团公司第七二三研究所，江苏 扬州 225101)

0 引 言

航路规划是无人机实现自主飞行的基础，是典型的多目标大范围优化问题。梯度法收敛速度快，但对目标函数要求高，且容易陷入局部最优解；动态规划算法能够求得最优解，但维数越大，计算量越大；遗传算法稳定性强，但收敛速度不快，容易早熟；稀疏A*算法能够减少搜索空间，但求解时间随着规划空间的增大越来越长。本文结合遗传算法，对粒子群算法的种群进行交叉、变异等遗传操作，提高种群的多样性，避免种群陷入“早熟”，从而获得目标函数的最优解。为了验证遗传-粒子群优化(GA-PSO)算法的性能，通过4个基准测试函数对GA-PSO算法进行测试。结果表明，较常规的PSO算法，GA-PSO算法具有更快的收敛速度和收敛精度。针对无人机航路规划问题，采用GA-PSO算法进行仿真实验，得到了理想的无人机航路，验证了GA-PSO在航路规划中的有效性。

1 改进的粒子群算法

1.1 标准粒子群算法

粒子群优化算法的思路如下：群体中的各个粒子具备自我学习能力，也可以根据群体中其他粒子的经验知识进行学习，根据学习结果，动态地改变粒子的速度，整个群体通过各个粒子之间的信息交换，实现群体协作，进而优化群体行为[1]。标准粒子群算法中，粒子的更新过程如式(1)和(2)所示：

Vid(t+1)=wVid(t)+c1r1(Pid-Xid(t))+

c2r2(Pgd-Xid(t))

(1)

Xid(t+1)=Xid(t)+Vid(t+1)

(2)

式中：i=1，2，…，N，N为粒子规模；d=1，2，…，D，D为粒子的维数；t为当前迭代次数；r1、r2为0～1的随机数，能使粒子群呈现多样性；w为惯性权重，用来平衡群体的全局搜索与局部探测能力(取值越大，越利于全局搜索，取值越小，越利于局部搜索)。

线性减小的惯性权重w的数学公式为[2]：

(3)

式中：通常wmax取0.9；wmin=0.4；I为迭代次数的最大值；i为当前迭代次数。

c1、c2为学习因子，一般，c1=c2=1.496 2，c1、c2能够使粒子自动调整并接受群体中其它粒子的优点，然后根据自己搜索到的历史最优位置和整个群体中的最优位置进化。

从式(1)和式(2)可以看出，粒子的移动速度由三部分决定，自己原有的速度Vid、与自己的历史最优位置的距离(Pid-Xid)和与全体最优位置的距离(Pgd-Xid)，并分别由权重系数w、c1和c2来决定其相对重要性。

1.2 量子粒子群算法

量子粒子群算法(QPSO)按照式(4)～(7)进行粒子位置更新，则：

pi=(r1×pbest+r2×gbest)/(r1+r2)

(4)

L=(1/g)×abs(xid-pi)

(5)

(6)

式中：r1、r2和u都是0～1的随机数；g称为收缩系数；p没有明确定义，为势场位置参数[3]。

和标准粒子群算法一样，为了后期扩大搜索范围使目标函数值达到更优值，收缩系数g的值,按照线性递增的规则，从 0.6 逐渐递增至 0.8，其更新公式如下：

g=0.6+0.2×i/I

(7)

可以看出：量子粒子群(QPSO)算法只有粒子更新方式和PSO算法不同，QPSO算法没有速度参数，因而可以避免速度限制导致的全局搜索能力下降的问题。

1.3 改进的粒子群算法

量子粒子群算法具有参数少、原理简单、通用性强、容易实现等优点，由于没有速度的限制，比常规粒子群算法具有更强的全局搜索能力，但是仍存在着收敛速度慢、容易陷入局部最优的缺陷。通过增加粒子群数目，可以增强群体的全局搜索能力，但群体“早熟”的问题没有从根本上解决。

遗传算法基于对自然界优胜劣汰的进化机制进行模拟而提出，根据自然界的选择、交叉、变异等遗传现象，根据选定的适应度函数对个体进行筛选，淘汰适应能力差的个体，保留适应能力强的个体，并组成新群体。这样，经过多次循环，实现群体的进化[3]。遗传算法具有较强的全局搜索能力，但是局部搜索能力不足。

常规量子粒子群算法，在对粒子进行更新时，没有进行任何判断，因此会存在更新后粒子适应值变差的情况。

本文在量子粒子群算法的基础上，在粒子进行更新时，先对粒子适应值进行判断，如果能够使适应值更好，则更新，否则不更新，为保持粒子群一定的多样性，判断完成后，再以一定概率更新。

同时，针对常规量子粒子群算法容易“早熟”的问题，本文结合遗传算法，增强群体在搜索过程中得到全局最优解的能力。具体步骤为：首先，计算粒子的适应值，并排序，根据适应值大小的顺序对粒子进行两两配对；然后根据其适应值的大小，赋予一定的随机杂交概率，适应值越高，则进行杂交操作的概率越小，反之则越大，依据杂交概率对配对的2个粒子进行杂交；最后，按照一定的变异概率对杂交后的粒子进行初始化，同样按照适应值的不同决定变异概率。

可以看出，该方法能够增加粒子多样性，群体中优良粒子的特性得到充分利用，群体收敛速度加快，多样性得到提高，避免了过早收敛。

杂交过程中，孩子粒子的位置由父母粒子的位置的算数加权来计算，即：

X1(t′)=r·X1(t)+(1-r())·X2(t)

(8)

(9)

式中：X为位置；而X1(t)和X2(t)为用来进行杂交的粒子；r()为D维随机变量；各分量在0～1间均匀分布。

由于该方法结合了遗传算法，因此称为GA-PSO算法，运算步骤如下：

(1) 初始化粒子群。初始化粒子群，包括粒子群的大小、维数、粒子的位置、收缩系数等。

(2) 收缩系数g，依据式(4)～(7)更新粒子的位置(X1(k)，X2(k)，…，Xn(k))。

(3) 计算每个粒子的适应值，根据适应值大小进行排序，并两两配对。

(4) 根据适应值大小，赋予每个粒子一定的随机杂交概率，适应值越大，进行杂交的概率越大；反之，越小。

行为风格或人格能够影响创造力，创造力与行为风格或人格密切相关。早期的研究就发现了一些较为稳定的人格对创造力有很大影响，如内在动机、宽广的兴趣、审美敏感、容忍模糊、直觉、冒险、韧性与自信、不关注公众认可等。巴龙、爱杜森等人在研究科学家的创造力时发现，高度的自我力量、独立自主的强烈需要、较高的自信水平、陶醉于所热爱和倾注的事业等是创造者的共同个性特征。克顿(1989)发现那些具有“创新性”解决问题的人往往以“新颖的”方式解决看似普通的问题，甚至重新“界定问题表征”，然后再找寻答案。他说，这些创造性行为风格是较为稳定的，一旦形成，就会贯穿于解决绝大多数问题的过程之中。

(5) 对进行杂交操作后的粒子按照变异概率进行变异操作，变异概率同样根据适应值确定，适应值越大，则变异概率越大；反之，则越小。

(6) 计算每个粒子的历史最优值和全局最优值，并比较。如果粒子的当前适应度值好于历史值，则替换该粒子适应值和历史最优位置；如果粒子的历史最优适应值好于全局最优值，则替换全局最优适应值为该历史最优值，并记录对应的全局最优粒子的位置。

(7) 判断是否有粒子达到目标值。如果有，退出循环，求出最优解；否则跳转到(2)，重新进行迭代操作。

1.4 改进效果仿真

为了验证GA-PSO算法的有效性，采用4个常用的测试函数进行测试[4]，文献[4]论述了这4个函数验证粒子群算法的寻优性能及其代表性。这4个函数分别是：

(1) Sphere函数：

(10)

(2) Griewank函数：

(11)

(3) Rastrigin函数：

(12)

(4) Rosenbrock函数：

(13)

式中：函数f1为单峰函数，当所有未知量都取0时，达到最小；f2的最小值也在所有未知量取0时得到，且存在很多的局部极小点；f3存在一个全局最小值fmin=0，且具有大量局部极值点；f4为一个非凸函数，在(1,1,…,1)达到最小。

仿真实验中，粒子群规模取60，迭代次数取300，粒子维数取10，参数变化范围为[-10，10]，变异系数取0.6，收缩系数从0.6线性增加至0.8。对上述4个测试函数，分别使用QPSO和改进的粒子群算法(GAQPSO)计算其最小值，试验重复进行100次，结果取平均值。为了更好地表现2种算法的差异，目标函数适应值取以10为底的对数进行显示。得到目标函数适应值随迭代次数变化曲线如图1～图4所示。

图1 Sphere函数适应值随迭代次数变化曲线

图2 Griewank函数适应值随迭代次数变化曲线

图3 Rastrigin函数适应值随迭代次数变化曲线

图4 Rosenbrock函数适应值随迭代次数变化曲线

从以上结果可以看出，对于4种测试函数，GA-PSO算法收敛速度更快，能够得到比常规的粒子群算法更优的最优解，说明其具有更强的搜索能力，优化性能显著提高。

2 航路规划

无人机航路规划过程需要对飞行区域的基准地形、障碍区域和威胁区域进行分析研究，通过把地形、障碍和威胁等环境信息建立成带有属性特征和空间位置特征的数字地图，进行航迹路线建模，完成航路规划[5]。

2.1 环境建模

根据无人机航路规划的特点，其环境建模主要包括3个：基准地形建模、障碍区域建模以及威胁区域建模。

基准地形建模中，将飞行区域抽象为一个带有坐标信息的三维空间，空间中每个点的Z坐标可以设为M×r，即0～M之间的随机数。

采用山峰模型进行障碍区域建模，其近似公式如下：

(14)

式中：z(x，y)为每个点的高度；i代表第i座山；(xi，yi)为第i座山的地理中心坐标；hi为其高度；xsi为第i座山在x轴方向的坡度；ysi为第i座山在y轴方向的坡度(坡度值太小将导致山体坡度较大，不能起到障碍作用；太大会导致山体坡度较小，山体间会冲突)。

采用雷达近似模型进行威胁区域建模，雷达探测区域的水平距离和雷达高度之间的关系可以用下式描述：

H=KR2

(15)

式中：K为与雷达特性(如信噪比、发射功率等)有关的系数。

无人机进入到雷达探测范围后，被探测到的概率p=Rmax4/(Rmax4+R4)，该概率是关于R4的泊松分布。Rmax表示雷达的最大作用距离，由雷达的参数确定。

雷达的探测特性受环境影响较大，其建模将十分复杂。为了验证算法的有效性，本文简化雷达探测性能的建模，用半径为rs的半球体来近似表示雷达的探测范围。

根据障碍山峰模型，建立的航迹规划的环境模型如图5所示。

图5 航迹规划环境模型

2.2 航迹路线建模

2.2.1 航迹路线建模

通过建立航迹评价函数，能够衡量航线的优劣，本文选择航迹长度Lp、最小转弯角θmin和最低飞行高度hmin作为航迹评价函数的参数项，其他因素如风速、转弯半径等，为简化问题，本文进行了忽略。

航迹长度Lp表示无人机的飞行路程，显然，该值越小越好。假设第i个航路点(xi,yi,zi)与第i+1个航路点(xi+1,yi+1,zi+1)间的距离为li，则2个航路点的距离为：

(16)

(17)

最小转弯角θmin表示无人机最小拐弯角度，该值越小，路线越平稳。

最低飞行高度hmin表示无人机与地形间的最短距离，该值越小，无人机与地形碰撞的几率越大。

根据以上参考项，建立航迹评价函数如下：

(18)

式中：P为航路点总个数；Li为第i个航路点与第i-1个航路点间的距离。

总航迹长度L=L2+L3+…+LP，Ti为第i个航路点处的威胁值，包含最小转弯角度和最低飞行高度2个因素。φ1和φ2为0 ～ 1之间的权重系数，φ1越大，航迹长度值越大；φ2越大，威胁项加权后的值越大。仿真中，φ1取为0.75，φ2取为0.25。

2.2.2 最优航线求解

使用粒子群算法求解最优航线时，每个粒子Xi代表一条航线，Xi=(xid,yid,zid)，d=1,2,…,D，i=1,2,…,N，D表示粒子的维数，即每条航线包含的节点数，N表示粒子的个数。

为了使航线更加平滑，需要对所有的航路点进行拟合，每2个航路点内插Pin个点[6]。

拟合结束后，第d个航路点和第d+1个航路点之间的航路距离为这2个航路点及其之间所有内插点连线的长度，计算公式如下：

Ld=

(19)

得到航迹的长度值和威胁值后，就能计算最优航迹的评价值，根据该评价值判断航迹的优劣。

3 仿真试验与分析

假定无人机的飞行区域设置为300×300，出发点坐标为(11,271,11)，目的地坐标为(291,31,11)，7个山峰模型的参数分别为(151,250,120)、(230,60,50)、(50,150,100)、(100,100,90)、(50,50,60)、(150,180,70)、(160,50,80)，雷达模型的参数为(250,200,60)。

设定最大迭代次数I为150，粒子群数量N为50，粒子维数D为7，内插点个数Pin为8，变异系数取0.6，收缩系数从0.6线性增加至0.8。

为了测试GA-PSO算法进行无人机航路规划的性能，进行仿真实验，并和量子粒子群算法进行比较，每种算法运行50次，实验结果如图6所示。

图6 目标函数适应值随迭代次数变化情况

从图6可知，GA-PSO算法由于在粒子更新过程中引入了遗传算法的操作，收敛速度明显加快，且具有更好的寻优能力。

使用GA-PSO算法得到的最优航迹路线如图7、图8所示，为了使航迹更符合实际，对两两航迹点进行拟合，这样，航线更为平滑。

图7 航迹规划三维立体图

图8 航迹规划三维俯视图

4 结束语

本文结合遗传算法，对粒子群算法的种群进行交叉、变异等遗传操作。对粒子进行更新时，先进行判断，只有当粒子更新后具有更好的适应值时，才以一定的概率进行更新；否则，不更新，种群多样性得到提高，避免陷入“早熟”，从而得到目标函数的最优解。通过基准测试函数对GA-PSO算法进行测试，并与常规粒子群优化算法进行比较，结果表明，GA-PSO算法收敛速度更快、精度更高。针对无人机航路规划问题，采用GA-PSO算法进行仿真，结果表明，采用本文提出的GA-PSO算法，能够得到满足要求的最优航迹，而且，在种群维度较高的情况下，也能够保证较高的航迹精度。