四维飞行轨迹预测方法的研究

王 静，张建伟，梁海军

（1.四川大学 计算机学院，四川 成都610064；2.四川大学 视觉合成图形图像技术国防重点学科实验室，四川 成都610064）

0 引 言

目前，空中交通自动化管理中的飞行安全、交通秩序维护、交通流量管理已成为热点研究问题，四维轨迹预测作为空管自动化的一项基本技术更在未来空管发展中有着重要地位。四维轨迹预测是对由航空器在空中的位置三维坐标经度、纬度、高度与对应点的时间组成四维轨迹进行预测。精确的四维轨迹预测是空中交通流量预测，飞行冲突探测与解脱，航迹优化，协同管制等的基础。

对轨迹预测算法的研究主要有以下3种：①基于神经网络或交互式多模型滤波等的预测研究；②基于航空器飞行模型和空气动力学模型的航迹预测算法；③基于数据挖掘的轨迹预测算法。

这些算法各有优缺点：更早的文献研究了基于α／β滤波，卡尔曼滤波，交互式多模型算法等，这类基于神经网络和交互式的算法模型简单，不需要大量的输入数据，但因为输入信息有限，缺乏提升性能空间，预测误差较大。文献 ［1］、［2］研究了基于飞行器模型和空气动力学模型的算法，这类算法需要大量飞行器性能参数和动力学参数，这些数据较难完整和准确的获得，且对飞行全程进行阶段划分也过于理想，真实飞行过程中飞机不断调整飞行姿态，很难确定属于哪一阶段，此外，飞机飞行过程中还会受到地面管制的影响，空气动力学模型忽略这一因素，从而导致了预测进度问题。文献 ［3］研究了基于数据挖掘的预测模型算法，它对每个航班进行建模，对历史数据进行回归预测，评估其管制因素和气象因子的影响。这种算法数据计算量和存储空间都较大，对于恶劣天气并不适用。

本文提出了一种新的预测模型—基于基因表达式编程（GEP）的频繁函数集挖掘的预测算法，通过对飞行数据的训练分析，挖掘出函数集即输入数据间的对应函数关系集。基于基因表达式编程的一般函数挖掘通常都以发现单个函数为目标，难以处理复杂数据集，例如对这类飞行数据就比较缺乏描述能力，而频繁函数集能满足对这类复杂数据的处理，通过仿真实验，该模型能对飞行全过程进行较精确的四维轨迹预测。

1 基于GEP的函数挖掘

1.1 GEP简介

GEP（gene expression programming）是借鉴生物遗传的基因表达规律提出的知识发现新技术，是葡萄牙学者Candida Ferreira在2000年提出。它的编码是采用简单易于操作的等长线性符号串即类似于遗传算法 （genetic algorithms，GA）的遗传编码，而表现型则采用树结构。GEP结合了遗传算法 （GA）的简单编码和遗传编程 （GP）的解决复杂问题弄得优点。在函数挖掘方面，比起传统的方法如数据拟合，回归分析和逼近论需要先确定函数和进行参数估计，再进而得出函数表达式。GEP则利用遗传算法的自适应性和自学习性搜索函数模型［4］，避免了传统算法建模时事先选定函数模型的盲目性。

1.2 GEP算法描述及应用

GEP的遗传编码串称为染色体。一个染色体可由多个基因组成。而每个基因有头部和尾部，头部包含函数符号（如 ＋，－，＊，＼，sin，cos，ln，if—else等）和终结符（程序的输入，常量以及没有参数的函数），尾部只包含终结符。头部长度h和尾部长度t满足以下关系式

式中：n——所使用的函数集中函数参数个数最大的值，头部长度则根据实际问题决定。例如符号集为 ｛＋，－，＊，＼，Q，sin，cos｝，则n＝2。假设h＝5，则对应的t＝6，基因总长度为11。于是，终结符集为 ｛a，b｝的

即对应一个GEP基因，其中从第6个字符开始的黑体部分表示尾部。对于加入常量参数处理的GEP编码，加入参数符号？作为终结符参加初始化和遗传操作，在编码尾部增加了跟尾部长度相同的参数集合，在计算时存放对应的参数序列。

GEP基因解码是从基因表达式依次读取字符并按从上到下和左到右的顺序排放成表达式树。式 （2）对应的表达式树如图1所示。

遍历表达式树得到＋Q＊b／aab为有效编码部分，有效基因长度为8。对应表达式为：＋（a／b）＊a。

图1 表达式树

GEP对初始种群进行遗传操作 （选择、交叉、变异、重组等）产生下一代，其中对每一个个体进行适应度评估，即用该表达式计算得到的数据与训练数据的吻合程度，选出较优个体。依此逐渐进化，直至产生满足算法停机的条件，可以是演化代数达到预定值或者适应度值达到一个预定阀值M，即fitness≤M。算法流程如图2所示。

图2 GEP算法流程

例如，文献 ［4］对某化学反应的生成物浓度与反应时间的数据进行函数挖掘实验，其中较好实验结果如下

2 频繁函数集挖掘

对于上面举例的化学反应数据是单一属性集，根据反应时间得反应浓度的函数，数据集和模型都较简单。然而有些情况下，单一函数就表现出了一定的局限性。例如文献 ［5］的例1，单个函数无法准确描述数据集中的属性关系。而在例2中，数据集中不是每个记录的属性值个数都是一样的，无法决定在哪些属性上挖掘，用单一函数就比较缺乏描述能力。

数据集中的属性集AttriSet＝ ｛A1，A2，…，Am｝，其中Ai表示各属性，m为属性集中属性个数，记录R＝ ｛Ai：Vi，Aj：Vj，…，Ak：Vk｝，其中Ai∈AttriSet，Vq（q＝1，2，…，k）为对应属性的值，数据集中所有记录构成记录集合DB＝ ｛R1，R2，…，Rt｝，DB的大小｜DB｜＝t。

对于函数

若 ｛X1，…，Xk｝AttriSet，则式 （4）的函数为AttriSet上的k－元函数。对于数据集DB中的一条记录Ri＝｛xi：Vxi，xj：Vxj， …，y：Vy｝， 如果有成立，则称式 （4）的函数在记录Ri上成立，其中e为预定的精度阀值，一般函数挖掘中对精度阀值的设定是在实验开始时给定固定值，文献［5］中应用了精度阀值队列 （PTQ），给定按降序排列的精度阀值队列， ［e1，e2，…，em］，其中0≤ei≤1 （1≤i≤m），进化代数的计算根据PTQ中的ei。即在精度为ei下需要进化的代数如下

记录集合RecordSet＝ ｛Ri｜Ri∈DB，f在Ri上成立｝的大小｜RecordSet｜与DB的大小｜DB｜的比值称为函数f的支持度，即

如果有Support（f）≥Minsupport，则称函数y＝f（x1，x2，…，xk）为频繁K－元函数，记为 FFSk，其中Minsupport为预先设定的最小支持度。容易得知频繁函数集如下：FFS＝FFD0∪FFS1∪…∪FFSm－1。

频繁函数集挖掘 （FFSM）就是在数据记录集合DB上进行多次反复，迭代地挖掘出满足最小支持度的函数集，应用PTQ策略的频繁函数集挖掘的算法流程图如图3描述。

3 预测模型试验

3.1 预测模型

目前，我国航空主要采用陆基地导航方式，飞行航线比较固定；短时间内的气象条件和管制规则限制也很相近。空管系统采用面向对象的四维轨迹预测机制，对于某段时间范围内的已有航班对象，如ATC限制、大气环境没有太大变化。基于这些，我们可将雷达获得的同一航班的前一天真实飞行数据作为训练数据集合 （DB），挖掘出各元频繁函数集，找出较好的函数模型来预测这一航班次日的飞行高度和时间情况。模型中的AttriSet由经度、纬度、高度、时间组成。

3.2 实验及性能分析

实验一：基于频繁函数集挖掘的轨迹预测

图3 采用PTQ策略的频繁函数集挖掘算法流程

实验数据：雷达获取的航班CCA4511（成都－青岛）于2010年9月28日的真实飞行数据，由于全程的时间和经纬度变化都不大，为了使精度更高，将时间和经纬度的单位都换成秒，且进行归零处理，即在起点ZUUU （成都）的经纬度和时间的值都是零，高度单位为米。DB的记录形式：

R＝ ｛g：6842，a：5020，h：7020，t：1380｝

AttriSet＝ ｛g，a，h，t｝，各属性分别代表经度、纬度、高度和时间，对初始数据进行了初步去噪，DB大小为200。

实验目的：得到频繁函数集，用来预测2010年9月29日同一航班过固定点的时间和高度信息，再与这一天的真实数据对比，使误差最小的函数才是较好的函数模型。

实验参数：

函数集合：FuncSet＝ ｛＋，－，＊，／，S，C，T，Q，l，e｝（S表示sin，C表示cos，T表示tan，Q表示开方，l表示ln，e表示exp函数 ）

最小支持度：Minsupport＝70%

精度阀值序列：PTQ＝ ［2E－1，2E－2，8E－3，2E－3］

种群规模：PopSize＝200

进化总代数：NumberofGeneration＝200

基因头长：h＝10

染色体中基因个数：NumofGenes＝3

连接函数：＋

实验得到的较好函数模型计算出了ZUUU－ZSQD其中CCTZS、JTG、 P248、 SUBUL、 NSH、 SHX、 WXI、YQG、YS等9个固定点的过点时间和高度，跟9月29日的真实数据对比如表1所示。

表1 实验结果与真实数据对比

实验参数：频繁函数挖掘的参数同实验一。

总的实验次数：Runs＝300

单一函数挖掘的精度阀值分别为e＝2E－2，e＝8E－3，e＝2E－3种情况，最小支持度Minsupport＝100%。

单一函数挖掘GEP的参数都与实验一相同。

实验结果如图4所示。通过图4可以看出，频繁函数集挖掘相对于单一函数挖掘在轨迹预测上的成功率较高，也说明对于这种数据集较复杂的问题，频繁函数集比单一函数的描述能力更强。

由表1看出，最大时间误差为点SHX的38s，最大高度误差为点CCTZS的61m，在雷达获取数据时就存在一定的误差。所以结果显示，在四维轨迹预测上应用这种频繁函数集挖掘的模型是可行的，且预测结果精度较高。

实验二：频繁函数集挖掘与单一函数挖掘的比较

实验数据：同实验一

实验目的：函数模型挖掘的成功率比较，即实验成功的次数与总的试验次数的比值

4 结束语

通过分析目前主要的3种研究轨迹预测模型的方法，提出基于函数挖掘的预测模型，通过对历史数据的操作挖掘出较好的函数模型来预测未来的航迹情况，通过实验对单一函数挖掘与频繁函数集挖掘的对比，证明频繁函数集挖掘的成功率和准确率都较高。但是频繁函数集中的最小支持度和经度阀值都对实验结果有所影响，设置合适的值都比较困难。虽然强调频繁函数子集的完整性不是很必要，但是属性集的大小和组成对结果函数集也是有影响的。我们的下一步工作是研究更合适的最小支持度、精度阀值和获取更大更合适的属性集数据记录集，以使结果函数集模型更好，能更精确的预测出四维轨迹。

图4 频繁函数集与单一函数不同精度阀值下的成功率对比

［1］GUO Yuntao，ZHU Yanbo，HUANG Zhigang.Study on key trajectory prediction techniques of civil aviation aircraf ［J］.Journal of Civil Aviation University of China，2007，25 （1）：20－24（in Chinese）.［郭运韬，朱衍波，黄智刚.民用飞机航迹预测关键技术研究 ［J］.中国民航大学学报，2007，25（1）：20－24.］

［2］WANG Chao，GUO Jiuxia.Prediction of 4Dtrajectory based on basic flight models ［J］.Journal of Southwest Jiaotong University，2009，44 （2）：295－300 （in Chinese）. ［王超，郭九霞.基于基本飞行模型的4D航迹预测方法 ［J］.西南交通大学学报，2009，44 （2）：295－300.］

［3］WU Kun，PAN Wei.4－D trajectory prediction model based on data mining ［J］.Journal of Computer Applications，2007，27（11）：2637－2639 （in Chinese）.［吴鹍，潘薇.基于数据挖掘的四维飞行轨迹预测模型 ［J］.计算机应用，2007，27（11）：2637－2639.］

［4］MO Haifang，KANG Lishan.Automatic modeling of complex functions based on gene expression programming ［J］.Journal of System Simulation，2008，20 （11）：2828－2831 （in Chinese）.［莫海芳，康立山.用GEP实现复杂函数的自动建模［J］.系统仿真学报，2008，20 （11）：2828－2831.］

［5］JIA Xiaobin，TANG Changjie，ZUO Jie，et al.Mining frequent function set based on gene expression programming ［J］.Chinese Journal of Computers，2005，28 （8）：1247－1253 （in Chinese）.［贾晓斌，唐常杰，左劫，等.基于基因表达式编程的频繁函数集挖掘 ［J］.计算机学报，2005，28 （8）：1247－1253.］

［6］TANG Changjie，ZHANG Tianqing，ZUO Jie，et al.Knowledge discovery based on gene expression programming——history，achievements and future directions ［J］.Journal of Computer Applications，2004，24 （10）：7－10 （in Chinese）.［唐常杰，张天庆，左劫，等.基于基因表达式编程的知识发现—沿革、成果和发展方向 ［J］.计算机应用，2004，24 （10）：7－10.］

［7］YUAN Changan，TANG Changjie，ZUO Jie，et al.Function mining based on gene expression programming——convergency analysis and rename－guided evolution algorithm ［J］.Journal of Sichuan University （Engineering Science Edition），2004，36 （6）：100－105（in Chinese）.［元昌安，唐常杰，左劫，等.基于基因表达式编程的函数挖掘—收敛性分析与残差制导进化算法 ［J］.四川大学学报 （工程科学版），2004，36 （6）：100－105.］

［8］ZUO J，TANG C J，LI C.Time series prediction based on gene expression programming ［C］.International Conference for Web Information，2004.

［9］GONG W Y，CAI Z H，LIU Y D.Automatic modeling of complex functions based on gene expression programming［J］.Journal of System Simulation，2006，18 （6）：1450－1454.

［10］CHEN A S，CAI Z H，GU Q.Novel GEP algorithm and its application ［J］.Application Research of Computers，2007，24（6）：98－102.

［11］NASA.A mathematical basis for the safety analysis of conflict prevention algorithms ［C］.National Aeronautics and Space Administration，2009.

［12］Munoz，Narkawicz.Time of closest approach in three－dimensional airspace ［C］.National Aeronautics and Space Administration，2010.

［13］ZHOU M H，WANG Q X.A perspective on evolution of middleware technology supporting internetware ［J］.Journal of Frontiers of Computer Science and Technology，2008，2（4）：337－345.

［14］ZHU Chengzhen，CHENG Nong，LI Qing.The four－dimensional trajectory prediction in terminal airspace ［J］.Journal of System Simulation，2010，22 （z1）：163－166 （in Chinese）.［朱成阵，程农，李清.终端区四维轨迹预测 ［J］.系统仿真学报，2010，22 （z1）：163－166.］

［15］QIN Weihua，HU Fei，HOU Xuemei.Tracks correlation algorithm based on wavelet transform ［J］.Journal of Electronics ＆Information Technology，2007，29 （5）：1027－1030 （in Chinese）.［秦卫华，胡飞，侯雪梅.基于小波变换的航迹关联方法 ［J］.电子与信息学报，2007，29 （5）：1027－1030.］