基于改进自适应遗传算法的特种飞机航线规划方法

刘家鹏，张雪松

(中国电子科学研究院,北京 100041)

0 引 言

信息时代战争中，依次关注制信息权、制天权、制空权、制海权。制空权也成为战斗中争夺的重要内容，没有制空权，就注定要失败[1]。在制空权的争夺中，决定战局的不仅仅是攻击利器，更重要的是能够及时发现敌人并采取行动。这催生了如预警机等具有预警探测和指挥控制功能的特种飞机。现代信息化条件下的战争核心是及时准确的获取各种情报。而在空战中，特别是对于地面预警探测系统难以企及的远程作战中，特种飞机将成为战场态势感知的主要信息源[2]。

特种飞机的飞行航线直接影响机载传感器的工作效果。在特种飞机航线规划的同时，需要考虑多种因素。不仅需要考虑云层、山峦等自然因素，还需要考虑雷达探测效果、通信覆盖率、无源侦察效果等情况。特种飞机使用中主要面临对各传感器规划不足，在航线规划中没有针对雷达、通信、无源侦察效果的考虑。

近些年来，主要的航线规划方法主要有蚁群算法[3]、Voronoi图法[4]、启发式A*算法[5]、粒子群算法[6]、遗传算法等。蚁群算法收敛速度慢，计算时间长，易于过早陷入局部最优；Voronoi图法中曲率约束的常微分方程求解过程很复杂，不易工程实现；A*算法要收敛到最优解需要很长的时间和较大的内存；粒子群算法具有搜索空间有限，但容易陷入局部最优。而自适应遗传算法能够自适应的修改遗传变异参数，全局搜索效果和局部搜索效果好，本文采用自适应遗传算法。

1 遗传算法及其应用情况

遗传算法提供了一种求解复杂系统优化问题的通用方法，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以遗传算法已有广泛的应用：函数优化、组合优化、生产调度问题、自动控制、图像处理和机器人学等[7]。本文将遗传算法应用于航线规划的研究。

遗传算法是一种借鉴生物界自然选择和自然遗传机制的全局搜索算法。它与传统的算法不同，大多数古典的优化算法是基于单一度量函数的梯度或较高次统计，以产生一个确定性的实验解序列。而遗传算法是一种全局搜索算法，它有效地解决了大空间搜索及全局优化。它不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解。其中，选择、交叉和变异构成了遗传算法的基本操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数这5个要素组成了遗传算法的核心内容。

2 航线规划问题建模

航线规划必须对飞行区域的环境信息和自身传感器的使用限制信息进行精确地了解。因此，合理、有效地针对环境威胁、机载传感器进行建模是航线规划成功的关键。

特种飞机在执行任务的过程中，其飞行的航线直接影响任务完成情况、自身安全、探测目标发现概率等。在航线规划过程中，需要考虑自身安全和传感器的使用，使其在保证安全的前提下，使特种飞机的探测能力最大化，各传感器充分发挥最大效能。

第一类问题，安全系数。

在航线规划所需考虑的诸多因素中，自身安全最为重要。首先特种飞机在使用时，飞行在我方控制空域，在整个飞行探测过程中与敌方的战斗机、防空区保持距离，同时与敌我分界线保持距离。所以特种飞机需要避开威胁空间主要包括自然威胁，包括山峦、云雨层、雷区等。从公开发表的文献[8]中可知，将各种威胁模型简化为具有一定规则的几何形状组合，有利于减少计算复杂度。

对自然威胁的建模分为两种情况，一是威胁区域，二是禁飞区,如图1、2所示。

图1 威胁区域 图2 禁飞区

威胁区域一般为山脉。山脉的威胁程度与距离有关，距离越近威胁程度越大。为计算航线段的威胁程度，引入Eij表示连接航线点i和j的航线片段，Lij表示航线片段Eij的长度。特种飞机所受到的威胁程度与航线在威胁区域的长短及与威胁中心的距离有关，

式中，(x,y)为威胁空间的中心点；(xk,yk)为进入威胁区域的点；N为进入威胁区域点的个数；a为系数。

而对于禁飞区，则是针对云层等恶劣天气区进行建模。可认为特种飞机在天气区内部所受到的威胁程度是相同的，即天气区对无人机的威胁服从均匀分布，因此采用均匀分布模型进行建模，其概率密度函数为

式中，Ji为禁飞区i的威胁程度；(a,b)、(c,d)为禁飞区对角线上的的两个顶点。

第二类问题，任务完成率。

优先级模型，特种飞机在航线规划过程中需要考虑多传感器的使用情况，实际是一个多目标优化问题。所以对于不同传感器模型，根据其重要程度对权重进行设定。首先特种飞机的安全系数最为重要，设为1级。

特种飞机最主要的功能是雷达探测，所以将雷达探测最大化，将其设计为2级。雷达有多种盲区，包括近距机翼遮挡盲区，固定角度盲区，顶空和机下盲区。考虑到特种飞机的安全、近距机翼遮挡盲区以，及顶空和机下问题，飞机航线规划在距离上需要距探测区域保持一定距离。由于某些特种飞机有一定角度的盲区，假设飞机机尾有盲区，所以最优航线侧向飞过探测区域，保证探测效果，而且需要提前进入探测区域一侧来尽可能减少机尾盲区的影响。航线规划同时考虑到这些盲区，使雷达发挥最大效果。

然后将通信设为3级，通信设备可能在敌方干扰或山脉遮挡无法与基地或部队实时联系。只要在任务过程中大部分时间能够与我方联系，某些短暂时刻不能达到实时通信，也可以完成任务，所以将其设为3级。最后考虑无源探测，探测敌方雷达位置，开机时长等，对任务影响最小，设为4级。

通信和无源侦察盲区会影响通信设备和无源侦察传感器的使用效果，降低任务完成率。其模型与自然威胁模型类似，采用圆形禁飞区域或方形禁飞区模型。这里的圆形禁飞区域模型与自然威胁区域不同，考虑通信设备和无源侦察设备在盲区中使用会受到影响，但与距离无关，所以采用禁飞区对无人机威胁服从均匀分布，概率分布为

对各个传感器的威胁程度进行归一化处理，对不同的威胁区域针对其重要程度设置不同的权重wi。总的惩罚函数为

wi根据优先级模型设定，将自然威胁w设为20，雷达探测w设为15，通信和无源侦察盲区w设为10。

3 算法改进描述

3.1 航线染色体编码

每一条航线由100个点组成，每个点的横坐标均匀分布，纵坐标采用二进制编码，随机生成的种群序列。这样的坐标实现方法基于两点考虑：(1)将问题转化为单值一维编码；(2)如果将横纵坐标都进行随机初始的话，每个点都有可能出现在坐标的任意位置，这样航线连续两点间距离会过大，不符合实际航线情况，同时也会造成搜索空间爆炸问题。

在此基础上再进行航线再编码，因为随机编码会产生初始航线起伏过大的问题，这样需要很多代的遗传变异才能生成较好的航线。所以需要对航线进行再编码，本文采用随机生成[-1,1]内随机数，然后从原点开始航线，每一点都在前一点的基础上随机生成。并在此基础上对每条航线进行平滑处理，以减少航线的振荡。这样将航线处理得更加平缓，同时更贴近真实航线，算法的效果也明显改进。

3.2 适应度函数

适应度函数以航线的飞行距离为基础，飞行距离决定飞机油耗等飞行成本，飞机在探测区域留空时间，所以总体选取飞行总距离小的航线。在此基础上增加惩罚因子，用与考虑威胁空间和各分系统的使用状况。

式中,N为航线中点的个数；n为航线进入威胁空间的总个数；wi为威胁空间i的权值；Ji为威胁空间i的威胁程度。

3.3 选择策略

选择策略为最小化问题，所以选择的原则是以大概率选择适应度函数值低的个体，以小概率选择适应度函数值大的个体，从而体现生物学上优胜劣汰的思想。

将所有航线代入适应度函数，得到适应度值排名，采用随机遍历抽样，适应度值小的子代以大概率遗传。

3.4 交叉算子和变异算子的自适应改进

为了克服传统遗传算法早熟问题和局部搜索能力差的问题，采用自适应技术。自适应遗传算法在种群进化初期，选取较大的交叉概率和变异概率，增加种群多样性，确保种群在大范围内搜索，增强全局搜索能力，避免早熟。在种群进化后期，接近最优解时，选取较小的交叉概率和变异概率，使种群在局部范围内进行搜索，增加局部搜索能力，同时增加收敛速度。

交叉算子采用多点交叉和单点交叉并用，由于多点交叉有利与种群多样化，但不利于最后算法的收敛。本文采用自适应技术，即在前50次进化的时候采用多点交叉，增加种群多样化，在后450次进化采用单点交叉，有利于算法快速收敛。改进后算法流程图如图3所示。

图3 改进算法的流程图

3.5 航线平滑处理

针对算法得出的最优航线，考虑飞机飞行转弯半径的限制进行平滑处理，航迹飞行转弯角度符合飞机特性，对转弯角度偏小的部分航线进行再处理，然后再针对整个航线进行平滑处理，保证航线能够正常飞行。

4 实验与分析

实验在配置为Intel Core i5 3.2 GHz处理器、4 GB RAM台式机上进行仿真，仿真环境为windows XP系统，Matlab 2010a平台。画出一个横坐标为[0,10]，纵坐标为[0，10]的坐标系，飞机从(0，6)点出发。在坐标系中画出数个威胁空间、敌我分界线以及探测空间。如图中小圈是无源侦察盲区，大圈是高山威胁，蓝色的方框是通信盲区。这三个区域都影响任务的正常执行，飞机不能飞入这些区域。带方块的直线为敌我分界线，节点为圆圈的方框为探测区域。

仿真结果如图4～图11所示。

图4 初始航线 图5 进化150代的航线 图6 算法效果图(终态)

图7 算法效果图(经过平滑后的航线) 图8 算法解的变化 图9 适应度值的变化与解的变化

图10 传统遗传算法初始航线 图11 传统最终航线

算法的个体数目N=50，最大遗传代数MAXGEN=500，变量个数(点的个数)NVAR=100，每个变量的二进制编码位数PRECI=20。每个图表示本次进化最优解的航线，即最短航路所对应的航线。

显示在进化初期(gen<50)，算法保持较大的变异概率Pm=0.01和较大的交叉概率Pc=0.7，选择多点交叉方式，航线进化时变化很大，有利于种群多样化。图8中所示在前50代的进化中，最优解的变化幅度很大，而且小于种群均值的变化，说明种群航线多样，有利于全局搜索适宜航线。进化后期采用单点交叉，和较小的变异概率Pm=0.000 35和较小的交叉概率Pc=0.5，有利与局部搜索，最优解与均值几乎重叠，在进化的过程中逐步优化航线。

图9中表示适应度值变化和解的均值变化，在前100代左右的进化中，二者相差很大，这是惩罚函数在起作用。种群在进化过程中，会有一些航线进入威胁区域，通过惩罚机制增大其适应度值，较小适应度值的种群有更大的概率保留下来。最终选择出不经过威胁区域而且有利于探测的的航线，达到我们对航线的要求。

图10、11标识传统遗传算法生成的初始航线和计算的最终航线，初始航线震荡幅度特别大，计算出的最优航线仍然有很大震荡，并会出现穿过威胁区域的情况，对比说明改进算法有一定优势。

5 结 语

针对特种飞机在预警探测过程中存在的自然威胁等飞行安全问题，探测区域覆盖率问题，机上设备使用限制等实际问题，提出了一种改进的自适应遗传算法。算法通过对初始种群编码的改进，以及交叉概率和变异概率的自适应计算。针对实际问题能够快速计算出特种飞机航线，并能有效的解决的传统遗传算法的早熟现象，不易收敛于局部最优解。

仿真结果表明，采用自适应遗传算法进行航线规划合理可行，能够在大范围内进行航线规划计算。改进的遗传算法不易收敛于局部最优，这在计算全局最优航线时效果明显。算法复杂度低、计算量少，适于工程实现。

[1] 朱里奥·杜黑.制空权.[M].北京:解放军出版社，1991.

[2] 刘波、沈齐、李文清.空基预警探测系统[M].北京:国防工业出版社.2012.

[3] 严勇，改进的蚁群一遗传算法在优化航线中的应用[J].计算机工程与应用.2008.44(23):230-232.

[4] 李璠.无人机航迹规划算法研究[D].大连：大连理工大学.2011.

[5] 黄文刚，张怡，姜文毅，等.基于改进稀疏A*算法的无人机航路规划[J].遥测遥感.2012,33(6):12-16.

[6] 唐强，王建元，朱志强.基于粒子群优化的三维突防航迹规划仿真研究[J].系统仿真学报，2004，16(9):2033-2038.

[7] 韩瑞锋，遗传算法原理与应用实例[M],北京：兵器工业出版社，2010.

[8] 刘超，欧杰，曹琪.基于自适应遗传算法的航迹规划研究[J].飞行力学.2010,28(1):36-39.

[9] TING LU,JIE ZHU.A Genetic Algorithm for Finding a Path Subject to Two Constraints[J].Applied Soft Computing Journal,2013,13(2):.

[10] HAI-BIN DUAN，XIANG-YIN ZHANG,JIANG WU,et al.Max-min Adaptive Ant Colony Optimization Approach to Mult-UAVs Coordinated Trajictory Replanning in Dynamic and Uncertain Environments[J].Journal of Bionic Engineering,2009:161-171.

[11] IOANNIS K NIKOLOS ,KIMON P VALAVANIS;NIKOS C TSOURVELOUDIS,et al.Evolutionary Algorithm Based Ofnine/Online Path Planner for UAV Navigation[C]//Transactions on Systems，Man，and Cybernetics-part B：Cybernetics：Accepted for future publication．2003：1-15．

[12] YOUFANG HUANG,CHENGJI LIANG,YANG YANG.The Optimum Route Problem by Genetic Algorithm for Loading/Unloading of Yard Crane[J].Computers & Industrial Engineering,2009,56(3):993-1001.