D0I:10.13374/.issn1001-053x.2012.01.020 第34卷第1期 北京科技大学学报 Vol.34 No.1 2012年1月 Journal of University of Science and Technology Beijing Jan.2012 基于改进差分进化算法的无人机在线低空突防航迹 规划 彭志红2) 孙琳12刃四陈杰12》 1)北京理工大学自动化学院，北京1000812)北京理工大学复杂系统智能控制与决策教有部重点实验室，北京100081 ☒通信作者，E-mail:s5sin@163.com 摘要为了解决无人机在部分未知敌对环境中的低空突防航迹规划问题，提出了一种改进的差分进化算法.该算法的进化 模型采用冯·诺伊曼拓扑结构，并对其进行拓展，使种群在进化初期保持多样性，避免进化早期陷入局部最优，而进化后期加 快收敛速度.该算法改进了差分进化算子中的变异操作，从而加快算法的收敛速度，快速找到多目标优化问题的最优解：同 时，采用将绝对笛卡儿坐标和相对极坐标相结合的编码方式以提高搜索效率.将该算法用于无人机在线航迹规划仿真实验， 并和未改进的算法结果作比较，验证了该算法的有效性. 关键词无人机：低空突防：差分进化算法：在线航迹规划 分类号TP391.9 Online path planning for UAV low-altitude penetration based on an improved differential evolution algorithm PENG Zhi--hong2,SUN Lin2☒，CHEN Jie,2 1)School of Automation,Beijing Institute of Technology,Beijing 100081,China 2)Key Laboratory of the Ministry of Education of China for Complex System Intelligent Control and Decision,Beijing Institute of Technology,Beijing 100081,China Corresponding author,E-mail:ssslin@163.com ABSTRACT An improved differential evolution algorithm was proposed for solving the online path planning problem of unmanned aerial vehicle (UAV)low-altitude penetration in partially known hostile environments.The algorithm adopts von Neumann topology and improves its structure to maintain the diversity of the population,prevent the population from falling into local optima in the early evolu- tion and speed up the convergence rate in the later evolution as well.The mutation operator of differential evolution is improved to speed up the convergence rate of the algorithm,so that the optimal solution of the multi-objective optimization problem can be found quickly: the coding method combined the absolute Cartesian coordinates with the relative polar coordinates is used to improve the searching effi- ciency.The simulation experiment of online path planning for UAV low-altitude penetration shows that the proposed algorithm has a better performance than the unimproved differential evolution algorithm. KEY WORDS unmanned aerial vehicles (UAV);low altitude penetration:differential evolution algorithms;online path planning 无人机在现代战争中扮演着日益重要的角色. 满足无人机的物理约束.在实际作战环境中，往往 在军事攻击作战任务中，低空突防技术以实现地形 存在诸多不确定性因素，如地形预先未知和出现突 跟随、地形回避和威胁回避飞行为目的，其中航迹规 发威胁，此时需要无人机进行实时在线航迹规划，要 划是实现无人机低空突防的关键.低空突防航迹规 求其能够在短时间内快速准确地规划出满足各种约 划就是利用地形和敌情等信息，规划出飞行器生存 束条件并且航迹性能指标最优的航迹. 概率和航程综合指标最优的突防航迹口，同时还要 差分进化算法(differential evolution,DE)是一 收稿日期：201105-26 基金项目：省部级重点基金资助项目9140A17051010BQ0104):省部级一般基金资助项目(9140A06040510BQ0121)
第 34 卷 第 1 期 2012 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 1 Jan． 2012 基于改进差分进化算法的无人机在线低空突防航迹 规划 彭志红1，2) 孙 琳1，2) 陈 杰1，2) 1) 北京理工大学自动化学院，北京 100081 2) 北京理工大学复杂系统智能控制与决策教育部重点实验室，北京 100081 通信作者，E-mail: ssslin@ 163． com 摘 要 为了解决无人机在部分未知敌对环境中的低空突防航迹规划问题，提出了一种改进的差分进化算法． 该算法的进化 模型采用冯·诺伊曼拓扑结构，并对其进行拓展，使种群在进化初期保持多样性，避免进化早期陷入局部最优，而进化后期加 快收敛速度． 该算法改进了差分进化算子中的变异操作，从而加快算法的收敛速度，快速找到多目标优化问题的最优解; 同 时，采用将绝对笛卡儿坐标和相对极坐标相结合的编码方式以提高搜索效率． 将该算法用于无人机在线航迹规划仿真实验， 并和未改进的算法结果作比较，验证了该算法的有效性． 关键词 无人机; 低空突防; 差分进化算法; 在线航迹规划 分类号 TP391. 9 Online path planning for UAV low-altitude penetration based on an improved differential evolution algorithm PENG Zhi-hong1，2) ，SUN Lin1，2) ，CHEN Jie 1，2) 1) School of Automation，Beijing Institute of Technology，Beijing 100081，China 2) Key Laboratory of the Ministry of Education of China for Complex System Intelligent Control and Decision，Beijing Institute of Technology，Beijing 100081，China Corresponding author，E-mail: ssslin@ 163． com ABSTRACT An improved differential evolution algorithm was proposed for solving the online path planning problem of unmanned aerial vehicle ( UAV) low-altitude penetration in partially known hostile environments． The algorithm adopts von Neumann topology and improves its structure to maintain the diversity of the population，prevent the population from falling into local optima in the early evolution and speed up the convergence rate in the later evolution as well． The mutation operator of differential evolution is improved to speed up the convergence rate of the algorithm，so that the optimal solution of the multi-objective optimization problem can be found quickly; the coding method combined the absolute Cartesian coordinates with the relative polar coordinates is used to improve the searching efficiency． The simulation experiment of online path planning for UAV low-altitude penetration shows that the proposed algorithm has a better performance than the unimproved differential evolution algorithm． KEY WORDS unmanned aerial vehicles ( UAV) ; low altitude penetration; differential evolution algorithms; online path planning 收稿日期: 2011--05--26 基金项目: 省部级重点基金资助项目 9140A17051010BQ0104) ; 省部级一般基金资助项目( 9140A06040510BQ0121) 无人机在现代战争中扮演着日益重要的角色． 在军事攻击作战任务中，低空突防技术以实现地形 跟随、地形回避和威胁回避飞行为目的，其中航迹规 划是实现无人机低空突防的关键． 低空突防航迹规 划就是利用地形和敌情等信息，规划出飞行器生存 概率和航程综合指标最优的突防航迹［1］，同时还要 满足无人机的物理约束． 在实际作战环境中，往往 存在诸多不确定性因素，如地形预先未知和出现突 发威胁，此时需要无人机进行实时在线航迹规划，要 求其能够在短时间内快速准确地规划出满足各种约 束条件并且航迹性能指标最优的航迹． 差分进化算法( differential evolution，DE) 是一 DOI:10.13374/j.issn1001-053x.2012.01.020
第1期 彭志红等：基于改进差分进化算法的无人机在线低空突防航迹规划 ·97 种基于群体差异的启发式随机搜索算法，该算法是 式中，(xya)为山峰中心点在平面坐标系中的坐标 Stom和Pice为求解切比雪夫多项式而提出的回， 值，h为控制山峰高度的参数，m,和m2为反映山坡 因其原理简单、受控参数少、鲁棒性强以及良好的全 陡度的系数 局寻优能力，被广泛用于多目标优化问题.loannis 地形约束包括无人机水平飞行范围约束和山峰 和Athina将差分进化算法用于二维环境下的无人 避碰约束.无人机在飞行过程中不能超越预先设定 机离线规划)，Chem等将差分进化算法用于动态目 的水平区域范围，这里的范围指无人机飞行全程水 标武器分配决策问题回.然而，传统的差分进化算 平规划范围.山峰避碰约束指无人机规划的航迹高 法在解决复杂的多目标优化问题时，往往存在容易 度不能低于所在位置的山峰高度，否则会使无人机 陷入局部最优、收敛速度慢等问题.为了提高差分 和山峰碰撞，造成巨大损失 进化算法的搜索效率，有效解决无人机在线低空突 为了提高低空突防在线航迹规划的实时性，本 防航迹规划问题，本文提出了一种改进的差分进化 文在差分进化算法初始化及其进化过程中将地形约 算法.该算法改进如下：(1)种群进化模型采用冯· 束直接嵌入其中，设定水平方向规划范围为(X, 诺伊曼拓扑结构)，并对其进行拓展.每个个体在 X)和(Ya,Ya）,飞行避碰约束范围（Hn, 进化初期只受周围邻居的影响，和其发生作用，多个 H）,这里的Hn为最小离地高度，Hn为最大离地 子种群同时进化，以保持种群多样性，克服标准差分 高度，Hmn可以避免无人机和山峰碰撞，Hm可以保 进化算法容易陷入局部最优的缺陷；个体进化后期 证飞行高度不超过一定范围，更安全.初始化和进 为了加快收敛速度，在子种群中引入全局最优解，参 化过程中的航迹点都限定在此范围之内 与进化过程.(2)改进差分进化算子中的变异操作， 1.2无人机物理约束 通过加入局部/全局最优解的差分项和基向量，并设 无人机的物理约束主要考虑无人机的最大拐弯 计动态缩放比例因子，在加快算法收敛性的同时，抑 角a、最大爬升/下滑角B、最小直飞距离约束l以 制其陷入局部最优，达到快速找到多目标优化问题 及探测范围R.如果违反了这些约束，则规划出来 最优解的目的.(3)采用将绝对坐标和相对极坐标 的航迹无人机无法执行.对于无人机物理约束，本 相结合的编码方式，在规划初期采用相对极坐 文引入了惩罚函数)，惩罚函数值的大小反映了所 标，利用其对路径点位置和方位的限制，显著减少搜 规划航迹对约束的违背程度，惩罚函数值越小，航迹 索空间，加快差分进化算法的收敛性，并保证规划范 质量越高。各物理约束的惩罚函数分别如下： 围在机载雷达探测范围内：在交叉和变异操作阶段， r0, ≤Cmxt (2) 使用绝对笛卡儿坐标，如此只引起局部改变，克服相 Kh,a>amuns 对极坐标会引起全局改变的缺陷. r0, B≤βnmxi 本文中无人机在执行低空突防任务之前，三维 K,BB (3) 地形环境是未知的，需要根据机载雷达扫描周围环 rK1,l≤lin: 境，确定地形信息，并根据机载定位设备实时计算所 m=0, (4) 1>luin 处位置.在无人机探测出所处位置环境信息后，进 r0, T≤R; 行局部最优路径规划，沿着所规划路径飞行，不断重 fmK. (5) r>R. 复扫描，直到无人机到达目标点 式中，K、K,、K和K,分别为最大拐弯角、最大爬 1 数学建模 升/下滑角、最小直飞距离约束以及深测范围的惩罚 系数 无人机在线航迹规划可以看作是多约束多目标 将各惩罚函数综合考虑，得到无人机物理约束 优化问题，为了模拟无人机的飞行环境，本文从地形 惩罚代价函数表示如下： 约束、无人机物理约束和航迹性能指标约束几个方 (6) 面建立问题的模型，并给出了处理各约束模型的 plysical =/hnge+vangle min+fdetect 若惩罚函数值为0，说明所规划航迹没有违反 方式. 物理约束，航迹是可飞的 1.1地形约束 1.3航迹性能指标约束 三维环境下的地形可以用下式描述： 航迹性能指标约束主要指航程、高程和威胁约 :(,）=he（-.=) (1) 束，航程、高程和威胁指标是衡量低空突防轨迹优劣
第 1 期 彭志红等: 基于改进差分进化算法的无人机在线低空突防航迹规划 种基于群体差异的启发式随机搜索算法，该算法是 Stom 和 Price 为求解切比雪夫多项式而提出的［2］， 因其原理简单、受控参数少、鲁棒性强以及良好的全 局寻优能力，被广泛用于多目标优化问题． Ioannis 和 Athina 将差分进化算法用于二维环境下的无人 机离线规划［3］，Chen 等将差分进化算法用于动态目 标武器分配决策问题［4］． 然而，传统的差分进化算 法在解决复杂的多目标优化问题时，往往存在容易 陷入局部最优、收敛速度慢等问题． 为了提高差分 进化算法的搜索效率，有效解决无人机在线低空突 防航迹规划问题，本文提出了一种改进的差分进化 算法． 该算法改进如下: ( 1) 种群进化模型采用冯· 诺伊曼拓扑结构［5］，并对其进行拓展． 每个个体在 进化初期只受周围邻居的影响，和其发生作用，多个 子种群同时进化，以保持种群多样性，克服标准差分 进化算法容易陷入局部最优的缺陷; 个体进化后期 为了加快收敛速度，在子种群中引入全局最优解，参 与进化过程． ( 2) 改进差分进化算子中的变异操作， 通过加入局部/全局最优解的差分项和基向量，并设 计动态缩放比例因子，在加快算法收敛性的同时，抑 制其陷入局部最优，达到快速找到多目标优化问题 最优解的目的． ( 3) 采用将绝对坐标和相对极坐标 相结合的编码方式［6］，在规划初期采用相对极坐 标，利用其对路径点位置和方位的限制，显著减少搜 索空间，加快差分进化算法的收敛性，并保证规划范 围在机载雷达探测范围内; 在交叉和变异操作阶段， 使用绝对笛卡儿坐标，如此只引起局部改变，克服相 对极坐标会引起全局改变的缺陷． 本文中无人机在执行低空突防任务之前，三维 地形环境是未知的，需要根据机载雷达扫描周围环 境，确定地形信息，并根据机载定位设备实时计算所 处位置． 在无人机探测出所处位置环境信息后，进 行局部最优路径规划，沿着所规划路径飞行，不断重 复扫描，直到无人机到达目标点． 1 数学建模 无人机在线航迹规划可以看作是多约束多目标 优化问题，为了模拟无人机的飞行环境，本文从地形 约束、无人机物理约束和航迹性能指标约束几个方 面建立问题的模型，并给出了处理各约束模型的 方式． 1. 1 地形约束 三维环境下的地形可以用下式描述: z( x，y) = h· ( e － ( x － x0) 2 m1 － ( y － y0) 2 m ) 2 2 . ( 1) 式中，( x0，y0 ) 为山峰中心点在平面坐标系中的坐标 值，h 为控制山峰高度的参数，m1和 m2 为反映山坡 陡度的系数． 地形约束包括无人机水平飞行范围约束和山峰 避碰约束． 无人机在飞行过程中不能超越预先设定 的水平区域范围，这里的范围指无人机飞行全程水 平规划范围． 山峰避碰约束指无人机规划的航迹高 度不能低于所在位置的山峰高度，否则会使无人机 和山峰碰撞，造成巨大损失． 为了提高低空突防在线航迹规划的实时性，本 文在差分进化算法初始化及其进化过程中将地形约 束直接嵌入其中，设定水平方向规划范围为( Xmin， Xmax ) 和 ( Ymin，Ymax ) ，飞 行 避 碰 约 束 范 围 ( Hmin， Hmax ) ，这里的 Hmin为最小离地高度，Hmax为最大离地 高度，Hmin可以避免无人机和山峰碰撞，Hmax可以保 证飞行高度不超过一定范围，更安全． 初始化和进 化过程中的航迹点都限定在此范围之内． 1. 2 无人机物理约束 无人机的物理约束主要考虑无人机的最大拐弯 角 α、最大爬升/下滑角 β、最小直飞距离约束 lmin以 及探测范围 R． 如果违反了这些约束，则规划出来 的航迹无人机无法执行． 对于无人机物理约束，本 文引入了惩罚函数［7］，惩罚函数值的大小反映了所 规划航迹对约束的违背程度，惩罚函数值越小，航迹 质量越高． 各物理约束的惩罚函数分别如下: fh_angle = 0， α≤αmax ; {Kh， α ＞ αmax ． ( 2) fv_angle = 0， β≤βmax ; {Kv， β ＞ βmax. ( 3) fl_min = Kl， l≤lmin ; 0， l ＞ l { min. ( 4) fr_detect = 0， r≤R; {Kr， r ＞ R． ( 5) 式中，Kh、Kv、Kl 和 Kr 分别为最大拐弯角、最大爬 升/下滑角、最小直飞距离约束以及探测范围的惩罚 系数． 将各惩罚函数综合考虑，得到无人机物理约束 惩罚代价函数表示如下: fphysical = fh_angle + fv_angle + fl_min + fr_detect ． ( 6) 若惩罚函数值为 0，说明所规划航迹没有违反 物理约束，航迹是可飞的． 1. 3 航迹性能指标约束 航迹性能指标约束主要指航程、高程和威胁约 束，航程、高程和威胁指标是衡量低空突防轨迹优劣 ·97·
·98 北京科技大学学报 第34卷 的三项重要指标.航程约束要求规划出来的航迹长 机初始化种群X={x,x,…,x心}，N,为种群规 度越短越好，因为航程越长，飞行时间增长从而加大 模，个体X={x1,x2,,x}用于表征问题解，D 被敌方雷达发现的概率，在线航迹规划是分段规划 为优化问题的维数.算法的基本思想是：对当前种 的，这里采用规划片段距离目标点的远近程度作为 群进行变异和交叉操作，产生另一个新种群：然后利 衡量指标.高程约束要求无人机在避免碰撞的情况 用选择操作对这两个种群进行一对一的选择，从而 下飞行高度越低越好，因为飞行高度越低隐蔽性越 产生最终的新一代种群.具体而言，首先通过对每 好，不容易被敌方发现.同理，威胁约束要求无人机 一个在第1代的个体x:实施变异操作，得到与其相 飞行过程中避开敌方雷达探测区域，减小无人机被 对应的变异个体，如下式所示： 击毁概率.描述航程、高程和威胁约束的函数分别 =+F(2-） (11) 如下式所示： 式中：T1,2,3∈{1,2，…，N}互不相同并且与i不 N-1 f= 1-xc)+G1-y。)'+(+1-e 同；x,为父代基向量；x,-x,为父代差分向量：F为 √(x-xc)2+(y:-yc)2+(a-e) 缩放比例因子.然后，利用下式对x由式(11)生成 (7) 的变异个体实施交叉操作，生成试验个体，即 Thk -Hninl (8) = ,if(and0)≤CR）orj=ja(12) N NT 「K/T,T<R； (9) x否则 10, T防≥Rg 式中，rand()为D,1]之间的均匀分布随机数：CR 式中，N为所规划航迹片段的航迹节点个数，N为总 为范围在D,1]之间的交叉概率j为{1,2，…，D} 的威胁雷达个数，G为目标点，：为第k个航迹点的 之间的随机量.利用下式对试验个体+1和x的 离地高度，，为航迹片段的第i个节点与第j个威胁 目标函数进行比较.对于最小化问题，则选择目标 雷达的距离，R,为威胁半径，K为常系数 函数值低的个体作为新种群中的个体x+,即 对于可飞的航迹，将航程、高程和威胁代价综合 ,iff(u）)<f(x): 考虑，构成无人机航路规划的代价函数，无人机航迹 x= (13) x, 否则 的代价方程如下式所示： 式中，f()为目标函数，上述过程是标准DE,表示为 Fpedocmance=ww3 (10) DE/rand/1/bin. 式中，W1、02和心为各项的权值.规划后代价函数最 小的航迹，将是得到的最优航迹 2.2改进差分进化算法 2.2.1冯·诺伊曼拓扑 2 基于改进差分进化算法的无人机在线航 冯·诺伊曼拓扑结构如图1所示，种群中的所有 迹规划 个体都被放在规模为M×M的二维网格上，每 差分进化算法是一种基于群体进化的算法，具 个个体占一个格点位置并且不能移动，每个个体只 有记忆个体最优解和种群内信息共享的特点，通过 能与其周围（上方，下方，左方，右方）的四个邻居个 种群内个体间的合作与竞争来实现对优化问题的求 体发生相互作用，它们构成了进化子种群.在多目 解，其本质是一种基于实数编码的具有保优思想的 标优化问题中，一个个体表示目标函数的一个解，在 贪婪遗传算法网 本文中就是代表无人机在线规划的航迹片段. 2.1标准差分进化算法一DE/rand/1/bin 差分进化算法包括三个进化操作算子：变异、交 叉和选择.差分策略可以概括表示为DEx/y/z.x 为扰动中心向量，它既可以是种群中的随机(rand) 向量，也可以是当前种群中的最优(best)向量，还可 以是当前(current)个体；y为差分向量的个数；z为 交叉的模式回.DE/rand/1/bin是目前使用最广的 差分策略. 图1冯·诺伊曼拓扑网格 标准差分进化算法首先在问题的可行解空间随 Fig.1 Von Neumann topology
北 京 科 技 大 学 学 报 第 34 卷 的三项重要指标． 航程约束要求规划出来的航迹长 度越短越好，因为航程越长，飞行时间增长从而加大 被敌方雷达发现的概率，在线航迹规划是分段规划 的，这里采用规划片段距离目标点的远近程度作为 衡量指标． 高程约束要求无人机在避免碰撞的情况 下飞行高度越低越好，因为飞行高度越低隐蔽性越 好，不容易被敌方发现． 同理，威胁约束要求无人机 飞行过程中避开敌方雷达探测区域，减小无人机被 击毁概率． 描述航程、高程和威胁约束的函数分别 如下式所示: fL = ∑ N－1 i =1 ( xi +1 － xG) 2 + ( yi +1 － yG) 2 + ( zi +1 － zG 槡 ) 2 ( xi － xG) 2 + ( yi － yG) 2 + ( zi － zG 槡 ) 2 ， ( 7) fH = ∑ N k = 1 | hk － Hmin | Hmin ， ( 8) fT = ∑ N i = 1 ∑ NT j = 1 fT，ij ， fT，ij = Kj /r 4 ij ， rij ＜ Rtj ; 0， r { ij≥Rtj ． ( 9) 式中，N 为所规划航迹片段的航迹节点个数，NT为总 的威胁雷达个数，G 为目标点，hk为第 k 个航迹点的 离地高度，rij为航迹片段的第 i 个节点与第 j 个威胁 雷达的距离，Rtj为威胁半径，Kj为常系数． 对于可飞的航迹，将航程、高程和威胁代价综合 考虑，构成无人机航路规划的代价函数，无人机航迹 的代价方程如下式所示: fperformance = w1 ·fL + w2 ·fH + w3 ·fT ． ( 10) 式中，w1、w2和 w3为各项的权值． 规划后代价函数最 小的航迹，将是得到的最优航迹． 2 基于改进差分进化算法的无人机在线航 迹规划 差分进化算法是一种基于群体进化的算法，具 有记忆个体最优解和种群内信息共享的特点，通过 种群内个体间的合作与竞争来实现对优化问题的求 解，其本质是一种基于实数编码的具有保优思想的 贪婪遗传算法［8］． 2. 1 标准差分进化算法———DE/rand /1 /bin 差分进化算法包括三个进化操作算子: 变异、交 叉和选择． 差分策略可以概括表示为 DE /x /y /z． x 为扰动中心向量，它既可以是种群中的随机( rand) 向量，也可以是当前种群中的最优( best) 向量，还可 以是当前( current) 个体; y 为差分向量的个数; z 为 交叉的模式［9］． DE /rand /1 /bin 是目前使用最广的 差分策略． 标准差分进化算法首先在问题的可行解空间随 机初始化种群 X0 = { x0 1，x0 2，…，x0 NP } ，NP 为种群规 模，个体 X0 i = { x 0 i，1，x 0 i，2，…，x 0 i，D } 用于表征问题解，D 为优化问题的维数． 算法的基本思想是: 对当前种 群进行变异和交叉操作，产生另一个新种群; 然后利 用选择操作对这两个种群进行一对一的选择，从而 产生最终的新一代种群． 具体而言，首先通过对每 一个在第 t 代的个体 xt i 实施变异操作，得到与其相 对应的变异个体 v t i，如下式所示: vt i = xt r1 + F( xt r2 － xt r3 ) ． ( 11) 式中: r1，r2，r3∈{ 1，2，…，NP } 互不相同并且与 i 不 同; xt r1为父代基向量; xt r2 － xt r3为父代差分向量; F 为 缩放比例因子． 然后，利用下式对 xt i 由式( 11) 生成 的变异个体 vt i 实施交叉操作，生成试验个体 ut i，即 ut i，j = v t i，j ， if ( rand( j) ≤CR) or j = jrand ; xt { i，j ， 否则 . ( 12) 式中，rand( j) 为［0，1］之间的均匀分布随机数; CR 为范围在［0，1］之间的交叉概率; jrand为{ 1，2，…，D} 之间的随机量． 利用下式对试验个体 ut + 1 i 和 xt i 的 目标函数进行比较． 对于最小化问题，则选择目标 函数值低的个体作为新种群中的个体 xt + 1 i ，即 xt + 1 i = ut i， if f( ut i ) ＜ f( xt i ) ; xt { i， 否则 . ( 13) 式中，f( ) 为目标函数，上述过程是标准 DE，表示为 DE /rand /1 /bin． 2. 2 改进差分进化算法 2. 2. 1 冯·诺伊曼拓扑 冯·诺伊曼拓扑结构如图1所示，种群中的所有 个体都被放在规模为 Msize × Msize的二维网格上，每 个个体占一个格点位置并且不能移动，每个个体只 能与其周围( 上方，下方，左方，右方) 的四个邻居个 体发生相互作用，它们构成了进化子种群． 在多目 标优化问题中，一个个体表示目标函数的一个解，在 本文中就是代表无人机在线规划的航迹片段． 图 1 冯·诺伊曼拓扑网格 Fig． 1 Von Neumann topology ·98·
第1期 彭志红等：基于改进差分进化算法的无人机在线低空突防航迹规划 ·99· 根据图1，将位置在(i,j)的个体表示为Mg,则 和x之间的位置.由此可以得到改进后的变异操 M的邻域为Ng,Ng={MM,M2,Mn},其中 作算子为 i-1,i≠1： j-1,j≠1： 片=ax+(1-a）xims+ i={M,i=1.i={M,j-l. [F+(F-Fa)7]x-x)+ i+l,i≠Me; i+1,j≠Mc: i=M; h={, [F-(F-F) (17) (14) 或 在冯·诺伊曼拓扑结构中，每个个体在进行差分 y片=ax+(1-a）·xam+ 进化操作时，只能随机选择邻居作为基向量和差分 向量，多个子种群同时进化，这样可以有效保持种群 [F+(F-F)·7]小xam-)+ 的多样性，避免算法陷入局部最优.在本文中，种群 进化初期，采用传统的冯·诺伊曼拓扑结构，在进化 [rm-(F-F)·7]。-).(I8) 后期，为了加快算法的收敛性，快速得到最优解，在 2.3编码和初始化 种群进化过程中引入全局最优解，参与子种群的 本文航迹表示采用三维航迹点列表{S,P,P2, 进化 ·,E},列表中S为在线规划航迹片段起始点，E为 2.2.2改进变异操作算子 规划航迹片段终止点，P1,P2,…,P、1为航迹途经 为了提高标准差分进化算法的效率，一些学者 点.每个航迹点由三个坐标点表示，不同的编码方 提出了新的变异操作算子模型，如DE/best/1/bin、 式其意义不同.在航迹片段初始化时采用相对极坐 DE/current-to-best/1/bin,DE/rand-to-best/1/bin, 标，利用其对路径点位置和方位的限制，显著减少搜 不同模式侧重点不同，有的有利于保持群体多样性， 索空间：在变异和交叉操作阶段，使用绝对笛卡儿坐 有的更强调算法的收敛速度.文献0]中提出了一 标，只引起局部改变，克服相对极坐标会引起全局改 种改进变异操作算子，结合了不同策略的优点，如下 变的缺陷.如图2所示，在相对极坐标系下，航迹点 式所示： 用(r,0,z)表示.其中，r为水平投影面中相邻两航 v=ax+(1-a）best+F,·(xim-x）+ 迹点间的距离，0为水平投影面中当前规划航迹点 F2(xn-x). (15) 相对于前一航迹点的变化角，：为当前规划航迹点 通过调整上式的参数可以得到不同的策略模 的高度值.在绝对坐标系下，航迹点用(x,y,z)表 型.若a=1,F,=0,则等价于DE/rand1/bin;若 示，xy和z分别表示航迹点在x轴y轴和z轴的坐 a=0,F,=0,则等价于DE/best/1/bin;若a=0, 标值（图2中z未标出）. F,≠0，则等价于DE/rand-to-best/1bin.在这里，将 此模型做一些改变，根据采用的冯·诺伊曼拓扑结 构，进化初期使用邻域最优解xm代替xa,这里 的，m为冯·诺伊曼拓扑网格中个体M,及其邻域 所构成小种群的局部最优解，进化后期使用整个种 群的全局最优解xa代替x·缩放因子F控制着 差分向量的幅度，较大的F,值可以使解收敛速度较 P: 快，但容易陷入局部最优：较大的F,可以使解在更 图2绝对笛卡儿坐标和相对极坐标下的无人机航迹点 大范围内搜索但收敛速度较慢.为了实现两者之间 Fig.2 UAV path points in absolute Cartesian and relative polar coor- 的折衷，本文设定 dinates [F=Fin+(F-Fai)T 在本文中，因为地形预先未知，故每次规划必须 (16) 在无人机的扫描半径内.为了提高规划效率，设定 F2=F-(Fs-Fa）7 扫描点为规划起点，初始化时规划终点落在扫描半 式中，(Fn,F)为F,和F2的取值范围，T为进化 径R上，中间的航迹点可以根据规划精度在空间内 总代数.式(15)中的参数a决定了基向量介于x, 均匀分布
第 1 期 彭志红等: 基于改进差分进化算法的无人机在线低空突防航迹规划 根据图 1，将位置在( i，j) 的个体表示为 Mij ，则 Mij的邻域为 Nij ，Nij = { Mi1，j ，Mi，j 1 ，Mi2，j ，Mi，j 2 } ，其中 i1 = i － 1， i≠1; {Msize， i = 1． j1 = j － 1， j≠1; {Msize， j = 1． i2 = i + 1， i≠Msize ; {1， i = Msize ; j2 = j + 1， j≠Msize ; {1， j = Msize ． ( 14) 在冯·诺伊曼拓扑结构中，每个个体在进行差分 进化操作时，只能随机选择邻居作为基向量和差分 向量，多个子种群同时进化，这样可以有效保持种群 的多样性，避免算法陷入局部最优． 在本文中，种群 进化初期，采用传统的冯·诺伊曼拓扑结构，在进化 后期，为了加快算法的收敛性，快速得到最优解，在 种群进化过程中引入全局最优解，参与子种群的 进化． 2. 2. 2 改进变异操作算子 为了提高标准差分进化算法的效率，一些学者 提出了新的变异操作算子模型，如 DE /best /1 /bin、 DE /current-to-best /1 /bin、DE /rand-to-best /1 /bin ［9］， 不同模式侧重点不同，有的有利于保持群体多样性， 有的更强调算法的收敛速度． 文献［10］中提出了一 种改进变异操作算子，结合了不同策略的优点，如下 式所示: vt i = a·xt r1 + ( 1 － a)·xt best + F1 ·( xt best － xt r1 ) + F2 ·( xt r2 － xt r3 ) ． ( 15) 通过调整上式的参数可以得到不同的策略模 型． 若 a = 1，F1 = 0，则等价于 DE /rand /1 /bin; 若 a = 0，F1 = 0，则 等 价 于 DE /best /1 /bin; 若 a = 0， F1≠0，则等价于 DE /rand-to-best /1 /bin． 在这里，将 此模型做一些改变，根据采用的冯·诺伊曼拓扑结 构，进化初期使用邻域最优解 xt i，jmax代替 xt best，这里 的 xt i，jmax为冯·诺伊曼拓扑网格中个体 Mij及其邻域 所构成小种群的局部最优解，进化后期使用整个种 群的全局最优解 xt gbest代替 xt best ． 缩放因子 F 控制着 差分向量的幅度，较大的 F1值可以使解收敛速度较 快，但容易陷入局部最优; 较大的 F2可以使解在更 大范围内搜索但收敛速度较慢． 为了实现两者之间 的折衷，本文设定 F1 = Fmin + ( Fmax － Fmin )·t T ， F2 = Fmax － ( Fmax － Fmin )·t T { ． ( 16) 式中，( Fmin，Fmax ) 为 F1和 F2的取值范围，T 为进化 总代数． 式( 15) 中的参数 a 决定了基向量介于 xt r1 和 xt best之间的位置． 由此可以得到改进后的变异操 作算子为 vt i = a·xt r1 + ( 1 － a)·xt i，jmax [ + Fmin + ( Fmax － Fmin )·t ] T ·( xt i，jmax － xt r1 ) [ + Fmax － ( Fmax － Fmin )·t ] T ·( xt r2 － xt r3 ) ( 17) 或 vt i = a·xt r1 + ( 1 － a)·xt gbest [ + Fmin + ( Fmax － Fmin )·t ] T ·( xt gbest － xt r1 ) [ + Fmax － ( Fmax － Fmin )·t ] T ·( xt r2 － xt r3 ) . ( 18) 2. 3 编码和初始化 本文航迹表示采用三维航迹点列表{ S，P1，P2， …，E} ，列表中 S 为在线规划航迹片段起始点，E 为 规划航迹片段终止点，P1，P2，…，PN － 1 为航迹途经 点． 每个航迹点由三个坐标点表示，不同的编码方 式其意义不同． 在航迹片段初始化时采用相对极坐 标，利用其对路径点位置和方位的限制，显著减少搜 索空间; 在变异和交叉操作阶段，使用绝对笛卡儿坐 标，只引起局部改变，克服相对极坐标会引起全局改 变的缺陷． 如图 2 所示，在相对极坐标系下，航迹点 用( r，θ，z) 表示． 其中，r 为水平投影面中相邻两航 迹点间的距离，θ 为水平投影面中当前规划航迹点 相对于前一航迹点的变化角，z 为当前规划航迹点 的高度值． 在绝对坐标系下，航迹点用( x，y，z) 表 示，x、y 和 z 分别表示航迹点在 x 轴、y 轴和 z 轴的坐 标值( 图 2 中 z 未标出) ． 图 2 绝对笛卡儿坐标和相对极坐标下的无人机航迹点 Fig． 2 UAV path points in absolute Cartesian and relative polar coordinates 在本文中，因为地形预先未知，故每次规划必须 在无人机的扫描半径内． 为了提高规划效率，设定 扫描点为规划起点，初始化时规划终点落在扫描半 径 R 上，中间的航迹点可以根据规划精度在空间内 均匀分布． ·99·
·100 北京科技大学学报 第34卷 2.4算法流程 表1航迹规划仿真参数设置 基于改进差分进化算法的无人机在线航迹规划 Table 1 Simulation parameters and their values for path planning 流程具体如下 参数 数值 Step1初始化规模为Me×M.i的冯·诺伊曼 最大拐弯角/（°） 60 拓扑网格M,t-1,i1,j1. 最大爬升下滑角/() 30° Step2如果t<T/2,计算M的邻域最优值 最小/最大离地高度/m 100/300 x,mr,对个体M,按照式(17)执行改进变异操作算 探测半径，R/km 公 子，得到：如果t≥T/2,按照式(18)执行改进变异 种群数目 64 操作算子 最大迭代次数 100 Step3对t和M执行交叉算子，得到g 智能体网格规模，M 8 收缩因子 Step4比较g和M的代价函数值，如果 Fln:0.4Fma 1 标准收缩因子，F 0.3 f(u)<f(M),将赋给M. 交叉概率，CR 0.5 Step5对M上其他的个体依次进行改进差 分进化操作，直到所有个体都参与进化，得到第1代 的全局最优解xt Step6如果t=T,则输出xem;否则，令t-t+ s1.0 l,转Step2. 0.5 Step7将xte作为当前航迹段的规划输出. 50 30 40 Step8如果满足终止条件，则退出；否则继续 .20 10 00 102030 x/km 规划下一个航迹段，转Step1. 图3三维地形及在线规划航迹图 3仿真和分析 Fig.3 3D terrain map and online path displays 改进差分进化算法用于无人机在线航迹规划的 效回避了威胁区域；规划航迹实现了低空突防地形 仿真实验是在Intel(R)2.93GHz的PC机上进行， 跟随和地形回避，航程也符合要求：每次扫描规划能 操作系统为Windows XP,编程仿真软件为VC++ 够在3s内完成，满足实时性要求，路径达到了安全 6.0,应用Matlab R2009a进行结果图形显示. 可飞且代价最小的目标要求. 假定数字地图规模为50km×50km,无人机起 为了测试本文提出的改进差分进化算法的有 始点的坐标为(0,0，Ma即(0,0))，目标点的坐标为 效性，采用了两种比较算法，一是标准的差分进化 (50,50,Map(50,50)),其中Map（)是指地形高 算法，即DE/rand/1bin差分策略，二是仅采用了 度.其他规划参数如表1所示.使用提出的改进差 文中提出的改进变异操作算子的差分进化算法 分进化算法进行无人机在线航迹规划结果如图3、 前者的目的是和改进后的算法作比较，后者的目 图4所示. 的是验证采用冯·诺伊曼拓扑结构是否能达到保 从图3和图4中可以看出：使用改进差分进化 持种群多样性，避免算法陷入局部最优.图5(a) 算法规划的航迹完全满足无人机机动性能要求，有 和(b)分别是使用两种比较算法的规划结果三维 50r (a) 06 12 航迹高程 40 1.0 一地形高程 0.8 30 0.6 04 02 10 30 0 15 0 x/km 航迹点号 图4三维航迹水平投影(a)、纵剖面图(b) Fig.4 3D horizontal projection (a)and vertical projection (b)of path planning results
北 京 科 技 大 学 学 报 第 34 卷 2. 4 算法流程 基于改进差分进化算法的无人机在线航迹规划 流程具体如下． Step 1 初始化规模为 Msize × Msize的冯·诺伊曼 拓扑网格 Mt ，t←1，i←1，j←1． Step 2 如果 t ＜ T /2，计算 Mt ij 的邻域最优值 xt i，jmax，对个体 Mt ij按照式( 17) 执行改进变异操作算 子，得到 v t ij ; 如果 t≥T /2，按照式( 18) 执行改进变异 操作算子． Step 3 对 v t ij和 Mt ij执行交叉算子，得到 ut ij ． Step 4 比 较 ut ij 和 Mt ij 的 代 价 函 数 值，如 果 f( ut ij ) ＜ f( Mt ij ) ，将 ut ij赋给 Mt + 1 ij ． Step 5 对 Mt 上其他的个体依次进行改进差 分进化操作，直到所有个体都参与进化，得到第 t 代 的全局最优解 xt gbest ． Step 6 如果 t = T，则输出 xt gbest ; 否则，令 t←t + 1，转 Step 2． Step 7 将 xt gbest作为当前航迹段的规划输出． Step 8 如果满足终止条件，则退出; 否则继续 规划下一个航迹段，转 Step 1． 图 4 三维航迹水平投影( a) 、纵剖面图( b) Fig． 4 3D horizontal projection ( a) and vertical projection ( b) of path planning results 3 仿真和分析 改进差分进化算法用于无人机在线航迹规划的 仿真实验是在 Intel( R) 2. 93 GHz 的 PC 机上进行， 操作系统为 Windows XP，编程仿真软件为 VC + + 6. 0，应用 Matlab R2009a 进行结果图形显示． 假定数字地图规模为 50 km × 50 km，无人机起 始点的坐标为( 0，0，Map( 0，0) ) ，目标点的坐标为 ( 50，50，Map( 50，50) ) ，其中 Map( ) 是指地形高 度． 其他规划参数如表 1 所示． 使用提出的改进差 分进化算法进行无人机在线航迹规划结果如图 3、 图 4 所示． 从图 3 和图 4 中可以看出: 使用改进差分进化 算法规划的航迹完全满足无人机机动性能要求，有 表 1 航迹规划仿真参数设置 Table 1 Simulation parameters and their values for path planning 参数 数值 最大拐弯角/( °) 60 最大爬升/下滑角/( °) 30° 最小/最大离地高度/m 100 /300 探测半径，R /km 10 种群数目 64 最大迭代次数 100 智能体网格规模，Msize 8 收缩因子 Fmin ∶ 0. 4Fmax ∶ 1 标准收缩因子，F 0. 3 交叉概率，CR 0. 5 图 3 三维地形及在线规划航迹图 Fig． 3 3D terrain map and online path displays 效回避了威胁区域; 规划航迹实现了低空突防地形 跟随和地形回避，航程也符合要求; 每次扫描规划能 够在 3 s 内完成，满足实时性要求，路径达到了安全 可飞且代价最小的目标要求． 为了测试本文提出的改进差分进化算法的有 效性，采用了两种比较算法，一是标准的差分进化 算法，即 DE /rand /1 /bin 差分策略，二是仅采用了 文中提出的改进变异操作算子的差分进化算法． 前者的目的是和改进后的算法作比较，后者的目 的是验证采用冯·诺伊曼拓扑结构是否能达到保 持种群多样性，避免算法陷入局部最优． 图 5 ( a) 和( b) 分别是使用两种比较算法的规划结果三维 ·100·
第1期 彭志红等：基于改进差分进化算法的无人机在线低空突防航迹规划 ·101· 地形图和等高线图，而表2是三种方法的平均代 效果好于标准差分进化算法，但两者效果差于同 价函数值f对比图.可以看出，在相同的条件 时采用冯·诺伊曼拓扑结构和改进变异操作算子 下，使用改进变异操作算子的差分进化算法规划 的改进差分进化算法 +改进变异算子差分进化 50 +标准差分进化 (a) 0 1.5 s1.0 0.5 00 30 10 40 改进变异 20 30 分化 10 10 20 际准麦分化 00 /km 10 20 30 40 50 x/km 图5两种比较算法在线规划三维航迹图(a)和等高线图(b) Fig.5 3D online route displays (a)and horizontal projections (b)of planning results using two comparison algorithms 表2三种算法的平均代价函数值比较 ning.Flight Dyn,1998,16(4):14 Table 2 Comparison of average cost function values for three algorithms (闵昌万，袁建平.军用飞行器航迹规划综述飞行力学， mcas feea fmean 1998,16(4):14) 三种差分进化算法 (T=40)(T=60)(T=100) 2] Storn R,Price K.Differential evolution:a simple and efficient 改进DE 6.812 5.377 4.932 heuristic for global optimization over continuous space.Clobal 采用改进差分变异算子DE7.922 6.824 5.129 0ptim,1997,11(4):341 标准DE/and/I/bin 9.641 8.243 7.688 B]loannis K N,Athina N B.Coordinated UAV path planning using differential evolution Proceedings of the 13th Mediterranean 4结论 Conference on Control and Automation.Limassol,2005:549 4 Chen J,Xin B,Peng Z H,et al.Evolutionary decision-makings (1)提出了一种改进差分进化算法用于三维部 for the dynamic weapon-arget assignment problem.Sci China Ser 分未知环境下无人机在线低空突防航迹规划，该算 F,2009,52(11):2006 法在继承了传统标准差分进化算法原理简单、鲁棒 1 Kennedy J,Mendes R.Population structure and particle swarm 性强等优点的基础上，针对其容易陷入局部最优，后 performance Proceedings of the World Congress on Computation- al Intelligence.Honolulu,2002:1671 期收敛速度慢的缺陷，提出了采用冯·诺伊曼拓扑和 国 Besada-Portas E,de la Torre L,de la Cruz J M,et al.Evolution- 改进差分进化变异操作相结合的方式，并对冯·诺伊 ary trajectory planner for multiple UAVs in realistic scenarios 曼拓扑作了扩展. IEEE Trans Rob,2010,26(4):619 (2)在规划过程中，采用了相对极坐标编码方 ] Wang G S,Li Q,Guo L J.Multiple UAVs routes planning based 式进行初始化，既大大缩小了算法搜索空间，又避免 on particle swarm optimization algorithm//The 2nd International Symposium on Information Engineering and Electronic Commerce 了规划范围超出机载雷达探测范围.在进行差分进 (EEC2010).Wuhan,2010:1 化变异、交叉操作时，采用绝对笛卡儿坐标编码方 8] Liu B,Wang L,Jin Y H.Advances in differential evolution. 式，避免了改变相对极坐标会引起全局变化的问题. Control Decis,2007,22(7):721 (3)仿真结果表明，改进差分进化算法具有良 (刘波，王凌，金以慧.差分进化算法研究进展.控制与决策， 好的全局搜索能力，有效克服了传统算法容易陷入 2007,22(7):721) 9] Price K V,Storn R M,Lampinen J A.Differential Erolution:A 局部最优及收敛速度慢的问题，能够在短时间内得 Practical Approach to Global Optimization.Berlin:Springer,2005 到满足各种约束条件的低空突防航迹.而且，该算 [10]Xia H M,Zhou Y Q.Improved differential evolution strategy op- 法移植性好，工程实用性强 timization algorithm for multiple hump functions.Comput Eng 4ppl,2009,45(32):41 参考文献 (夏慧明，周永权.改进差分进化策略在多峰值函数优化中 Min C W,Yuan J P.Introduction of military aircraft route plan- 的应用.计算机工程与应用，2009,45(32)：41)
第 1 期 彭志红等: 基于改进差分进化算法的无人机在线低空突防航迹规划 地形图和等高线图，而表 2 是三种方法的平均代 价函数 值 fmean 对 比 图． 可 以 看 出，在 相 同 的 条 件 下，使用改进变异操作算子的差分进化算法规划 效果好于标准差分进化算法，但两者效果差于同 时采用冯·诺伊曼拓扑结构和改进变异操作算子 的改进差分进化算法． 图 5 两种比较算法在线规划三维航迹图( a) 和等高线图( b) Fig． 5 3D online route displays ( a) and horizontal projections ( b) of planning results using two comparison algorithms 表 2 三种算法的平均代价函数值比较 Table 2 Comparison of average cost function values for three algorithms 三种差分进化算法 fmean ( T = 40) fmean ( T = 60) fmean ( T = 100) 改进 DE 6. 812 5. 377 4. 932 采用改进差分变异算子 DE 7. 922 6. 824 5. 129 标准 DE /rand /1 /bin 9. 641 8. 243 7. 688 4 结论 ( 1) 提出了一种改进差分进化算法用于三维部 分未知环境下无人机在线低空突防航迹规划，该算 法在继承了传统标准差分进化算法原理简单、鲁棒 性强等优点的基础上，针对其容易陷入局部最优，后 期收敛速度慢的缺陷，提出了采用冯·诺伊曼拓扑和 改进差分进化变异操作相结合的方式，并对冯·诺伊 曼拓扑作了扩展． ( 2) 在规划过程中，采用了相对极坐标编码方 式进行初始化，既大大缩小了算法搜索空间，又避免 了规划范围超出机载雷达探测范围． 在进行差分进 化变异、交叉操作时，采用绝对笛卡儿坐标编码方 式，避免了改变相对极坐标会引起全局变化的问题． ( 3) 仿真结果表明，改进差分进化算法具有良 好的全局搜索能力，有效克服了传统算法容易陷入 局部最优及收敛速度慢的问题，能够在短时间内得 到满足各种约束条件的低空突防航迹． 而且，该算 法移植性好，工程实用性强． 参 考 文 献 ［1］ Min C W，Yuan J P． Introduction of military aircraft route planning． Flight Dyn，1998，16( 4) : 14 ( 闵昌万，袁 建 平． 军用飞行器航迹规划综述． 飞 行 力 学， 1998，16( 4) : 14) ［2］ Storn R，Price K． Differential evolution: a simple and efficient heuristic for global optimization over continuous space． J Global Optim，1997，11( 4) : 341 ［3］ Ioannis K N，Athina N B． Coordinated UAV path planning using differential evolution / / Proceedings of the 13th Mediterranean Conference on Control and Automation． Limassol，2005: 549 ［4］ Chen J，Xin B，Peng Z H，et al． Evolutionary decision-makings for the dynamic weapon-target assignment problem． Sci China Ser F，2009，52( 11) : 2006 ［5］ Kennedy J，Mendes R． Population structure and particle swarm performance / / Proceedings of the World Congress on Computational Intelligence． Honolulu，2002: 1671 ［6］ Besada-Portas E，de la Torre L，de la Cruz J M，et al． Evolutionary trajectory planner for multiple UAVs in realistic scenarios． IEEE Trans Rob，2010，26( 4) : 619 ［7］ Wang G S，Li Q，Guo L J． Multiple UAVs routes planning based on particle swarm optimization algorithm / / The 2nd International Symposium on Information Engineering and Electronic Commerce ( IEEC2010) ． Wuhan，2010: 1 ［8］ Liu B，Wang L，Jin Y H． Advances in differential evolution． Control Decis，2007，22( 7) : 721 ( 刘波，王凌，金以慧． 差分进化算法研究进展． 控制与决策， 2007，22( 7) : 721) ［9］ Price K V，Storn R M，Lampinen J A． Differential Evolution: A Practical Approach to Global Optimization． Berlin: Springer，2005 ［10］ Xia H M，Zhou Y Q． Improved differential evolution strategy optimization algorithm for multiple hump functions． Comput Eng Appl，2009，45( 32) : 41 ( 夏慧明，周永权． 改进差分进化策略在多峰值函数优化中 的应用． 计算机工程与应用，2009，45( 32) : 41) ·101·