改进的混沌遗传算法求解无人机航迹规划问题

来源：核心期刊咨询网时间：12

摘要：摘 要： 针对无人机航迹规划问题展开研究，采用混沌遗传算法对无人机低空追击目标的航迹进行规划。该方法将无人机在低空复杂环境中的动力学模型离散化，结合约束条件，将三维空间划分为多个二维空间并利用栅格法进行二维建模，在二维空间下采用改进的混沌遗

　　摘 要： 针对无人机航迹规划问题展开研究，采用混沌遗传算法对无人机低空追击目标的航迹进行规划。该方法将无人机在低空复杂环境中的动力学模型离散化，结合约束条件，将三维空间划分为多个二维空间并利用栅格法进行二维建模，在二维空间下采用改进的混沌遗传算法来路径寻优，最终完成在三维空间中避开障碍物的航迹搜索过程。以建模工具Creator/Vega为仿真平台，建立仿真环境。仿真结果表明，该算法能够有效地规划出一条满足要求的航迹，且通过把三维空间转化为二维建模，避免了在三维空间求解的复杂性，提高了算法的工程实用性。

　　关键词： 三维航迹规划; 无人机; 混沌遗传算法; 混沌扰动; 扰动因子

　　0 引言

　　无人机航迹规划就是指综合考虑无人机机动性能、突防概率、碰地概率和飞行时间等约束因素下，寻找一条从起始点到目标点的最优或可行的飞行轨迹[1]。

　　由于遗传算法的鲁棒性，近年来有诸多学者，利用进化与遗传算法进行路径规划研究，取得了一定的成果。魏亭等人提出了基于稀疏A*遗传算法的无人机三维航迹规划方法[2]，稀疏A*算法是一种启发式搜索算法，它结合约束条件大大缩小了搜素空间，大大缩小搜素时间，但在三维空间中构造代价函数和启发函数，由于函数求解过程需要在立体空间中计算，大大增加了算法的难度。刘群芳，李军华在稀疏A*算法的基础上结合进化原理，引入了文化算法，基于稀疏A*算法与文化算法的混合算法实现了动态目标的无人机航迹规划，为有效解决复杂的多维非线性工程优化问题提供了一条分析方法，有很大的参考价值。本文利用混沌遗传算法(Chaotic Genetic Algorithm， CGA)并进行扰动因子的改进，综合考虑无人机的机动性能、地形高程障碍威胁以及飞行任务等多种因素，运用改进的CGA进行航迹规划。

　　首先利用Creator/Vega进行三维空间建模，然后参考文献[3]和文献[4]的方式，将三维空间搜寻转为二维空间求解，最后利用改进的CGA在二维空间展开航迹搜寻。经由对搜寻空间降维，下降算法难度，以获得提升搜寻效率的目标。

　　1 三维航迹转化为二维空间及在二维空间建模

　　CGA是在二维空间中的一种路径优先搜索算法，而低空无人机的航迹是三维的，因此必须把三维转化为二维空间搜索。在转化过程中，如何使用CGA从初始点到达目标点进行航迹搜索，如何进行节点扩展，如何选择候选节点就成为首要解决的问题。而正确的建立搜索空间，正是解决这些问题的先决条件。

　　在三维空间中，目标和障碍物位置已知情况下，無人机自初始位置选择最佳避障路径向目标位置行进的过程(如图1)。

　　假定S为无人机的出发点，E为终止点，障碍物为一个长方体图形A1B1C1D1-ABCD，当由S点直线飞行到E点时，会与障碍物发生碰撞。

　　探索路径的三维搜寻空间，并绕开障碍物的前提下，过程建立如下：

　　Step1 连出发点到终止点的线段SE，找到SE线段与长方体障碍物的第一个交点M，经由M做与长方体顶面平行的平面，且此平面与该长方体依次交于H、I、G、K四点，改变扩展因子把此平面向周围扩大搜寻空间为OPQR。扩展因子的选取值以无人机能够旋转的最大角度α为基准。

　　Step2 在二维水平空间确立搜寻区域(如图2)。

　　H、I、G、K四点组成的平面为障碍物在搜寻空间的投影平面，剩余的区域为可通过的区域。首先在搜寻平面上按栅格进行划分，按照栅格中心点的估计函数进行最优搜寻，找到向左或向右的飞行轨迹;然后将交点M向外扩展到点M1，在搜寻区域范围内寻找启发函数的最佳点M2;最后利用CGA可以找到由M1到M2的最佳搜寻路径。则二维搜寻路径最终由S到M1，再由M1到M2，M2到E。如图2所示。

　　Step3 在三维垂直空间确立搜寻区域(如图3)。

　　首先将OPQR平面以扩展因子的值不断向上扩展，当超出障碍物的顶部时，求得无人机向上飞行的轨迹搜寻区域;其次在该三维空间的顶面栅格中计算出离目的地E路径最短的栅格M2;然后应用CGA找出顶面中距离M1最短的栅格路径。则三维搜寻路径最终由S到M1，再由M1到M2，M2到E。

　　Step4 比较水平搜寻路径(如图2)和垂直向上搜寻路径(如图3)的路径值，最后确定最佳路径。

　　2 三维航迹规划及算法设计

　　2.1 无人机的约束条件与优化函数

　　无人机在飞行时有很多的约束限制，不同条件下约束各异。本文研究的无人机的主要约束条件包括：最小步长限制([Smin])，最大转向角度([θmax])，最大爬升/俯冲角，航迹距离约束，固定进入(接近)目标位置时的方向，飞行高度限制([Hmax])。综合以上约束条件，采用如下代价函数：

　　本文把从扩展节点到目标节点之间的直线距离作为启发函数[5]。即：

　　其中启发函数表示的其实是从当前节点到目标节点实际代价的下限，这样既满足可纳性，又满足一致性。

　　2.2 航迹规划的搜索步骤

　　Step1 粗略过滤障碍物。输入障碍物的坐标，判定此障碍物是不是在(Sx，Sy，Sz)到(Ex，Ey，Ez)所组成的长方体范围内。如果在，转到Step2;如果只有一部分在，则对区域边缘以n倍的Smin进行外扩，给n设定一个上限，这里设为3，转到Step2;如果不在，则对超出的范围的障碍物不予考虑，转到Step5。

　　Step2 在起始位置S到目标位置E的连线上，按照Step1设定的长方体范围判断，障碍物是否与SE直线相交。若相交，则计算线段SE与障碍物的交点，否则，转到Step5。

　　Step3 过交点上做与顶面平行和垂直的平面。对于平行平面，利用第3部分改进的CGA进行二维路径规划，找出最优路径轨迹(如图2)。对于垂直平面，使用扩展因子在平面中进行三维扩展(如图3)，扩展后的平面同样采用CGA进行路径寻优，然后选择距离最短的那条路径段作为最终的轨迹。

　　Step4 将交点1、交点2…，所有轨迹线交点的坐标添加到Vega路径中，实现避障路径规划;

　　Step5 把S点移到当前位置，E点不变。按照SE方向继续向前搜索，若到达目标位置，则退出。若碰到障碍物，则转到Step2。

　　3 CGA二维路径规划及算法设计

　　在二维空间采用栅格法建模后，采用实数编码，运用CGA来优化路径。CGA是混沌算法(Chaos Algorithm，CA)和遗传算法(Genetic Algorithm，GA)的集成，是在求解复杂优化问题使用的最广泛的遗传算法的基础上，引入混沌扰动来解决单一遗传的早熟和局部收敛的算法。

　　CGA设计思想是首先按照遗传算法的基本步骤，即初始种群生成、选择、交叉和变异生成路径;然后引入混沌扰动。因篇幅所限，本文直接把遗传算法变异后的解集代入混沌优化式中，对遗传算法求解的详细计算过程不做描述。

　　3.1 随机扰动的确定

　　δ*为当前最优解(x1*，…，xr*)映射到[0，1]区间后形成的向量，称为最优混沌向量;δk为迭代k次后的混沌向量，δ′k为加了随机扰动后(x1，…，xr)对应的混沌向量[6]。其中0<α<1，采用自适应选取，这是因为搜索初期希望(x1，…，xr)变动较大，需要较大的α。随着搜索的进行，(x1，…，xr)逐渐接近最优点，故需要选用较小的α，以便在(x1*，…，xr*)所在的小范围内搜索[7]。本文应用式⑷确定α。

　　其中m为一整数，依优化目标函数而定;k为迭代次数。

　　3.2 CGA设计步骤

　　在3.1节确定扰动方案后，按CGA算法搜索待优化参数xi的步骤如下。

　　Step1 给变量设定取值范围[ai，bi]、群体大小m、混沌算子中的吸引子μi及父代间的互换率Pc1，Pc2和子代的变异率Pm[8]。

　　Step2 选用式⑸所示的Logistic映射，关系式如下：

　　其中i表示混沌变量的序号，i=1，…，r;u表示种群序号，u=0，1，…，m;βi表示混沌变量，0≤βi≤1;μi表示吸引子。

　　取u=0，μi=4[9]。先给式⑸赋r个微小差异的初值，得到r个混沌变量βi(1)，(i=1，…，r)。依次取u=1，2，…，m，可得到m个初始解群[10]。

　　Step3 用载波法[11]，将选定r个混沌变量βi(u+1)分别引入到式⑹的r个优化变量中，使其变换为混沌变量[x'i]，混沌变量的取值范围，会相应切换到相应的优化变量的取值范围[12]。

　　Step4 把式⑵作為适应度函数的判断准则，计算式⑻生成的适应度值，把适应度值按照降序排列，因为f(X′)小于0时不能作为适应度，而且即便f(X′)非负，但若f(X′)对某一代群体相对变化范围过小，相当于两代值过于靠近或类同，会造成算法收敛速率很慢，因此还需要对f(X′)按下式作微小变化：

　　其中f′k(X′)为微小变化后的适应度值，fk(X′)为微小变化前的适应度值，f(X′)min为微小变化前的最小适应度值，f(X′)max为微小变化前的最大适应度值，m为群体大小，按式⑼调整后，适应度值均大于0，且适应度值的相对变化范围加大，便于加大收敛速度。

　　推荐阅读：无人机遥感在水土保持领域的应用分析

转载请注明来自：http://www.qikan2017.com/lunwen/nye/17962.html