王 靜，張建偉，梁海軍

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

0 引 言

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

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

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

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

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

1.1 GEP簡(jiǎn)介

GEP（gene expression programming）是借鑒生物遺傳的基因表達(dá)規(guī)律提出的知識(shí)發(fā)現(xiàn)新技術(shù)，是葡萄牙學(xué)者Candida Ferreira在2000年提出。它的編碼是采用簡(jiǎn)單易于操作的等長(zhǎng)線(xiàn)性符號(hào)串即類(lèi)似于遺傳算法 （genetic algorithms，GA）的遺傳編碼，而表現(xiàn)型則采用樹(shù)結(jié)構(gòu)。GEP結(jié)合了遺傳算法 （GA）的簡(jiǎn)單編碼和遺傳編程 （GP）的解決復(fù)雜問(wèn)題弄得優(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的遺傳編碼串稱(chēng)為染色體。一個(gè)染色體可由多個(gè)基因組成。而每個(gè)基因有頭部和尾部，頭部包含函數(shù)符號(hào)（如 ＋，－，＊，＼，sin，cos，ln，if—else等）和終結(jié)符（程序的輸入，常量以及沒(méi)有參數(shù)的函數(shù)），尾部只包含終結(jié)符。頭部長(zhǎng)度h和尾部長(zhǎng)度t滿(mǎn)足以下關(guān)系式

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

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

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

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

圖1 表達(dá)式樹(shù)

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

圖2 GEP算法流程

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

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

對(duì)于上面舉例的化學(xué)反應(yīng)數(shù)據(jù)是單一屬性集，根據(jù)反應(yīng)時(shí)間得反應(yīng)濃度的函數(shù)，數(shù)據(jù)集和模型都較簡(jiǎn)單。然而有些情況下，單一函數(shù)就表現(xiàn)出了一定的局限性。例如文獻(xiàn) ［5］的例1，單個(gè)函數(shù)無(wú)法準(zhǔn)確描述數(shù)據(jù)集中的屬性關(guān)系。而在例2中，數(shù)據(jù)集中不是每個(gè)記錄的屬性值個(gè)數(shù)都是一樣的，無(wú)法決定在哪些屬性上挖掘，用單一函數(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）為對(duì)應(yīng)屬性的值，數(shù)據(jù)集中所有記錄構(gòu)成記錄集合DB＝ ｛R1，R2，…，Rt｝，DB的大?。麯B｜＝t。

對(duì)于函數(shù)

若 ｛X1，…，Xk｝AttriSet，則式 （4）的函數(shù)為AttriSet上的k－元函數(shù)。對(duì)于數(shù)據(jù)集DB中的一條記錄Ri＝｛xi：Vxi，xj：Vxj， …，y：Vy｝， 如果有成立，則稱(chēng)式 （4）的函數(shù)在記錄Ri上成立，其中e為預(yù)定的精度閥值，一般函數(shù)挖掘中對(duì)精度閥值的設(shè)定是在實(shí)驗(yàn)開(kāi)始時(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的大小｜DB｜的比值稱(chēng)為函數(shù)f的支持度，即

如果有Support（f）≥Minsupport，則稱(chēng)函數(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ù)，迭代地挖掘出滿(mǎn)足最小支持度的函數(shù)集，應(yīng)用PTQ策略的頻繁函數(shù)集挖掘的算法流程圖如圖3描述。

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

3.1 預(yù)測(cè)模型

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

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

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

圖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í)間，對(duì)初始數(shù)據(jù)進(jìn)行了初步去噪，DB大小為200。

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

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

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

最小支持度：Minsupport＝70%

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

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

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

基因頭長(zhǎng)：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)的過(guò)點(diǎn)時(shí)間和高度，跟9月29日的真實(shí)數(shù)據(jù)對(duì)比如表1所示。

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

實(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所示。通過(guò)圖4可以看出，頻繁函數(shù)集挖掘相對(duì)于單一函數(shù)挖掘在軌跡預(yù)測(cè)上的成功率較高，也說(shuō)明對(duì)于這種數(shù)據(jù)集較復(fù)雜的問(wèn)題，頻繁函數(shù)集比單一函數(shù)的描述能力更強(qiáng)。

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

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

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

［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ù)測(cè)關(guān)鍵技術(shù)研究 ［J］.中國(guó)民航大學(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ù)測(cè)方法 ［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ù)測(cè)模型 ［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á)式編程的知識(shí)發(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ù)測(cè) ［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.］