四維飛行軌跡預測方法的研究

王 靜，張建偉，梁海軍

（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的大?。麯B｜＝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上成立｝的大?。黂ecordSet｜與DB的大?。麯B｜的比值稱為函數f的支持度，即

如果有Support（f）≥Minsupport，則稱函數y＝f（x1，x2，…，xk）為頻繁K－元函數，記為 FFSk，其中Minsupport為預先設定的最小支持度。容易得知頻繁函數集如下：FFS＝FFD0∪FFS1∪…∪FFSm－1。

頻繁函數集挖掘 （FFSM）就是在數據記錄集合DB上進行多次反復，迭代地挖掘出滿足最小支持度的函數集，應用PTQ策略的頻繁函數集挖掘的算法流程圖如圖3描述。

3 預測模型試驗

3.1 預測模型

目前，我國航空主要采用陸基地導航方式，飛行航線比較固定；短時間內的氣象條件和管制規則限制也很相近?？展芟到y采用面向對象的四維軌跡預測機制，對于某段時間范圍內的已有航班對象，如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.］