一种基于遗传算法一模式搜索法的无人机路径规划

一种基于遗传算法一模式搜索法的无人机路径 一种基于遗传算法一模式搜索法的无人机 路径规划 第29卷第3期 2009年O6月 弹箭与制导 JournalofProjectiles,Rockets,MissilesandGuidance V01.29NO.3 Jun2009 一 种基于遗传算法一模式搜索法的 无人机路径规划 袁麟博,章卫国,李广文 (西北工业大学自动化学院,西安710072) 摘要:为改善遗传算法局部寻优精度较差的固有缺陷,提出一种基于遗传算法一模式搜索法的无人机路径规 划算法.采用简单的一维编码示路径,构造了路径最优化的目标函数和适应度函数.先用遗传算法全局搜 索.得到全局近似最优路径,在此基础上使用局部寻优精度好的模式搜索法,得到精度更好的路径.仿真结果 表明所提的遗传算法一模式搜索法改善了单一遗传算法局部寻优精度较差的缺陷,提高了路径规划的精度. 关键词:路径规划;目标函数;遗传算法;模式搜索法 中图分类号:V279文献标志码:A APathPlanningforUAVBasedon Genetic-patternSearchingAlgorithm YUANLinbo.ZHANGWeiguo,LIGuangwen (SchoolofAutomation.NorthwesternPolytechnicalUniversity,Xi'an710072,China) Abstract:Apathplanningforunmannedaerialvehicle(UAV)basedongenetic-patternsearchingalgorithmwasproposed inordertOimprovetheinherentdisadvantageofthegeneticalgorithm.Thepathwasdenotedbyone-dimensioncoding. Theobjectivefunctionandthefitnessfunctionofthepathplanningproblemwereconstructed.Thepatternsearchingal— gorithmwasutilizedforsearchingtheimprovedpath,whichwasbasedontheglobalapproximateoptimalpathobtained bygeneticalgorithm.Thesimulationresultshowsthattheinherentdisadvantageofthegeneticalgorithmisimproved andtheprecisionofthepathisincreasedbythealgorithm. Keywords:pathplanning;objectivefunction;geneticalgorithm;patternsearchingalgorithm 0引言 无人机路径规划是指在分布了一些威胁区 域的任务区域中,在一定的约束条件下,寻找从 起始点到目标点的最优路径.其本质是多目标 多约束的最优化问.求解这类问题的典型算 法有dijkstra法,模拟退火法,人工势场法,遗传 算法等.由于遗传算法全局搜索能力强,适合全 局优化问题的求解,所以广泛应用于路径规划问 题[1].然而遗传算法局部寻优精度较差,使用 单一的遗传算法并不能得到最优的路径. 为了改善遗传算法局部寻优精度较差的固 有缺陷,文中借鉴了文献E51中算法混合的思路, 在遗传算法结束后转入局部寻优精度好的模式 搜索法,两种算法取长补短,规划出精度更高的 路径.仿真结果验证了所提算法的有效性. 1遗传算法一模式搜索法规划路径 1.1遗传算法 . 遗传算法是基于达尔文的进化论和孟德尔 的遗传学原理,由美国密歇根大学Holland教授 提出的进化算法.该算法模拟基因重组与进化 的自然过程,把待解决问题的参数编码构成个 体,许多个体构成种群,种群中的个体进行选择, 交叉和变异的运算,经过多次重复迭代直至得到 最后的优化结果.它的本质是一种并行的全局 优化算法. 路径点采用浮点数编码,在坐标系XOy. *收稿日期:2oo8一O7—26 作者简介:袁麟博(1982一),男,湖北襄樊人,硕士研究生,研究方向:飞行器路径规划. ? 280?弹箭与制导第29卷 中,路径点P的坐标是二维的,形如(z,Y),比 较复杂.为减少编码维数,旋转坐标系(xOY.旋 转变换为Xoy),X轴为起始点和目标点的连 线,将x2轴扎等分为Xl,X2,…,z1,X,每段长 为d.,过X作垂线,垂线上的某一点作为路径点 P,路径点的连线即为无人机的路径.路径可以 表示为((z,Y),(,Y1),(2do,y2),…,(nd0, Y),(,Y)),路径点的一维编码为(t,yz,…, y),(见图1). 遗传算法的 基本算子有选 择,交叉,变异三 种.选择又称复 制,是在种群中 选择生命力强即 适应度值大的个 体产生新种群的 / .at Y/ /x. 图1路径编码示意图 过程.适应度大的个体被遗传到下一代种群中的 概率较大.交叉又称重组,是按较大的概率从种 群中选择两个个体,交换两个个体的某些基因产 生新个体过程.产生的子代继承了父代的基本特 征.变异是以较小的概率改变个体上的某些基因 值,产生新个体的过程. 无人机路径规划的 目标主要有两个:回避威哥 胁;燃油代价最少.由目蓑 标函数确定的适应度函至 数是区分群体中个体好 坏的,也是选择的标 准.适应度函数总是非负 的,任何情况下都希望其 值越大越好. 图2无人机的 生存概率 为了最大程度的回避威胁,引入了生存概率 以评价路径回避威胁的优劣程度.它的函数 (见图2). UAV在路径点P受到威胁Tj时存活率为 qd,UAV在路径点P时的最小生存概率为: qf—min(q)(一1,…,)(1) 该路径回避威胁的目标函数为: objvall一?q(2) UAV存活概率越大,objval1越大. 燃油代价可以用路径的欧式距离来简单衡 量,UAV燃油代价的目标函数为: n objval2一?f一1 (z汁l—X1)+(斗1一Y1) (3) 最终的最小化的目标函数为: objval=+2*objval2(4) ooj~uu/~ ?为威胁回避权值,.为路径最短权值. 由目标函数确定的适应度函数为: fitval一盂L_(5)1 虽然遗传算法是一种通用且有效的全局寻优 算法,但是由于该算法局部寻优精度较差,所以单 独使用遗传算法并不能得到最优的路径.而模式 搜索法恰好局部寻优精度好,遗传算法与模式搜 索法混合可以取长补短,得到精度更高的路径. 1.2模式搜索法 模式搜索法是直接搜索法的一种,由两个动 作构成,分别称为探测移动和模式搜索[6].根据 动作的执行结果,重复执行其中之一,或交替执 行它们. 探测移动从一个基点R0依次沿个坐标轴 e一(O??.010…O)(=1,2,…,)的正反方向 以为步长探测目标值更小的点.设有探测点 R,探测开始时,R一R..如果f(R+)< f(R)则称e正向探测成功,探测点R移动到 R+.,准备沿方向e探测;如果f(R+)? f(R)则称e正向探测失败,再反过头来沿e负 方向探测.如果f(R一)<f(R)则称e反 向探测成功,探测点R移动到R一鼬,准备沿 方向e探测.如果f(R一,)?f(R)则称et 正反两个方向均失败,探测点R原地不动,准备 沿方向e探测.对所有坐标轴方向e执行上述过 程.探测移动完成后,有两种可能的结果:一种是 R?R0,即f(R)<f(R.),称为探测移动成功; 另一种是R一R.,即沿所有方向的探测全部失 败,称为探测移动失败.如果探测移动成功,则执 行模式搜索;如果探测移动失败,则缩短步长 ,称为收缩因子,0<<1.再从基点R.开 始重新探测,或进入模式搜索,直到步长小于给 第3期袁麟博等:一种基于遗传算法一模式搜索法的无人机路径规划.281' 定的截止误差容限,为止. 模式搜索是在探测移动的基础上进行的.当 探测移动得到了更好的点R,猜测方向R—R0 是一个目标函数值更小的方向,于是从当前位置 风出发沿该方向模式移动得到: Mo=R+(R一R0)一2R一Ro(6) 以Mo为基点作一次探测移动,得到M,如果 ,(M)<,(R),则称模式搜索成功,继续进行模 式搜索,即先从出发,沿方向一R模式移 动,得到新的Mo,再以Mo为基点作探测移动.如 果,(M)?,(民)则称模式搜索失败,此时应返 回R并缩短步长,重新开始探测移动. 1.3遗传算法一模式搜索法的基本步骤 stepl设定遗传算法与模式搜索法的各项控 制参数,将待优化的路径编码并生成初始路径种 群; step2根据式(1),式(5)计算种群中每条 路径的目标函数值和适应度值; step3选择,交叉,变异生成新的路径种群; step4判断:遗传代数小于最大遗传代数,如 果是,转到step2;如果否,从最终的种群中挑出 最优解..和最差解x,并转入step5; step5模式搜索法初始化,R.一&= lIxbc一x.lI2,一0.5,e一10一; step6以R.为基点,探测移动得到终点R; step7判断:f(R)<f(R.),如果是,转到 step8;如果否,转到steplO; step8Mo亡2R一Ro,以Mo为基点探测移 动,得到终点M; step9判断:厂()<f(R),如果是, Ro皇R,R,转到step8;如果否,RoR,并 转到step10; step10缩短步长口; stepl1判断:<e,如果是,算法终止,得到 最终路径;如果否,转到step6. 2仿真算例 为验证所提算法的正确性,采用两种仿真方 案进行对比.A为单一的遗传算法,种群规 模为2O,交叉概率为0.8,变异概率为0.2,最大 遗传代数为lOO,用虚线表示路径.方案B为所提 出的一种遗传算法一模式搜索法,遗传算法的所 有参数与方案A的参数相同,模式搜索法初始步 长一lI.一xw.Ill引,收缩因子为0.5,截 止误差容限e为10一km,最大迭代次数为5O,用 实线表示路径.起始点和目标点分别用三角形和 方形表示.威胁分为三种,有效威胁半径依次为 3km,2km,lkm,用六角形表示威胁所在位置,用 不同半径的圆表示威胁范围.权系数?t一200, 叫.=1.起始点为(O,O),目标点为(14,14)单位 为km.每种任务区域做100次仿真,当路径不穿 越威胁区域且目标值和平均目标值相差50以 内时,认为算法成功.否则认为失败【4].仿真图见 图3,图4,仿真结果见表1,表3. l6 14 12 1o E8 i6 4 2 0 — 2 图3较少威胁时 的规划路径 仿真图表明, 所提算法规划出 的路径更平滑. 实验数据表明所 提算法各项结果 均优于单一的遗 传算法.当威胁 区域变密集时, 单一遗传算法的 成功率下降较 大,而所提算法 的成功率仍然保 16 l4 12 10 g8 i6 4 2 0 — 2 图4较多威胁时 的规划路径 表1成功率对比 表2目标值均值对比 表3目标值标准差对比 持在较高水平.两种情况下,所提算法规划出的 路径的目标值及其标准差都小于简单遗传算法. 说明路径精度更高,算法更稳定. 3结论 针对遗传算法局部寻优精度较差的固有缺 陷,提出了一种基于遗传算法一模式搜索法的无 ? 282?弹箭与制导第29卷 (上接第275页) 实的多普勒频移.图7则是采用光学延迟环将脉 冲重复频率提高1O倍后的相位检波器时域输出 信号,这时,脉冲重复频率(也就是采样频率)达到 了60kHz,通过相位检波器可以得到真实的. 3 88fi}88玲,38{i{i?{il…{i{…{ 洲i}iii{y《《,也;i{;{iffi《_ 图6低PRF状态下相位检波器的输 出,难以得到真实的多普勒频移 图7高PRF状态下相位检波器的 输出,真实反映多普勒频移 结论 在测距阶段采用低PRF,可以得到不模糊的 距离信息,然后对进入距离门的回波脉冲进行复 制,得到高PRF相参脉冲串,再利用新得到的高 PRF相参脉冲串测速,可以得到不模糊的速度 信息,使得在发射低PRF信号的状态下,不但能 不模糊的测距,还能够不模糊的测速. 参考文献: E1]邱绍峰,范戈.光纤延迟线在雷达信号处理中的 应用EJ].光电技术,2003,29(4):429—430. [2]张忠华.孙晓昶.光控相控阵雷达[J].电讯技术, 2004(2):71—75. [3]酆达,李铮,郑铮,等.基于光纤延迟的光脉冲有源 复制器rJ].北京航空航天大学,2005,31 (12):2l2—2l7. [4]陈宇晓,酆达.光脉冲光纤周期复制技术研究[J]. 激光技术,2005,29(6):6O4—607. [5]林茂庸,柯有安.雷达信号理论[M].北京:国防工 业出版社,1984. [6]丁鹭飞,耿富录.雷达原理[M].西安:电子科技大 学出版社.1984. [7]解安国,薛余网,郭建文.微波光纤延迟线技术研究 [J].光纤与电缆及其应用技术.2002(4):1—5. [8]Ming—ChiangLi.AhighprecisionDopplerradar basedonopticalfiberdelayloopsEJ~.IEEETrans— actionsonAntennasandPropagation.2004,52 (12):3319—3328.