巡航导弹航路规划算法研究＊

肖 刘，陈红林，叶 健，李矛彤

（1西北工业大学电子信息学院，西安 710129；2海军驻安顺地区航空军事代表室，贵州安顺 561018；3总参陆航部驻西安地区军事代表室，西安 710061）

0 引言

巡航导弹航路规划是指在特定约束条件下，寻找导弹从初始点到目标点满足某种性能指标最优的运动轨迹，是提高巡航导弹低空突防能力的一个很重要的方法［1］。巡航导弹在进行低空突防飞行时，其很大程度上取决于其自身的突防能力，也就是最大限度的减小地空导弹、高炮、电磁脉冲等威胁单元和地形地物障碍对其自身造成伤害的能力，即威胁回避的能力（文中将对地形地物障碍的回避简化为威胁回避）。因此，如果事先通过搜集任务区域的情报知道敌方威胁的分布和作用范围，就可以采用有效的航路优化技术对从起始点到目标点的飞行航路进行规划，得到全局最优或次优的飞行航路。

在任务区域内进行航路优化是典型的大范围优化问题。动态规划算法可以得到问题的最优解，但具有维数爆炸特性。梯度法容易陷入局部最优解中。另有一些优化方法，如神经网络［2］等，存在收敛速度慢等问题。更为重要的是，这些算法得到的飞行航路，从起始点出发，不能保证有效收敛于目标点。而遗传算法（genetic algorithm）的优点是能够在最短的时间里找到次优解。基于遗传算法的优点，文中在大范围、多威胁区的二维空间里用改进的遗传算法解决受约束巡航导弹的航路规划问题。

1 遗传算法

在大范围、多威胁区环境下应用遗传算法解决航路规划问题，需要采用有效的编码方式和准确而计算快速的适应度函数，选择合理的遗传操作参数。

1.1 染色体编码

一般而言，航路点编码需要包含航路所有信息。假设巡航导弹是按直线从一个点到下一点飞行的，那么当巡航导弹在两个点之间飞行时每个染色体可能包含一个高度变量。当然其它的航路细节如速度、加速度限制也可以包含在染色体里面。文中将在二维空间里并假设速度恒定的情况下研究遗传算法，并采用直接对航路点位置（横纵坐标）进行编码。

个体编码采用对航路点直接编码的方法，x2I是航路点所在位置的横纵坐标二进制合成编码，（x1x2…xIxI＋1…x2I），其中I为航路点的数目，（x1，xI＋1）是第一个航路点，（x2，xI＋2）是第二个航路点，其它航路点以此类推。对于航路点横纵坐标染色体编码，若航路点个数较多，则二进制码的位数非常长，降低算法的进化效率。为了减小染色体长度，需要初步确定航路点个数。过多的航路点数量必然影响遗传进化的速度，合理的航路点个数应该使得进化过程的计算可以实现，同时不失去优良航路个体。文中依据威胁区数量确定节点个数，根据大量仿真实验可知，航路点个数I应该取N－2～N＋2之间［3］，其中N是威胁区个数。

1.2 初始种群

由于遗传算法的群体型操作的需求，必须为遗传操作准备一个由若干个初始个体组成的初始种群，种群中的个体都是通过随机方法在遗传空间内产生的。假定初始种群规模为NIND，使用随机数发生器产生［0 1］之间的均匀分布随机数，乘以相应基因幅值的限制值，形成初始种群。

1.3 适应度函数的求取

必须首先考虑航路的避开威胁区能力，在此基础上再做航路长度的比较，以确定航路个体的适应度函数。

航路的适应度函数按式（1）定义：

其中Pmissle＿arrival为巡航导弹最终到达目标的概率。式（1）用自然对数函数有利于增大具有较高到达目标概率航路之间适应度的区分度。如果用到达目标概率本身作为适应度，两个航路被遗传到下一代的概率将会几乎相同。通过利用自然对数函数，较优的航路被遗传到下一代的概率将会更高。而当到达目标概率降到10%以下时被遗传到下一代的概率将会近似呈线性下降。

影响到达目标概率的因素有巡航导弹的偶然失败、陷入已知威胁区的概率，以及巡航导弹由于违规不能按照航路飞行。把偶然失败简单描述为服从在10000km内失败的平均距离的泊松分布。

偶然失败概率函数为：

式中：λ是在每公里内偶然失败的概率，x是飞行的距离，n是偶然失败的次数。

此时如果巡航导弹到达目标，其偶然失败概率为式（2）在到达目标之前偶然失败次数n为0的概率。

其中失败率λ是失败的平均距离的倒数。文中λ设为10－4／km。

对于陷入已知威胁区的概率是这样处理的：如果巡航导弹各航路点连线不穿过威胁圆，就认为陷入已知威胁区的概率为0；反之如果航路点连线穿过威胁圆就认为陷入已知威胁区的概率为1，即巡航导弹到达目标概率为0。

在航路规划的过程中，如果对航路的长度不做约束，用遗传算法将很容易得到从初始点到目标的并且绕过所有预先探测的威胁区的一条最优航路。然而，实际中的巡航导弹只能携带有限的燃料，如果航路长度大于自身携带燃料所能到达的最大航程，那么巡航导弹到达目标概率可能将为0或者非常小。有必要对超过航路长度约束的航路进行处罚。式（4）为航路长度处罚概率函数：

ΔL＝Lroute－Lconstraint，以上航路长度单位都是km，Lroute为航路的总长度，Lconstraint为航路所允许的最大长度。

从式（4）可以看出：如果航路长度超过航路长度约束的幅度很小，航路长度处罚概率将几乎为0.5，而随着超过幅度的增大，航路长度处罚概率将趋于1，即如果规划的航路超过航路长度约束，航路长度处罚概率至少为0.5。如果规划的航路没有超过航路长度约束，将不处罚航路长度，即Lpenalty＝0。

巡航导弹到达目标概率将通过乘以1－Lpenalty而减小。

与航路长度处罚类似，在航路规划中也要对航路的转弯进行考虑，以满足巡航导弹的转弯半径性能指标要求。文中取了一个跟转弯半径相对应的参数变量——转弯弧度。如果航路在一航路点转弯弧度超过巡航导弹最大转弯弧度将要受到处罚。航路转弯弧度处罚概率函数为：

上式角度的单位为rad，Tangle为航路在航路点转弯的弧度，Tconstraint为航路转弯所允许的最大弧度。如果在某航路点航路转弯弧度在所允许范围之内，就不处罚，即Tpenalty＝0。巡航导弹到达目标的概率会通过乘以1－Tpenalty而减小。

为保证巡航导弹能够在最大过载范围内沿着航路正常转弯，要对航路点之间的最小距离即航路最小步长进行限制。如果航路在两航路点之间距离长度小于航路最小步长将要受到处罚。航路最小步长处罚概率函数为：

Sconstraint为航路最小步长，Slength为两航路点之间距离长度，R为巡航导弹的最小转弯半径。如果航路在两航路点之间距离长度大于航路最小步长，将不会受到处罚，即Spenalty＝0。巡航导弹到达目标的概率会通过乘以1－Spenalty而减小。

综上所述，巡航导弹到达目标概率为：

1.4 遗传算法的改进

基本遗传算法采用适应度比例选择、单点交叉和单点变异方法进行遗传操作，其主要不足是收敛速度慢、早熟收敛。为了克服这些缺点，文中在实际仿真过程中对基本遗传操作进行改进：

1）设置代沟GGAP，剔除一部分不合理的个体，加快收敛速度。

2）采用两点交叉的方式，增强算法的全局搜索能能力，防止陷入局部最优解之中。两点交叉是设置了两个交叉点，将两个交叉点之间的同组基因进行基因的交换。当染色体长n时，则可能有（n－2）＊（n－3）种交叉点的设置。

3）采用高斯算子的变异方式，让变异与适应度紧密相连，防止随机变异对适应度较优的个体造成损伤，按变异率选择某个个体并按下式变异（以k染色体为例）：

式中：gen′（i），gen（i）分别为子代和父代个体的第i位基因；Fmax、Fk分别为本代个体的最优适应度和第k代个体适应度。γi为均值为0、方差为1的高斯随机变量。

2 算法流程

1）根据编码，应用随机数函数随机产生初始种群的个体；

2）针对每个个体，形成相应的航路，并计算相应的个体适应度；

3）个体按照性能指标排序，并通过设置代沟剔除不良个体，复制优良个体；

4）种群内个体随机两两配对，按照交叉概率PC进行交叉操作，文中采用两点交叉操作；

5）计算个体的变异概率PM，进行变异操作，文中采用高斯算子变异方式操作；

6）终止条件判断，若不满足中终条件，则继续重复2）～5）的步骤；若满足终止条件，则输出最优或次优结果，作出航路规划图，算法结束。

3 仿真结果

航路的初始点和目标点坐标分别为（0，0），（30，30），单位都是km。航路点坐标为（Xi，Yi）（其中i＝1，2，…，I），I为所取航路点的数目。

使用参数：

巡航导弹最小转弯半径R＝0.6km；

群体规模NIND＝500；

最大遗传代数MAXGEN＝300；

代沟GGAP＝0.9；

交叉概率PC＝0.7；

变异概率PM＝0.7／Lind，其中Lind为染色体长度；

航路长度约束（最大航路长度）

Lconstraint＝50km；

航路转弯约束（最大转弯弧度）

Tconstraint＝π／3rad；

航路点个数I＝4。

文中取了4个威胁圆（x，y，r），x、y分别为其中心坐标，r为其作用半径。

威胁圆1：（3，5，1）为地形地物障碍威胁；

威胁圆2：（5，3，1）为高炮阵地威胁；

威胁圆3：（15，15，5）为电磁脉冲威胁；

威胁圆4：（25，25，3）为防空导弹阵地威胁。

文中在联想奔4台式机Windows XP sp3环境下利用Matlab R2008a实现上述算法，共花费时间为2min35s。

仿真结果如图1、图2所示。

图1 巡航导弹的航路图

图2 到达目标概率变化和到达目标概率均值的变化图

4 结论

文中将遗传算法理论应用到巡航导弹低空突防航路规划中，并在航路规划中对具有典型意义的巡航导弹在现在战争中可能遇到的四种威胁区进行了考虑。同时用改进后的遗传算法对其进行模拟仿真，从仿真结果图1来看文中的遗传算法还是有效可行的，从图2来看该算法是收敛的，同时也表明该算法可以解决大范围、多威胁区的巡航导弹低空突防航路规划问题。

［1］范洪达，马向玲，叶文.飞机低空突防航路规划技术［M］.北京：国防工业出版社，2007.

［2］阎平凡.人工神经网络与模拟进化计算［M］.北京：清华大学出版社，2000.

［3］冯琦，周德云.极坐标系下基于遗传算法的路径规划方法［J］.机械科学与技术，2004，23（5）：625－626.

［4］Matthew A Russell，Gary B Lamont.A genetic algorithm for unmanned aerial vehicle routing［C］／／Proceedings of the 2005Conference on Genetic and Evolutionary Computation，2005：1523－1530.

［5］J Latiurell，B Wallet，B Copeland.Genetic algorithm to solve constrained routing problem with applications for cruise missile routing［C］／／Proc SPIE 1998，vol.3390：490－500.