文档介绍：该【改进的混沌遗传算法求解无人机航迹规划问题 】是由【小舍儿】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【改进的混沌遗传算法求解无人机航迹规划问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。·26·
DOI:.cn33-1094/
改进的混沌遗传算法求解无人机航迹规划问题
郑涛
(广东科学技术职业学院,广东珠海519090)
摘要:针对无人机航迹规划问题展开研究,采用混沌遗传算法对无人机低空追击目标的航迹进行规划。该方法将无
人机在低空复杂环境中的动力学模型离散化,结合约束条件,将三维空间划分为多个二维空间并利用栅格法进行二维建
模,在二维空间下采用改进的混沌遗传算法来路径寻优,最终完成在三维空间中避开障碍物的航迹搜索过程。以建模工
具Creator/Vega为仿真平台,建立仿真环境。仿真结果表明,该算法能够有效地规划出一条满足要求的航迹,且通过把三
维空间转化为二维建模,避免了在三维空间求解的复杂性,提高了算法的工程实用性。
关键词:三维航迹规划;无人机;混沌遗传算法;混沌扰动;扰动因子
中图分类号::A文章编号:1006-8228(2020)11-26-05
Chaoticgeneticalgorithmforaircraftrouteplanningproblemresolution
ZhengTao
(GuangdongPolytechnicofScienceandTechnology,Zhuhai,Guangdong519090,China)
Abstract:Thepaperdiscussesrouteplanningissuesofunmannedaerialvehiclebychaoticgeneticalgorithms,emphaseson
-altitude
aircraftincomplexenvironments,andaccordingtoalltheconstraints,the3Dspaceisdividedintoseveral2Dspaces,andthegrid
methodisusedfor2Dmodeling,andtheimprovedchaoticgeneticalgorithmisusedtooptimizethepathinthe2Dspace,thus
successfully,andavidsolvingthecomplexityofrouteplanningprobleminthe3Dspacebytransforming3Dto2D,which
improvestheengineeringpracticability.
Keywords:three-dimensionalrouteplanning;unmannedaerialvehicle;chaoticgeneticalgorithm;chaoticperturbation;perturbation
factor
0引言大增加了算法的难度。刘群芳,李军华在稀疏A*算法
的基础上结合进化原理,引入了文化算法,基于稀疏
无人机航迹规划就是指综合考虑无人机机动性能、
A*算法与文化算法的混合算法实现了动态目标的无
突防概率、碰地概率和飞行时间等约束因素下,寻找
人机航迹规划,为有效解决复杂的多维非线性工程优
一条从起始点到目标点的最优或可行的飞行轨迹[1]。
化问题提供了一条分析方法,有很大的参考价值。本
由于遗传算法的鲁棒性,近年来有诸多学者,利
文利用混沌遗传算法(ChaoticGeneticAlgorithm,
用进化与遗传算法进行路径规划研究,取得了一定的
CGA)并进行扰动因子的改进,综合考虑无人机的机动
成果。魏亭等人提出了基于稀疏A*遗传算法的无人
性能、地形高程障碍威胁以及飞行任务等多种因素,
机三维航迹规划方法[2],稀疏A*算法是一种启发式搜
运用改进的CGA进行航迹规划。
索算法,它结合约束条件大大缩小了搜素空间,大大
首先利用Creator/Vega进行三维空间建模,然后参
缩小搜素时间,但在三维空间中构造代价函数和启发
考文献[3]和文献[4]的方式,将三维空间搜寻转为二维
函数,由于函数求解过程需要在立体空间中计算,大
收稿日期:2020-6-30
作者简介:郑涛(1979-),女,河南新乡人,硕士研究生,系统架构设计师/高级工程师,主要研究方向:混沌遗传算法的改进及其无人机上的应用。
万方数据
计算机时代2020年第11期·27·
空间求解,最后利用改进的CGA在二维空间展开航迹数进行最优搜寻,找到向左或向右的飞行轨迹;然后
搜寻。经由对搜寻空间降维,下降算法难度,以获得将交点M向外扩展到点M1,在搜寻区域范围内寻找
提升搜寻效率的目标。启发函数的最佳点M2;最后利用CGA可以找到由M1
到M2的最佳搜寻路径。则二维搜寻路径最终由S到
1三维航迹转化为二维空间及在二维空间建模
M1,再由M1到M2,M2到E。如图2所示。
CGA是在二维空间中的一种路径优先搜索算法,
而低空无人机的航迹是三维的,因此必须把三维转化
为二维空间搜索。在转化过程中,如何使用CGA从初
始点到达目标点进行航迹搜索,如何进行节点扩展,
如何选择候选节点就成为首要解决的问题。而正确
的建立搜索空间,正是解决这些问题的先决条件。
在三维空间中,目标和障碍物位置已知情况下,
无人机自初始位置选择最佳避障路径向目标位置行
进的过程(如图1)。图2水平扩展搜索区域
Step3在三维垂直空间确立搜寻区域(如图3)。
首先将OPQR平面以扩展因子的值不断向上扩
展,当超出障碍物的顶部时,求得无人机向上飞行的
轨迹搜寻区域;其次在该三维空间的顶面栅格中计算
出离目的地E路径最短的栅格M2;然后应用CGA找
出顶面中距离M1最短的栅格路径。则三维搜寻路径
最终由S到M1,再由M1到M2,M2到E。
图1确定搜索平面OPQR图
假定S为无人机的出发点,E为终止点,障碍物为
一个长方体图形ABCD-ABCD,当由S点直线飞行
1111
到E点时,会与障碍物发生碰撞。
探索路径的三维搜寻空间,并绕开障碍物的前提
下,过程建立如下:
Step1连出发点到终止点的线段SE,找到SE线
图3向上扩展搜索区域
段与长方体障碍物的第一个交点M,经由M做与长方
体顶面平行的平面,且此平面与该长方体依次交于H、Step4比较水平搜寻路径(如图2)和垂直向上搜
I、G、K四点,改变扩展因子把此平面向周围扩大搜寻寻路径(如图3)的路径值,最后确定最佳路径。
空间为OPQR。扩展因子的选取值以无人机能够旋转
α2三维航迹规划及算法设计
的最大角度为基准。
Step2在二维水平空间确立搜寻区域(如图2)。
H、I、G、K四点组成的平面为障碍物在搜寻空间无人机在飞行时有很多的约束限制,不同条件下
的投影平面,剩余的区域为可通过的区域。首先在搜约束各异。本文研究的无人机的主要约束条件包括:
最小步长限制(S),最大转向角度(θ),最大爬升/俯
寻平面上按栅格进行划分,按照栅格中心点的估计函minmax
万方数据
·28·
冲角,航迹距离约束,固定进入(接近)目标位置时的方Algorithm,CA)和遗传算法(GeneticAlgorithm,GA)的
向,飞行高度限制(H)。综合以上约束条件,采用如集成,是在求解复杂优化问题使用的最广泛的遗传算
max
下代价函数:法的基础上,引入混沌扰动来解决单一遗传的早熟和
=∑n(+)⑴
g(n)lh局部收敛的算法。
ii
=1
iCGA设计思想是首先按照遗传算法的基本步骤,
=(-)2+(-)2+(-)2
其中lxx-1yy-1zz-1,l表
iiiiiiii即初始种群生成、选择、交叉和变异生成路径;然后引
示第i段路径的长度;h表示第i个节点的偏转代价。入混沌扰动。因篇幅所限,本文直接把遗传算法变异
i=2
当为水平面的偏转时,hS;当为垂直面上的后的解集代入混沌优化式中,对遗传算法求解的详细
imin23
=计算过程不做描述。
偏转时,即进行爬升和俯冲时,h3S,其中S
iminmin
表示无人机的最小步长。
=+(1-)*⑶
本文把从扩展节点到目标节点之间的直线距离令δ'αδαδ
δkk
作为启发函数[5]。即:*为当前最优解(x*,…,x*)映射到[0,1]区间后形
=(-)+(-)+(-)⑵1rδ
f(n)xx2yy2zz2成的向量,称为最优混沌向量;为迭代k次后的混沌
ngoalngoalngoalδk
向量,′为加了随机扰动后(x,…,x)对应的混沌向
其中启发函数表示的其实是从当前节点到目标节点kα1r
量[6]。其中0<<1,采用自适应选取,这是因为搜索初
实际代价的下限,这样既满足可纳性,又满足一致性。α
期希望(x,…,x)变动较大,需要较大的。随着搜索的
进行,(x,…,x)逐渐接近最优点,故需要选用较小的,
Step1粗略过滤障碍物。输入障碍物的坐标,判1r
以便在(x*,…,x*)所在的小范围内搜索[7]。本文应用
定此障碍物是不是在(S,S,S)到(E,E,E)所组成的长⑷1αr
xyzxyz式确定。
方体范围内。如果在,转到Step2;如果只有一部分在,-1
=1-ékùm⑷
则对区域边缘以n倍的Smin进行外扩,给n设定一个αêú
ëkû
上限,这里设为3,转到Step2;如果不在,则对超出的
其中m为一整数,依优化目标函数而定;k为迭代次数。
范围的障碍物不予考虑,转到Step5。
Step2在起始位置S到目标位置E的连线上,按照
Step1设定的长方体范围判断,,按CGA算法搜索待优
化参数x的步骤如下。
相交。若相交,则计算线段SE与障碍物的交点,否则,i
Step1给变量设定取值范围[a,b]、群体大小m、
转到Step5。μii
混沌算子中的吸引子及父代间的互换率P,P和子
Step3过交点上做与顶面平行和垂直的平面。对ic1c2
代的变异率P[8]。
于平行平面,利用第3部分改进的CGA进行二维路径m⑸
Step2选用式所示的Logistic映射,关系式如下:
规划,找出最优路径轨迹(如图2)。对于垂直平面,使+1=()(1-)⑸
β(u)μβuβ(u)
用扩展因子在平面中进行三维扩展(如图3),扩展后的iiii
平面同样采用CGA进行路径寻优,然后选择距离最短其中i表示混沌变量的序号,i=1,…,r;u表示种群序号,
β≤β≤μ
的那条路径段作为最终的轨迹。u=0,1,…,m;表示混沌变量,01;表示吸引子。
μi⑸ii
Step4将交点1、交点2…,所有轨迹线交点的坐取u=0,=4[9]。先给式赋r个微小差异的初值,
iβ
得到r个混沌变量(1),(i=1,…,r)。依次取u=1,2,…,m,
标添加到Vega路径中,实现避障路径规划;i
Step5把S点移到当前位置,E点不变。按照SE可得到m个初始解群[10]。
β
方向继续向前搜索,若到达目标位置,则退出。若碰Step3用载波法[11],将选定r个混沌变量(u+1)分
⑹i
到障碍物,则转到Step2。别引入到式的r个优化变量中,使其变换为混沌变
量x',混沌变量的取值范围,会相应切换到相应的优化
3CGA二维路径规划及算法设计i
变量的取值范围[12]。
=+(+1)⑹
x'cdβu
在二维空间采用栅格法建模后,采用实数编码,iiii
运用CGA来优化路径。CGA是混沌算法(Chaos其中,c,d为变换常数,i=1,2,…,r。令
ii
万方数据
计算机时代2020年第11期·29·
=,,⋯,⑺
X(x1x2x)Step8按适应度值大小再次对群体排序,求出
r⑽
=,,⋯,⑻适应度平均值,按式的规则将其与最大值比对,若
X'(x'1x'2x')
r⑽
⑵式建立,则寻优结束并输出最优值,不然转到Step5。
Step4把式作为适应度函数的判断准则,计算
⑻按上述八个步骤对变异后的基因加入混沌扰动,
式生成的适应度值,把适应度值按照降序排列,因
且仅对某一代群体中适应度较小的90%的基因加混
为f(X′)小于0时不能作为适应度,而且即便f(X′)非
沌扰动,相当于对这些基因进行启发式的变异操作,
负,但若f(X′)对某一代群体相对变化范围过小,相当
可减少算法的进化代数,及早找到最优解;而且这种
于两代值过于靠近或类同,会造成算法收敛速率很
扰动有可能产生比前述10%较高适应度对应的基因
慢,因此还需要对f(X′)按下式作微小变化:
1更好的基因,有效地避免单纯的遗传算法局部收敛与
=-+(-)⑼
f'(X')f(X')f(X')f(X')f(X')早熟的问题,此外,由于遗传已生成10%的适应度较
kkminmmaxmin
其中f′(X′)为微小变化后的适应度值,f(X′)为微小高的基因,只对剩下90%的基因进行混沌扰动,缩小
kk
变化前的适应度值,f(X′)为微小变化前的最小适应了遗传算法的搜寻空间,可加速寻优速率。
min
度值,f(X′)为微小变化前的最大适应度值,m为群
max⑼4仿真及结果分析
体大小,按式调整后,适应度值均大于0,且适应度
值的相对变化范围加大,便于加大收敛速度。
⑴
Step5把所有变量按十进制进行编码,上一代群软件环境
体中适应度值排在前10%的变量不参与遗传的三种Vega是MultiGen-Paradigm公司最主要的工业软件
操作(复制、交叉、变异),直接进入下一代群体,剩下环境,用于实时视觉模拟、虚拟现实和普通视觉应用。
的90%由这三种操作生成,对子代群体按规则解码。Creator是MultiGen-Paradigm公司开发的一种用
Step6对下一代群体按规则计算出符合自身条件于创建逼真的三维模型和复杂地形的工具软件。
⑾
的适应度值,然后按式的规则适度调整,调整完毕VC++2015是Microsoft公司推出的Microsoft
按调整后的适应度值大小,对群体排序,求出适应度VisualStudio2015工具包里的软件之一,用于编写日
⑽
均值,并将其均值与适应度最大值按照式进行比常应用软件。
⑽
对,若式成立,则认为寻优过程结束,输出结果作为MatlabR2017b是MathWorks公司推出的专门用
⑽于科学、工程计算和系统仿真的高级语言。
最优值;若式不成立,执行Step7。⑵
----(----)-()<⑽硬件环境
|f'X'f'X'|ε1
max主机配置:Intel(R)Core(TM)i3-4130CPU,1G
其中
1内存,800G硬盘。操作系统:Windows10。
=∑()⑾
--------m
f'(X')=1f'X'
mjj
()=max⑿
f'X'{f'(X')}本文首先在二维环境下仿真,在VC++平台下实
max=1,2,⋯j
εjm现CGA路径寻优,并对相关数据借助Matlab曲线模拟
为预先给定的某个小正数。
1进行分析;然后以Vega为仿真平台,利用Creator工具
Step7在当前代群体中,选取适应度较小的90%
⑸建立100km×100km的三维地理环境模型,包括沙漠、
个体,找到其对应的最优解,先按照式的方法给其
⑹沼泽地、湖泊、城镇、乡村、道路、高大植物等,以城镇
加一混沌扰动,将其转换为混沌变量,然后再按式
建筑物和高大植物为障碍物,演示低空无人机在击中
的方法映射为混沌优化变量,最后将混沌变量和混沌
⑶目标时,避开这些障碍物寻优航迹的情况。
优化变量代入式,进行迭代计算。随着迭代次数的⑴
⑷二维环境仿真
增加,式计算出的α值不断变化,迭代逐步向最优解
在二维平面仿真中,运用栅格法对环境进行划分
逼近,逼近到先后两次计算出的适应度平均值之差小
(如图4)。
ε2
于预先给定的某个小正数时,运算结束。从图4中可以看出,满足约束条件的前提下,寻到
----(----)--------(-----)<⒀
|f'X'f'+1X'|ε2
kk了一条接近最优解的路径。由于遗传算法的随机性,
其中k为迭代次数,k=0,1,…;进行多次实验求其均值。
万方数据
·30·
考虑在三维中的应用情况,验证是否实现二维到三维
的平滑过渡与无缝连接。
图4CGA二维栅格避障图
图5改进的CGA在不同进化代数下的最优解
从图5看出,收敛速度较快,在第10代左右已寻
到最优解,且随着进化代数的增加,完好保持了最优为此,本文以Creator/Vega为仿真平台,建立仿真
解,并未发生传统遗传算法的解丢失情况。环境,完成对复杂地形地貌场景的设计。根据算法的
⑵
三维环境仿真设计情况,分别对水平与垂直两种情况下的航迹进行
仅考虑二维环境的路径规划是远远不够的,必须验证,避障仿真效果如图6和图7。
图6水平仿真避障图图7垂直仿真避障图
从图6、图7看出,用本文所设计方法进行三维环境也占用一定的时间而降低算法性能。
路径规划,画面运行流畅,不仅能避开障碍物,而且基本
符合真实性和实时性的要求,所规划出的路径也相对
较优。
⑶
运行时间与CPU占用率
当栅格数较小时,改进的混沌遗传算法较A*算法
有所改善但并不明显,是因为三维空间的数据值比较
小,使得运算与二维的复杂度接近,如图8所示。
但是随着栅格数的增加,搜素空间也逐步加大,
二维运算的优势逐步显现,运行时间大大缩短。因此图8程序运行时间对比图
当栅格数较小时,把三维空间转化为二维空间的效果5结束语
并不理想,甚至有可能因为在转化过程中,转化程序仿真结果表明,本文算法充分考虑了地形信息,
万方数据
计算机时代2020年第11期·31·
计算出来的航迹能主动的对障碍物进行判断并绕行[5]马云鹏,牛培峰,陈科,
避障,在航迹最佳性,搜寻实时性和算法时效性上更法锅炉NO_x模型优化研究[J].计量学报,(1):125-
高效,能够满足实时规划需要。129
[6][J].江南
参考文献(References):
大学学报(自然科学版),(6):746-750
[1]李猛,王道波,[7][D].天津
航迹规划[J].华南理工大学学报(自然科学版),,2017
(10):37-43[8][D].西安
[2]魏亭,*遗传算法的无人机三维航迹规划[J].建筑科技大学硕士学位论文,2016.
北京信息科技大学学报(自然科学版),:35-40[9]柳缔西子,范勤勤,
[3]ZENGJia-you,XIEYu-peng,BIANHong-fei,[J].智能系统学报,(5):818-
Researchonanti-saturationattackmodelofSAMto828
ARM[C]//InternationalConferenceonCommunications[10]李晓萌,王道波,郭继凯,杨华,
:Springer,算法的无人机航迹规划[J].机械与电子,(11):
2012:221-22715-19
[4]ChengLJ,DingYS,[11]孙健,井立,[J].
classifierwithimmuneclonalselectionalgorithmfor飞行力学,(3):52-55
automaticdiseriminantofprimaryopen-angleglauco-[12]余岩,王宏远,
▲
ma[J].Neurocomputing,(15):1-11方法[J].系统工程与电子技术,(4):707-711CE
􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻􀤻
(上接第25页)
配网对于合环潮流实时性,准确性的要求。配网主站算[J].电力系统及其自动化学报,:124-127
对上级电网的拓扑分析一般通过SCADA系统获取,[6]汲亚飞,[J].
本文采用的拓扑算法为“节点-节点”关联算法,后期电力系统保护与控制,(12):15-19
[7]徐华月,章坚民,
可以改进为“节点-支路”关联算法,把由节点、开关组
快速潮流计算[J].电力系统保护与控制,(7):45-48
成的物理模型转化为由母线、线路组成的数学模型。
[8]冯静,张建华,[J].
参考文献(References):现代电力,(3):41-44
[1]姜瀚书,孙翀也,贾彦兵,[9]ZimmermanR,Murillo-SanchezC,-
过程的分析与仿真[J].黑龙江电力,(2):88-90,94POWER:Steady-stateoperations,planningandanalysis
[2]邹俊雄,周冠波,付轲,[J].IEEE
与试验分析[J].电力系统保护与控制,(8):144-148TransactionsonPowerSystems,(1):12-19
[3]叶清华,唐国庆,王磊,谢敬东,吴国忠,[10]ZimmermanR,Murillo-SanchezC,GanDeqiang.
作环流分析系统的开发和应用[J].电力系统自动化,MATPOWER:AMATLABpowersystemsimulation
:66-69package[DB/OL].Ithaca,NY:PowerSystems
[4]曹亮,孔峰,[J].电网技EngineeringResearchCenteratCornellUniversity,
术,:58-602010[2014-12-17]./
▲
[5]葛少云,/.CE
万方数据