·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·