韓冬， 張學軍,*， 聶尊禮， 管祥民

(1. 北京航空航天大學 電子信息工程學院, 北京 100083； 2. 中國民航管理干部學院, 北京 100102)

復雜低空受多樣多變地形、障礙物和極端惡劣氣象等復雜環(huán)境要素的約束，有限空域內(nèi)多航空器的密集飛行呈現(xiàn)出高度復雜的時空相互制約性[1]，基于航路航線沖突探測的一些假設條件在低空中并不適用。此外，由于低空沖突探測以短期預測為主，沖突探測必須在極短的時間內(nèi)完成，這樣才能保證在有限的時間、空間裕度內(nèi)實施有效的躲避策略。綜合考慮適用性與計算效率，是低空飛行沖突探測的難點所在。

國內(nèi)外對于沖突探測的研究主要分為確定型(也稱幾何型)和概率型(也稱解析型)2類。確定型沖突探測[2-4]一般采用計算幾何的方法，判斷2架航空器在相遇幾何內(nèi)是否存在潛在飛行沖突。但是實際情況下存在風、導航定位、飛行員操作等不確定性因素引起的誤差，將直接影響到?jīng)_突探測的準確度。概率型沖突探測[5-7]則通過計算航空器之間的沖突概率，以解析的方法確定是否存在潛在飛行沖突，但是閾值的選取十分關(guān)鍵：如果閾值選取過大，可能造成漏警；如果閾值選取過小，則可能造成大量的誤警[8]。

傳統(tǒng)的空中交通警戒與防撞系統(tǒng)(Traffic Alert and Collision Avoidance System,TCAS)是當前廣泛應用的機載避撞系統(tǒng)[9]，主要為飛行員提供空-空碰撞告警。TCASⅠ只提供碰撞告警服務，TCASⅡ除了告警外，還提供沖突解脫建議，但只是簡單的爬升和下降機動，此外TCASⅡ在1 000 m以下低空存在較高的虛警率，在通用航空上應用并不廣泛[10]。廣播式自動相關(guān)監(jiān)視(Automatic Dependent Surveillance-Broadcast，ADS-B)設備結(jié)構(gòu)簡單，成本較低，信息更新速率快，監(jiān)視精度較高，已經(jīng)廣泛用于高空航線飛機和低空通航飛機上[11]。

Lin[12]根據(jù)TCAS檢測邏輯，設計了一種基于ADS-B和目視飛行規(guī)則的針對低空通航小飛機的空域沖突探測和解脫方法。焦玉亮等[13]采用支持向量機(Support Vector Machine,SVM)，提出一種針對高空航路的水平二維沖突探測方法。

考慮到通用航空一般在特定空域內(nèi)飛行，在相對固定的飛行環(huán)境中，可以獲取豐富的歷史飛行數(shù)據(jù)，通過提前分析這些先驗數(shù)據(jù)，挖掘數(shù)據(jù)關(guān)聯(lián)特征，提取飛行沖突探測的判定依據(jù)，是一種解決低空復雜飛行沖突探測問題的新思路。航空器可以在起飛前加載經(jīng)過訓練的分類器，減少飛行中在線解算的時間，有效解決傳統(tǒng)沖突探測算法難以兼顧適用性與解算效率的缺陷。

1 基于SVM的沖突探測

檢測系統(tǒng)的結(jié)構(gòu)如圖1所示。

圖1 檢測系統(tǒng)結(jié)構(gòu)

1.1 數(shù)據(jù)預處理

數(shù)據(jù)預處理主要計算目標飛機相對于本機的位置、速度和航向等信息。

為了簡化模型，保護區(qū)設置為半徑528 ft(1 ft=0.304 8 m)的球形，如圖2所示。

圖2 保護區(qū)模型

相對水平航向是以相對坐標系的X軸正方向為基準的。

2) 如果目標飛機的相對速度vRx<0,vRy>0或者vRx<0,vRy<0,水平相對航向為

垂直航向是以相對坐標軸中Z軸正方向為基準。

1.2 SVM模塊

在將經(jīng)過預處理的數(shù)據(jù)輸入SVM模塊后，筆者首先將數(shù)據(jù)進行過濾處理，將一些一定不會發(fā)生沖突的目標提前進行分類處理，如表1所示。

經(jīng)過訓練的SVM分類器對經(jīng)過過濾和歸一化的輸入數(shù)據(jù)進行分類。對于所有的分類目標，如果在t時刻目標為存在潛在沖突可能，則在假設對于第i架飛機在t時刻的預測值為Pt(Ti)=1，如果目標在t時刻經(jīng)過SVM分類檢測不存在沖突可能，則Pt(Ti)=-1。

數(shù)據(jù)后期處理主要采用移動平均加權(quán)，考慮到對飛機的沖突檢測是一個連續(xù)的過程，在某個時間點對沖突進行探測，需要考慮前一段時間的預測結(jié)果。移動加權(quán)平均的滑動窗口為m，滑動加權(quán)系數(shù)w={wt-m+1,…,wt-1,wt}，則對于第i架飛機在t時刻經(jīng)過移動加權(quán)平均后的預測值為

表1 無沖突判定準則

2 支持向量機

通過選取適當?shù)暮撕瘮?shù)及相應的參數(shù)，以及懲罰因子C,可以建立一個適當?shù)姆诸惸Ｐ蛯?shù)據(jù)進行分類。所以，參數(shù)的選取是建立SVM模型的重要步驟。本文選取徑向基函數(shù)作為其核函數(shù)，涉及到的參數(shù)有C和σ。

C主要影響建立SVM模型的復雜度。較高的C使得模型的復雜度高，但模型的推廣能力差，C越低，建立的模型越簡單，模型的推廣能力越高。較高的C雖然使得模型訓練準確度高，但是對于預測樣本的分類正確率低。

σ控制了徑向的作用范圍，σ越高，對于特征數(shù)據(jù)的映射能力越弱，σ越低，映射能力越強，但是可能會造成過擬合的情況。

傳統(tǒng)的參數(shù)選取的方法包括網(wǎng)格搜索(Grid-Search)法和經(jīng)驗選擇法，經(jīng)驗選擇法雖然簡單，但是存在很大的主觀性。網(wǎng)格搜索法在一定的搜索空間中以一定的步進逐步搜索，但是存在計算量大，搜索精度不足等問題。

近年來，國內(nèi)外許多研究學者采用進化算法對SVM的參數(shù)進行選取。常用的有遺傳(GA)算法和粒子群(PSO)算法。GA算法借鑒生物界中生物進化繁衍的規(guī)律，通過對個體的選擇、交叉、變異等操作來尋找解空間的潛在最優(yōu)解。但是GA算法具有較大的隨機性，且算法本身的參數(shù)設置過多，容易產(chǎn)生早熟收斂等問題。PSO算法模擬鳥群捕食行為，通過考慮粒子的個體最優(yōu)值和全體最優(yōu)值來引導粒子的搜索策略。但是PSO算法同樣存在容易陷入局部最優(yōu)的情況，切對于粒子的初始值比較敏感。所以本文結(jié)合GA和PSO算法各自的優(yōu)點，提出一種GA-PSO混合算法，來解決SVM的參數(shù)尋優(yōu)問題，訓練流程如圖3所示。

2.1 GA-PSO混合算法

PSO算法粒子種群由n個粒子組成X=(X1,X2,…,Xn)，每一個粒子位置Xi=(xi1,xi2,…,xiD)，D為解空間的維數(shù)；每一個粒子的速度為Vi=(Vi1,Vi2,…,ViD) ，以K類交叉驗證(cross-validation)[15]正確率作為粒子的適應度函數(shù)P。

圖3 GA-PSO混合算法訓練流程

所謂K類交叉驗證，就是將訓練集平均分為K份，每次取1份作為測試集，剩余的K-1份作為訓練集，然后采用當前的參數(shù)取值，也就是粒子位置Xi=(xi1,xi2,…,xiD)作為訓練參數(shù)時進行模型的建立和對測試集的分類，最后將K個模型的分類正確率平均。個體極值為Pi=(Pi1,Pi2,…,PiD)，全局極值為Pg=(Pg1,Pg2,…,PgD)，粒子的更新公式為

式中：k為種群的當前迭代次數(shù)；c1、c2為加速度常數(shù)；r1、r2為(0,1)之內(nèi)的隨機數(shù)。

粒子的位置變化幅度是由粒子的飛行速度的大小決定的，粒子飛行速度大，能夠在短時間內(nèi)飛到搜索空間中最優(yōu)解的區(qū)域，其全局搜索能力較強，粒子飛行速度較低時，粒子的位置變化幅度較小，有利于增加搜索的精度，局部搜索能力強，全局搜索能力弱。但是，如果粒子的飛行速度一直保持一個較高的值，可能會導致粒子越過最優(yōu)解區(qū)域，飛行速度一直較低的時候，雖然搜索的精度會增加，但是可能導致粒子陷入局部最優(yōu)解。所以對速度更新公式增加了一個加權(quán)系數(shù)：

式中：g為當前迭代次數(shù)；G為最大迭代次數(shù)。以此，粒子在迭代初期能夠保持較高的更新速度，以獲得較強的全局搜索能力，在迭代后期具有較低的更新速度，具有較強的局部搜索能力，w變化曲線如圖4所示。

在算法迭代初期，為了加大粒子的不確定度，增強算法的全局搜索能力參考遺傳算法的機理，對粒子進行變異，具體流程如圖5所示。

圖4 w變化曲線

圖5 粒子變異流程

步驟1設定種群規(guī)模和迭代次數(shù),搜索空間大小和速度大小等參數(shù)。根據(jù)限制隨機初始化粒子的位置X=(X1,X2,…,Xn)和速度V=(V1,V2,…,Vn)。

步驟2根據(jù)每個粒子的位置Xi=(xi1,xi2)對模型進行訓練，將交叉驗證正確率作為該粒子的適應度。

步驟3根據(jù)每個粒子的適應度和其歷史位置上的適應度相比較，將適應度較高的作為新的個體極值Pi=(Pi1,Pi2,…,PiD)。

步驟4根據(jù)每個粒子的適應度和所有粒子經(jīng)過的最優(yōu)適應度相比較，將適應度較高的作為新的全局極值Pg=(Pg1,Pg2,…,PgD)。

步驟5根據(jù)粒子的速度和位置更新公式對粒子進行更新。

步驟6迭代次數(shù)是否滿足條件g<40，若滿足進行步驟7，是否滿足最大迭代次數(shù)，如果滿足，輸出結(jié)果，若不滿足，返回步驟3。

步驟7計算粒子的適應度值，根據(jù)粒子適應度的大小按一定比例選從種群Z取出種群Z2。

步驟8對Z2進行重組交叉。

步驟9對Z2進行變異。

步驟10計算Z2的適應度，根據(jù)適應度重插入種群Z中，保留適應度高的，排除適應度低的。

步驟11返回步驟3。

2.2 算法比較

實驗的相關(guān)參數(shù)設置如表2所示。

采用5-折交叉驗證，分別生成了3組訓練數(shù)據(jù)，比較GA、PSO和GA-PSO 3種算法的尋優(yōu)性能。訓練數(shù)據(jù)為經(jīng)過過濾和歸一化的目標飛機狀態(tài)信息，包含目標飛機的相對位置、相對速度和相對航向角等信息，如表3所示。

記錄訓練過程中的每一代的交叉驗證正確率，針對每組數(shù)據(jù)，采用3種算法分別進行50次尋優(yōu)，記錄訓練過程中每一代的平均正確率。圖6為訓練數(shù)據(jù)樣本為200個的時候，訓練過程中，交叉驗證過程適應度的變化。

將50次的訓練結(jié)果作為參數(shù)去分別訓練SVM模型，并對測試數(shù)據(jù)進行預測分類，測試數(shù)據(jù)為目標飛機相對狀態(tài)信息，其中一半為沖突狀態(tài)，另一半為非沖突狀態(tài)。

平均正確率統(tǒng)計如表4所示。

可以看出，GA-PSO混合算法能夠克服原GA和PSO算法過早收斂的不足。由于尋優(yōu)前期較大的隨機性和隨著訓練代數(shù)而變化的粒子速度。由于GA-PSO混合算法具有較好的全局尋優(yōu)能力，在局部尋優(yōu)時也有較好的準確性，其能夠搜索到更優(yōu)的解。

表2 3種算法參數(shù)

注：N/A表示不適用。

表3 歸一化飛行狀態(tài)

圖6 交叉驗證平均正確率

3 仿真分析

以經(jīng)典的CESSNA 172單引擎飛機作為目標參考(其主要參數(shù)見表5)，生成了4 000個作為訓練數(shù)據(jù)，其中包含2 000個沖突飛機的特征數(shù)據(jù)，2 000個不沖突飛機的特征數(shù)據(jù)，相對位置坐標位于本機水平范圍0.9～3.0 nmi(1 nmi=1.852 km)。選取RBF徑向基核函數(shù)，采用GA-PSO混合算法尋得訓練參數(shù)。

采用蒙特卡羅方法對該方法的性能進行分析，生成測試數(shù)據(jù)一共20組，每組一共包含500個航跡信息，250個沖突航跡和250個不沖突的航跡，航跡的初始相對位置位于本機監(jiān)視范圍1.3～3.0 nm之間，針對每個航跡，進行持續(xù)10 s的檢測時間，監(jiān)視范圍為水平1～3 nm，如果目標飛機位置處于在水平監(jiān)視范圍以外時停止檢測，垂直檢測范圍為1 000 m以下，測試統(tǒng)計結(jié)果如表6所示。

表5 CESSNA 172的尺寸和性能

注：最大承載人數(shù)為4。

表6 用于檢測的統(tǒng)計數(shù)據(jù)

表7 檢測系統(tǒng)性能的統(tǒng)計數(shù)據(jù)

4 結(jié) 論

1) 本文提出的基于SVM的沖突探測算法，將沖突探測問題轉(zhuǎn)化為一個規(guī)劃求解的問題。首先對ADS-B報文數(shù)據(jù)進行篩選和歸一化處理，其次通過GA-PSO混合算法完成SVM的參數(shù)選優(yōu)，并通過先驗信息對SVM進行訓練，最后通過移動加權(quán)平均，優(yōu)化SVM分類判定結(jié)果，實現(xiàn)了基于SVM的飛行沖突探測。

2) 通過對比參數(shù)優(yōu)化及探測能力實驗結(jié)果，GA-PSO混合算法在參數(shù)優(yōu)化上性能優(yōu)良，確保訓練后的SVM在沖突探測時保持了較高的正確率和解算速度，本文算法適用于解決低空復雜飛行沖突探測問題。

參考文獻(References)

[1] GARIEL M,HANSMAN R,FRAZZOLI E.Impact of GPS and ADS-B reported accuracy on conflict detection performance in dense traffic:AIAA-2011-6893[R].Reston：AIAA,2011.

[2] FULTON N L.Airspace design:Towards a rigorous specification of complexity based on computational geometry[J].Aeronautical Journal,1999,103(1020):75-84.

[3] CHIANG,YI J,KLOSOWSKI J,et al.Geometric algorithms for conflict detection and resolution in air traffic management[C]∥36th IEEE Conference on Decision and Control.Piscataway,NJ:IEEE Press,1997,2(2):1835-1840.

[4] MCDONALD J,VIVONA R.Strategic airborne conflict detection of air traffic and area hazards：NAS2-98005[R].Washington,D.C.:NASA,2000.

[5] PRANDINI M,HU J,SASTRY S.A probabilistic approach to aircraft conflict detection[J].IEEE Transactions on Intelligent Transportation Systems,2000,1(4):199-220.

[6] JARDIN M R.Grid-based strategic air traffic conflict detection:AIAA-2005-5826[R].Reston：AIAA,2005.

[7] HU J.Aircraft conflict detection in presence of spatially correlated wind perturbations:AIAA-2003-5339[R].Reston:AIAA,2003.

[8] 李彬,吳珍珍.基于航跡預測的飛行沖突預測[J].微處理機,2011(2):73-80.

LI B,WU Z Z.Flight conflict detection based on flight path prediction[J].Microprocessors,2011(2):73-80(in Chinese).

[9] 韓艷茹,敬忠良,龔嘉琦.空中交通預警與防撞系統(tǒng)(TCAS)風險及對策研究[J].計算機測量與控制,2012,20(3):737-740.

HAN Y R,JING Z L,GONG J Q.Research of traffic alert and collision avoidance system(TCAS) risk and countermeasure[J].Computer Measurement & Control,2012,20(3):737-740(in Chinese).

[10] WILLIAMSON T,SPENCER N A.Development and operation of the traffic alert and collision avoidance system(TCAS)[J].Proceedings of the IEEE,1989,77(11):1735-1744.

[11] 林熙.密集飛行條件下的間隔自主保持方法研究[D].北京：北京航空航天大學,2011:11-13.

LIN X.Research on self-separation assurance methods in condition of intensive flight[D].Beijing:Beihang University,2011:11-13(in Chinese).

[12] LIN C E.Collision avoidance solution for low-altitude flights[J].Proceedings of the Institution of Mechanical Engineers,Part G:Journal of Aerospace Engineering,2011,225(7):779-790.

[13] JIAO Y L,ZHANG X J,GUAN X M.An algorithm for airborne conflict detection based on support vector machine[J].Applied Mechanics and Materials,2012,229-231:1140-1145.

[14] CORTES C,VAPNIK V.Support-vector networks[J].Machine Learning,1995,20(3):273-276.

[15] KOHAVI R.A study of cross-validation and bootstrap for accuracy estimation and model selection[C]∥Proceedings of the 14th International Joint Conference on Artificial Intelligence.New York:ACM,1995:1137-1143.