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

　第 29 卷 　第 3 期2009 年 06 月 弹 　箭 　与 　制 　导 　学 　报 Journal of Projectiles , Rocket s , Missiles and Guidance Vol. 29 　No. 3 J un 2009 　 一种基于遗传算法2模式搜索法的 无人机路径规划 3 袁麟博 ,章卫国 ,李广文 (西北工业大学自动化学院 ,西安 　710072) 摘 　要 :为改善遗传算法局部寻优精度较差的固有缺陷 ,提出一种基于遗传算法2模式搜索法的无人机路径规 划算法。采用简单的一维编码表示路径 ,构造了路径最优化的目标函数和适应度函数。先用遗传算法全局搜 索 ,得到全局近似最优路径 ,在此基础上使用局部寻优精度好的模式搜索法 ,得到精度更好的路径。仿真结果 表明所提的遗传算法2模式搜索法改善了单一遗传算法局部寻优精度较差的缺陷 ,提高了路径规划的精度。 关键词 :路径规划 ;目标函数 ;遗传算法 ;模式搜索法 中图分类号 : V279 　　文献标志码 :A A Path Planning for UAV Based on Genetic2pattern Searching Algorithm YUAN Linbo , ZHAN G Weiguo , L I Guangwen (School of Automation , Northwestern Polytechnical University , Xi’an 710072 , China) Abstract :A path planning for unmanned aerial vehicle (UAV) based on genetic2pattern searching algorithm was proposed in order to improve the inherent disadvantage of the genetic algorithm. The path was denoted by one2dimension coding. The objective function and the fitness function of the path planning problem were const ructed. The pattern searching al2 gorithm was utilized for searching the improved path , which was based on the global approximate optimal path obtained by genetic algorithm. The simulation result shows that the inherent disadvantage of the genetic algorithm is improved and the precision of the path is increased by the algorithm. Keywords :path planning ; objective function ; genetic algorithm ; pattern searching algorithm 0 　引言 无人机路径规划是指在分布了一些威胁区 域的任务区域中 ,在一定的约束条件下 ,寻找从 起始点到目标点的最优路径。其本质是多目标 多约束的最优化问题。求解这类问题的典型算 法有 dijkst ra 法、模拟退火法、人工势场法、遗传 算法等。由于遗传算法全局搜索能力强 ,适合全 局优化问题的求解 ,所以广泛应用于路径规划问 题[1 - 3 ] 。然而遗传算法局部寻优精度较差 ,使用 单一的遗传算法并不能得到最优的路径。 为了改善遗传算法局部寻优精度较差的固 有缺陷 ,文中借鉴了文献[ 5 ]中算法混合的思路 , 在遗传算法结束后转入局部寻优精度好的模式 搜索法 ,两种算法取长补短 ,规划出精度更高的 路径。仿真结果验证了所提算法的有效性。 1 　遗传算法2模式搜索法规划路径 1 . 1 　遗传算法 遗传算法是基于达尔文的进化论和孟德尔 的遗传学原理 ,由美国密歇根大学 Holland 教授 提出的进化算法。该算法模拟基因重组与进化 的自然过程 ,把待解决问题的参数编码构成个 体 ,许多个体构成种群 ,种群中的个体进行选择、 交叉和变异的运算 ,经过多次重复迭代直至得到 最后的优化结果。它的本质是一种并行的全局 优化算法。 路径点采用浮点数编码 , 在坐标系 X1 OY13 收稿日期 :2008 - 07 - 26 作者简介 :袁麟博 (1982 - ) ,男 ,湖北襄樊人 ,硕士研究生 ,研究方向 :飞行器路径规划。 弹 箭 与 制 导 学 报 第 29 卷 　 中 ,路径点 pi 的坐标是二维的 ,形如 ( x i , y i ) ,比 较复杂。为减少编码维数 ,旋转坐标系 ( X1 OY1 旋 转变换为 X2 OY2 ) , X2 轴为起始点和目标点的连 线 ,将 X2 轴 n 等分为 x 1 , x2 , ⋯, x n- 1 , x n ,每段长 为 d0 ,过 x i 作垂线 ,垂线上的某一点作为路径点 pi ,路径点的连线即为无人机的路径。路径可以 表示为 ( ( xs , ys) , ( d0 , y1 ) , (2 d0 , y2 ) , ⋯, ( nd0 , y n) , ( x g , y g ) ) ,路径点的一维编码为 ( y1 , y2 , ⋯, y n) , (见图 1) 。 图 1 　路径编码示意图 遗传算法的 基本算子有选 择、交叉、变异三 种。选择又称复 制 , 是在种群中 选择生命力强即 适应度值大的个 体产生新种群的 过程。适应度大的个体被遗传到下一代种群中的 概率较大。交叉又称重组 ,是按较大的概率从种 群中选择两个个体 ,交换两个个体的某些基因产 生新个体过程。产生的子代继承了父代的基本特 征。变异是以较小的概率改变个体上的某些基因 值 ,产生新个体的过程。 图 2 　无人机的 生存概率 无人机路径规划的 目标主要有两个 : 回避 威胁 ;燃油代价最少。由 目标函数确定的适应度 函数是区分群体中个体 好坏的 , 也是选择 的标准。适应度函数总 是非负的 , 任何情况下 都希望其值越大越好。 为了最大程度的回 避威胁 ,引入了生存概率以评价路径回避威胁的 优劣程度[3 ] 。它的函数 (见图 2) 。 UAV 在路径点 pi 受到威胁 T j 时存活率为 q ij , UAV 在路径点 pi 时的最小生存概率为 : qi = min m j = 1 ( qij ) 　( i = 1 , ⋯, n) (1) 该路径回避威胁的目标函数为 : obj v al1 = ∑ n i = 1 qi (2) UAV 存活概率越大 , obj v al1 越大。 燃油代价可以用路径的欧式距离来简单衡 量 , UAV 燃油代价的目标函数为 : obj v al2 = ∑ n i = 1 x i+1 - x i 2 + y i+1 - y i 2 (3) 最终的最小化的目标函数为 : obj v al = ω1 obj v al1 +ω2 3 obj v al2 (4) ω1 为威胁回避权值 ,ω2 为路径最短权值。 由目标函数确定的适应度函数为 : f i t v al = 1 obj v al (5) 虽然遗传算法是一种通用且有效的全局寻优 算法 ,但是由于该算法局部寻优精度较差 ,所以单 独使用遗传算法并不能得到最优的路径。而模式 搜索法恰好局部寻优精度好 ,遗传算法与模式搜 索法混合可以取长补短 ,得到精度更高的路径。 1 . 2 　模式搜索法 模式搜索法是直接搜索法的一种 ,由两个动 作构成 ,分别称为探测移动和模式搜索[6 ] 。根据 动作的执行结果 ,重复执行其中之一 ,或交替执 行它们。 探测移动从一个基点 R0 依次沿 n 个坐标轴 e j = (0 ⋯010 ⋯0) T ( i = 1 ,2 , ⋯, n) 的正反方向 以δ为步长探测目标值更小的点。设有探测点 Rn ,探测开始时 , Rn = R0 。如果 f ( Rn +δe1 ) < f ( Rn) 则称 e1 正向探测成功 ,探测点 Rn 移动到 Rn +δe1 ,准备沿方向 e2 探测 ;如果 f ( Rn +δe1 ) ≥ f ( Rn) 则称 e1 正向探测失败 ,再反过头来沿 e1 负 方向探测。如果 f ( Rn - δe1 ) < f ( Rn) 则称 e1 反 向探测成功 ,探测点 Rn 移动到 Rn - δe1 ,准备沿 方向 e2 探测。如果 f ( Rn - δe1 ) ≥ f ( Rn) 则称 e1 正反两个方向均失败 ,探测点 Rn 原地不动 ,准备 沿方向 e2 探测。对所有坐标轴方向 ej 执行上述过 程。探测移动完成后 ,有两种可能的结果 :一种是 Rn ≠R0 ,即 f ( Rn) < f ( R0 ) ,称为探测移动成功 ; 另一种是 Rn = R0 ,即沿所有方向的探测全部失 败 ,称为探测移动失败。如果探测移动成功 ,则执 行模式搜索 ; 如果探测移动失败 , 则缩短步长 δαβδ,β称为收缩因子 ,0 <β< 1。再从基点 R0 开 始重新探测 ,或进入模式搜索 ,直到步长小于给 ·082· 　第 3 期 袁麟博等 :一种基于遗传算法 2模式搜索法的无人机路径规划 定的截止误差容限ε为止。 模式搜索是在探测移动的基础上进行的。当 探测移动得到了更好的点 Rn ,猜测方向 Rn - R0 是一个目标函数值更小的方向 ,于是从当前位置 Rn 出发沿该方向模式移动得到 : M0 = Rn + ( Rn - R0 ) = 2 Rn - R0 (6) 以 M0 为基点作一次探测移动 ,得到 Mn ,如果 f ( Mn) < f ( Rn) ,则称模式搜索成功 ,继续进行模 式搜索 ,即先从 Mn 出发 ,沿方向 Mn - Rn 模式移 动 ,得到新的 M0 ,再以 M0 为基点作探测移动。如 果 f ( Mn) ≥ f ( Rn) 则称模式搜索失败 ,此时应返 回 Rn 并缩短步长δαβδ,重新开始探测移动。 1 . 3 　遗传算法 2模式搜索法的基本步骤 step1 设定遗传算法与模式搜索法的各项控 制参数 ,将待优化的路径编码并生成初始路径种 群 ; step2 根据式 (1) ～ 式 (5) 计算种群中每条 路径的目标函数值和适应度值 ; step3 选择、交叉、变异生成新的路径种群 ; step4 判断 :遗传代数小于最大遗传代数 ,如 果是 ,转到 step2 ;如果否 ,从最终的种群中挑出 最优解 Xbest 和最差解 Xworst ,并转入 step5 ; step5 模式搜索法初始化 , R0 = Xbest ,δ0 = ‖Xbest - Xworst ‖2 ,β= 0 . 5 ,ε= 10 - 6 ; step6 以 R0 为基点 ,探测移动得到终点 Rn ; step7 判断 : f ( Rn) < f ( R0 ) ,如果是 ,转到 step8 ;如果否 ,转到 step10 ; step8 M0 α2 Rn - R0 , 以 M0 为基点探测移 动 ,得到终点 Mn ; step9 判 断 : f ( Mn) < f ( Rn) , 如 果 是 , R0 α Rn , Rn α Mn ,转到 step8 ;如果否 , R0 α Rn ,并 转到 step10 ; step10 缩短步长δαβδ; step11 判断 :δ <ε,如果是 ,算法终止 ,得到 最终路径 ;如果否 ,转到 step6。 2 　仿真算例 为验证所提算法的正确性 ,采用两种仿真方 案进行对比。 A 为单一的遗传算法 ,种群规 模为 20 ,交叉概率为 0 . 8 ,变异概率为 0 . 2 ,最大 遗传代数为 100 ,用虚线表示路径。方案B为所提 出的一种遗传算法 2模式搜索法 ,遗传算法的所 有参数与方案 A 的参数相同 ,模式搜索法初始步 长δ0 = ‖Xbest - Xworst ‖[5 ]2 ,收缩因子为 0 . 5 ,截 止误差容限ε为 10 - 6 km ,最大迭代次数为 50 ,用 实线表示路径。起始点和目标点分别用三角形和 方形表示。威胁分为三种 ,有效威胁半径依次为 3km ,2km ,1km ,用六角形表示威胁所在位置 ,用 不同半径的圆表示威胁范围。权系数ω1 = 200 , ω2 = 1。起始点为 (0 ,0) ,目标点为 (14 ,14) 单位 为 km。每种任务区域做 100 次仿真 ,当路径不穿 越威胁区域且目标值和平均目标值相差 50 % 以 内时 ,认为算法成功。否则认为失败[4 ] 。仿真图见 图 3 ～图 4 ,仿真结果见表 1 ～表 3。 表 1 　成功率对比 图 3 图 4 方案 A 92 % 67 % 方案 B 95 % 82 % 表 2 　目标值均值对比 图 3 图 4 方案 A 36. 3634 38. 3097 方案 B 35. 4390 36. 4807 表 3 　目标值标准差对比 图 3 图 4 方案 A 1. 0397 2. 0133 方案 B 0. 4513 1. 5790 　　仿真图表明 , 所提算法规划出 的路径更平滑。 实验数据表明所 提算法各项结果 均优于单一的遗 传算法。当威胁 区域变密集时 , 单一遗传算法的 成功 率 下 降 较 大 ,而所提算法 的成功率仍然保 持在较高水平。两种情况下 ,所提算法规划出的 路径的目标值及其标准差都小于简单遗传算法。 说明路径精度更高 ,算法更稳定。 3 　结论 针对遗传算法局部寻优精度较差的固有缺 陷 ,提出了一种基于遗传算法2模式搜索法的无 ·182· 弹 箭 与 制 导 学 报 第 29 卷 　 人机路径规划算法。仿真结果表明该算法可有 效解决单一遗传算法寻优精度较差的缺点 ,规划 出的路径精度更高 ,并在一定程度上提高了路径 规划的成功率。 参考文献 : [1 ] 　HAN W G , BA EK S M. Genetic algorithm based path planning and dynamic obstacle avoidance of mobile robot s[ C] / / IEEE. 1997 :2747 - 2751. [2 ] 　Pellazar M B. Vehicle route planning with con2 st raint s using Genetic algorithms[ C] / / Proceeding of IEEE NA ECON , 1998 :392 - 399. [3 ] 　贾秋玲 ,李广文 ,闫建国. 基于遗传算法的无人机协 同逆推式路径规划[ J] . 西北工业大学学报 ,2007 , 25 (4) :590 - 593. [4 ] 　唐国新 ,陈雄 ,袁杨. 机器人路径规划中的改进型遗 传算法[ J] . 计算机工程与应用 ,2007 ,43 (22) :67 - 70. [5 ] 　李广文. 进化算法及其在飞行控制系统中的应用 [ D] . 西安 :西北工业大学 ,2007. [6 ] 　栗塔山. 最优化计算原理与算法程序设计[ M] . 长 沙 :国防科技大学出版社 ,2002. (上接第 275 页) 实的多普勒频移。图 7 则是采用光学延迟环将脉 冲重复频率提高 10 倍后的相位检波器时域输出 信号 ,这时 ,脉冲重复频率 (也就是采样频率) 达到 了 60k Hz ,通过相位检波器可以得到真实的 f d 。 3 　结论 在测距阶段采用低 PRF ,可以得到不模糊的 距离信息 ,然后对进入距离门的回波脉冲进行复 制 ,得到高 PRF 相参脉冲串 ,再利用新得到的高 PRF 相参脉冲串测速 ,可以得到不模糊的速度 信息 ,使得在发射低 PRF 信号的状态下 ,不但能 不模糊的测距 ,还能够不模糊的测速。 参考文献 : [1 ] 　邱绍峰 , 范戈. 光纤延迟线在雷达信号处理中的 应用[ J] . 光电技术 ,2003 ,29 (4) :429 - 430. [2 ] 　张忠华 ,孙晓昶 . 光控相控阵雷达[ J] . 电讯技术 , 2004 (2) :71 - 75. [3 ] 　酆达 ,李铮 ,郑铮 ,等. 基于光纤延迟的光脉冲有源 复制器 [ J] . 北京航空航天大学学报 , 2005 , 31 (12) :212 - 217. [4 ] 　陈宇晓 ,酆达. 光脉冲光纤周期复制技术研究[ J] . 激光技术 ,2005 ,29 (6) :604 - 607. [5 ] 　林茂庸 ,柯有安. 雷达信号理论[ M] . 北京 :国防工 业出版社 ,1984. [6 ] 　丁鹭飞 ,耿富录. 雷达原理[ M] . 西安 :电子科技大 学出版社 ,1984. [7 ] 　解安国 ,薛余网 ,郭建文. 微波光纤延迟线技术研究 [ J] . 光纤与电缆及其应用技术 , 2002 (4) :1 - 5. [8 ] 　Ming2Chiang Li. A high precision Doppler radar based on optical fiber delay loops[ J] . IEEE Trans2 actions on Antennas and Propagation , 2004 , 52 (12) :3319 - 3328. ·282·