王 靜，張建偉，梁海軍

（1.四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都610064；2.四川大學(xué) 視覺合成圖形圖像技術(shù)國防重點(diǎn)學(xué)科實(shí)驗(yàn)室，四川 成都610064）

0 引 言

目前，空中交通自動(dòng)化管理中的飛行安全、交通秩序維護(hù)、交通流量管理已成為熱點(diǎn)研究問題，四維軌跡預(yù)測作為空管自動(dòng)化的一項(xiàng)基本技術(shù)更在未來空管發(fā)展中有著重要地位。四維軌跡預(yù)測是對由航空器在空中的位置三維坐標(biāo)經(jīng)度、緯度、高度與對應(yīng)點(diǎn)的時(shí)間組成四維軌跡進(jìn)行預(yù)測。精確的四維軌跡預(yù)測是空中交通流量預(yù)測，飛行沖突探測與解脫，航跡優(yōu)化，協(xié)同管制等的基礎(chǔ)。

對軌跡預(yù)測算法的研究主要有以下3種：①基于神經(jīng)網(wǎng)絡(luò)或交互式多模型濾波等的預(yù)測研究；②基于航空器飛行模型和空氣動(dòng)力學(xué)模型的航跡預(yù)測算法；③基于數(shù)據(jù)挖掘的軌跡預(yù)測算法。

這些算法各有優(yōu)缺點(diǎn)：更早的文獻(xiàn)研究了基于α／β濾波，卡爾曼濾波，交互式多模型算法等，這類基于神經(jīng)網(wǎng)絡(luò)和交互式的算法模型簡單，不需要大量的輸入數(shù)據(jù)，但因?yàn)檩斎胄畔⒂邢?，缺乏提升性能空間，預(yù)測誤差較大。文獻(xiàn) ［1］、［2］研究了基于飛行器模型和空氣動(dòng)力學(xué)模型的算法，這類算法需要大量飛行器性能參數(shù)和動(dòng)力學(xué)參數(shù)，這些數(shù)據(jù)較難完整和準(zhǔn)確的獲得，且對飛行全程進(jìn)行階段劃分也過于理想，真實(shí)飛行過程中飛機(jī)不斷調(diào)整飛行姿態(tài)，很難確定屬于哪一階段，此外，飛機(jī)飛行過程中還會(huì)受到地面管制的影響，空氣動(dòng)力學(xué)模型忽略這一因素，從而導(dǎo)致了預(yù)測進(jìn)度問題。文獻(xiàn) ［3］研究了基于數(shù)據(jù)挖掘的預(yù)測模型算法，它對每個(gè)航班進(jìn)行建模，對歷史數(shù)據(jù)進(jìn)行回歸預(yù)測，評估其管制因素和氣象因子的影響。這種算法數(shù)據(jù)計(jì)算量和存儲(chǔ)空間都較大，對于惡劣天氣并不適用。

本文提出了一種新的預(yù)測模型—基于基因表達(dá)式編程（GEP）的頻繁函數(shù)集挖掘的預(yù)測算法，通過對飛行數(shù)據(jù)的訓(xùn)練分析，挖掘出函數(shù)集即輸入數(shù)據(jù)間的對應(yīng)函數(shù)關(guān)系集。基于基因表達(dá)式編程的一般函數(shù)挖掘通常都以發(fā)現(xiàn)單個(gè)函數(shù)為目標(biāo)，難以處理復(fù)雜數(shù)據(jù)集，例如對這類飛行數(shù)據(jù)就比較缺乏描述能力，而頻繁函數(shù)集能滿足對這類復(fù)雜數(shù)據(jù)的處理，通過仿真實(shí)驗(yàn)，該模型能對飛行全過程進(jìn)行較精確的四維軌跡預(yù)測。

1 基于GEP的函數(shù)挖掘

1.1 GEP簡介

GEP（gene expression programming）是借鑒生物遺傳的基因表達(dá)規(guī)律提出的知識發(fā)現(xiàn)新技術(shù)，是葡萄牙學(xué)者Candida Ferreira在2000年提出。它的編碼是采用簡單易于操作的等長線性符號串即類似于遺傳算法 （genetic algorithms，GA）的遺傳編碼，而表現(xiàn)型則采用樹結(jié)構(gòu)。GEP結(jié)合了遺傳算法 （GA）的簡單編碼和遺傳編程 （GP）的解決復(fù)雜問題弄得優(yōu)點(diǎn)。在函數(shù)挖掘方面，比起傳統(tǒng)的方法如數(shù)據(jù)擬合，回歸分析和逼近論需要先確定函數(shù)和進(jìn)行參數(shù)估計(jì)，再進(jìn)而得出函數(shù)表達(dá)式。GEP則利用遺傳算法的自適應(yīng)性和自學(xué)習(xí)性搜索函數(shù)模型［4］，避免了傳統(tǒng)算法建模時(shí)事先選定函數(shù)模型的盲目性。

1.2 GEP算法描述及應(yīng)用

GEP的遺傳編碼串稱為染色體。一個(gè)染色體可由多個(gè)基因組成。而每個(gè)基因有頭部和尾部，頭部包含函數(shù)符號（如 ＋，－，＊，＼，sin，cos，ln，if—else等）和終結(jié)符（程序的輸入，常量以及沒有參數(shù)的函數(shù)），尾部只包含終結(jié)符。頭部長度h和尾部長度t滿足以下關(guān)系式

式中：n——所使用的函數(shù)集中函數(shù)參數(shù)個(gè)數(shù)最大的值，頭部長度則根據(jù)實(shí)際問題決定。例如符號集為 ｛＋，－，＊，＼，Q，sin，cos｝，則n＝2。假設(shè)h＝5，則對應(yīng)的t＝6，基因總長度為11。于是，終結(jié)符集為 ｛a，b｝的

即對應(yīng)一個(gè)GEP基因，其中從第6個(gè)字符開始的黑體部分表示尾部。對于加入常量參數(shù)處理的GEP編碼，加入?yún)?shù)符號？作為終結(jié)符參加初始化和遺傳操作，在編碼尾部增加了跟尾部長度相同的參數(shù)集合，在計(jì)算時(shí)存放對應(yīng)的參數(shù)序列。

GEP基因解碼是從基因表達(dá)式依次讀取字符并按從上到下和左到右的順序排放成表達(dá)式樹。式 （2）對應(yīng)的表達(dá)式樹如圖1所示。

遍歷表達(dá)式樹得到＋Q＊b／aab為有效編碼部分，有效基因長度為8。對應(yīng)表達(dá)式為：＋（a／b）＊a。

圖1 表達(dá)式樹

GEP對初始種群進(jìn)行遺傳操作 （選擇、交叉、變異、重組等）產(chǎn)生下一代，其中對每一個(gè)個(gè)體進(jìn)行適應(yīng)度評估，即用該表達(dá)式計(jì)算得到的數(shù)據(jù)與訓(xùn)練數(shù)據(jù)的吻合程度，選出較優(yōu)個(gè)體。依此逐漸進(jìn)化，直至產(chǎn)生滿足算法停機(jī)的條件，可以是演化代數(shù)達(dá)到預(yù)定值或者適應(yīng)度值達(dá)到一個(gè)預(yù)定閥值M，即fitness≤M。算法流程如圖2所示。

圖2 GEP算法流程

例如，文獻(xiàn) ［4］對某化學(xué)反應(yīng)的生成物濃度與反應(yīng)時(shí)間的數(shù)據(jù)進(jìn)行函數(shù)挖掘?qū)嶒?yàn)，其中較好實(shí)驗(yàn)結(jié)果如下

2 頻繁函數(shù)集挖掘

對于上面舉例的化學(xué)反應(yīng)數(shù)據(jù)是單一屬性集，根據(jù)反應(yīng)時(shí)間得反應(yīng)濃度的函數(shù)，數(shù)據(jù)集和模型都較簡單。然而有些情況下，單一函數(shù)就表現(xiàn)出了一定的局限性。例如文獻(xiàn) ［5］的例1，單個(gè)函數(shù)無法準(zhǔn)確描述數(shù)據(jù)集中的屬性關(guān)系。而在例2中，數(shù)據(jù)集中不是每個(gè)記錄的屬性值個(gè)數(shù)都是一樣的，無法決定在哪些屬性上挖掘，用單一函數(shù)就比較缺乏描述能力。

數(shù)據(jù)集中的屬性集AttriSet＝ ｛A1，A2，…，Am｝，其中Ai表示各屬性，m為屬性集中屬性個(gè)數(shù)，記錄R＝ ｛Ai：Vi，Aj：Vj，…，Ak：Vk｝，其中Ai∈AttriSet，Vq（q＝1，2，…，k）為對應(yīng)屬性的值，數(shù)據(jù)集中所有記錄構(gòu)成記錄集合DB＝ ｛R1，R2，…，Rt｝，DB的大小｜DB｜＝t。

對于函數(shù)

若 ｛X1，…，Xk｝AttriSet，則式 （4）的函數(shù)為AttriSet上的k－元函數(shù)。對于數(shù)據(jù)集DB中的一條記錄Ri＝｛xi：Vxi，xj：Vxj， …，y：Vy｝， 如果有成立，則稱式 （4）的函數(shù)在記錄Ri上成立，其中e為預(yù)定的精度閥值，一般函數(shù)挖掘中對精度閥值的設(shè)定是在實(shí)驗(yàn)開始時(shí)給定固定值，文獻(xiàn)［5］中應(yīng)用了精度閥值隊(duì)列 （PTQ），給定按降序排列的精度閥值隊(duì)列， ［e1，e2，…，em］，其中0≤ei≤1 （1≤i≤m），進(jìn)化代數(shù)的計(jì)算根據(jù)PTQ中的ei。即在精度為ei下需要進(jìn)化的代數(shù)如下

記錄集合RecordSet＝ ｛Ri｜Ri∈DB，f在Ri上成立｝的大?。黂ecordSet｜與DB的大?。麯B｜的比值稱為函數(shù)f的支持度，即

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

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

3 預(yù)測模型試驗(yàn)

3.1 預(yù)測模型

目前，我國航空主要采用陸基地導(dǎo)航方式，飛行航線比較固定；短時(shí)間內(nèi)的氣象條件和管制規(guī)則限制也很相近?？展芟到y(tǒng)采用面向?qū)ο蟮乃木S軌跡預(yù)測機(jī)制，對于某段時(shí)間范圍內(nèi)的已有航班對象，如ATC限制、大氣環(huán)境沒有太大變化?；谶@些，我們可將雷達(dá)獲得的同一航班的前一天真實(shí)飛行數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集合 （DB），挖掘出各元頻繁函數(shù)集，找出較好的函數(shù)模型來預(yù)測這一航班次日的飛行高度和時(shí)間情況。模型中的AttriSet由經(jīng)度、緯度、高度、時(shí)間組成。

3.2 實(shí)驗(yàn)及性能分析

實(shí)驗(yàn)一：基于頻繁函數(shù)集挖掘的軌跡預(yù)測

圖3 采用PTQ策略的頻繁函數(shù)集挖掘算法流程

實(shí)驗(yàn)數(shù)據(jù)：雷達(dá)獲取的航班CCA4511（成都－青島）于2010年9月28日的真實(shí)飛行數(shù)據(jù)，由于全程的時(shí)間和經(jīng)緯度變化都不大，為了使精度更高，將時(shí)間和經(jīng)緯度的單位都換成秒，且進(jìn)行歸零處理，即在起點(diǎn)ZUUU （成都）的經(jīng)緯度和時(shí)間的值都是零，高度單位為米。DB的記錄形式：

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

AttriSet＝ ｛g，a，h，t｝，各屬性分別代表經(jīng)度、緯度、高度和時(shí)間，對初始數(shù)據(jù)進(jìn)行了初步去噪，DB大小為200。

實(shí)驗(yàn)?zāi)康模旱玫筋l繁函數(shù)集，用來預(yù)測2010年9月29日同一航班過固定點(diǎn)的時(shí)間和高度信息，再與這一天的真實(shí)數(shù)據(jù)對比，使誤差最小的函數(shù)才是較好的函數(shù)模型。

實(shí)驗(yàn)參數(shù)：

函數(shù)集合：FuncSet＝ ｛＋，－，＊，／，S，C，T，Q，l，e｝（S表示sin，C表示cos，T表示tan，Q表示開方，l表示ln，e表示exp函數(shù) ）

最小支持度：Minsupport＝70%

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

種群規(guī)模：PopSize＝200

進(jìn)化總代數(shù)：NumberofGeneration＝200

基因頭長：h＝10

染色體中基因個(gè)數(shù)：NumofGenes＝3

連接函數(shù)：＋

實(shí)驗(yàn)得到的較好函數(shù)模型計(jì)算出了ZUUU－ZSQD其中CCTZS、JTG、 P248、 SUBUL、 NSH、 SHX、 WXI、YQG、YS等9個(gè)固定點(diǎn)的過點(diǎn)時(shí)間和高度，跟9月29日的真實(shí)數(shù)據(jù)對比如表1所示。

表1 實(shí)驗(yàn)結(jié)果與真實(shí)數(shù)據(jù)對比

實(shí)驗(yàn)參數(shù)：頻繁函數(shù)挖掘的參數(shù)同實(shí)驗(yàn)一。

總的實(shí)驗(yàn)次數(shù)：Runs＝300

單一函數(shù)挖掘的精度閥值分別為e＝2E－2，e＝8E－3，e＝2E－3種情況，最小支持度Minsupport＝100%。

單一函數(shù)挖掘GEP的參數(shù)都與實(shí)驗(yàn)一相同。

實(shí)驗(yàn)結(jié)果如圖4所示。通過圖4可以看出，頻繁函數(shù)集挖掘相對于單一函數(shù)挖掘在軌跡預(yù)測上的成功率較高，也說明對于這種數(shù)據(jù)集較復(fù)雜的問題，頻繁函數(shù)集比單一函數(shù)的描述能力更強(qiáng)。

由表1看出，最大時(shí)間誤差為點(diǎn)SHX的38s，最大高度誤差為點(diǎn)CCTZS的61m，在雷達(dá)獲取數(shù)據(jù)時(shí)就存在一定的誤差。所以結(jié)果顯示，在四維軌跡預(yù)測上應(yīng)用這種頻繁函數(shù)集挖掘的模型是可行的，且預(yù)測結(jié)果精度較高。

實(shí)驗(yàn)二：頻繁函數(shù)集挖掘與單一函數(shù)挖掘的比較

實(shí)驗(yàn)數(shù)據(jù)：同實(shí)驗(yàn)一

實(shí)驗(yàn)?zāi)康模汉瘮?shù)模型挖掘的成功率比較，即實(shí)驗(yàn)成功的次數(shù)與總的試驗(yàn)次數(shù)的比值

4 結(jié)束語

通過分析目前主要的3種研究軌跡預(yù)測模型的方法，提出基于函數(shù)挖掘的預(yù)測模型，通過對歷史數(shù)據(jù)的操作挖掘出較好的函數(shù)模型來預(yù)測未來的航跡情況，通過實(shí)驗(yàn)對單一函數(shù)挖掘與頻繁函數(shù)集挖掘的對比，證明頻繁函數(shù)集挖掘的成功率和準(zhǔn)確率都較高。但是頻繁函數(shù)集中的最小支持度和經(jīng)度閥值都對實(shí)驗(yàn)結(jié)果有所影響，設(shè)置合適的值都比較困難。雖然強(qiáng)調(diào)頻繁函數(shù)子集的完整性不是很必要，但是屬性集的大小和組成對結(jié)果函數(shù)集也是有影響的。我們的下一步工作是研究更合適的最小支持度、精度閥值和獲取更大更合適的屬性集數(shù)據(jù)記錄集，以使結(jié)果函數(shù)集模型更好，能更精確的預(yù)測出四維軌跡。

圖4 頻繁函數(shù)集與單一函數(shù)不同精度閥值下的成功率對比

［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）.［郭運(yùn)韜，朱衍波，黃智剛.民用飛機(jī)航跡預(yù)測關(guān)鍵技術(shù)研究 ［J］.中國民航大學(xué)學(xué)報(bào)，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航跡預(yù)測方法 ［J］.西南交通大學(xué)學(xué)報(bào)，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）.［吳鹍，潘薇.基于數(shù)據(jù)挖掘的四維飛行軌跡預(yù)測模型 ［J］.計(jì)算機(jī)應(yīng)用，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實(shí)現(xiàn)復(fù)雜函數(shù)的自動(dòng)建模［J］.系統(tǒng)仿真學(xué)報(bào)，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）.［賈曉斌，唐常杰，左劫，等.基于基因表達(dá)式編程的頻繁函數(shù)集挖掘 ［J］.計(jì)算機(jī)學(xué)報(bào)，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）.［唐常杰，張?zhí)鞈c，左劫，等.基于基因表達(dá)式編程的知識發(fā)現(xiàn)—沿革、成果和發(fā)展方向 ［J］.計(jì)算機(jī)應(yīng)用，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）.［元昌安，唐常杰，左劫，等.基于基因表達(dá)式編程的函數(shù)挖掘—收斂性分析與殘差制導(dǎo)進(jìn)化算法 ［J］.四川大學(xué)學(xué)報(bào) （工程科學(xué)版），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）.［朱成陣，程農(nóng)，李清.終端區(qū)四維軌跡預(yù)測 ［J］.系統(tǒng)仿真學(xué)報(bào)，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）.［秦衛(wèi)華，胡飛，侯雪梅.基于小波變換的航跡關(guān)聯(lián)方法 ［J］.電子與信息學(xué)報(bào)，2007，29 （5）：1027－1030.］