基于蟻群聚類算法的扇區(qū)復(fù)雜性分析

朱承元，孫辰欣，趙立剛

(1. 中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300；2. 民航局空管局空域管理中心，北京 101312)

1 引言

在經(jīng)濟(jì)快速發(fā)展的大環(huán)境下，民航業(yè)前景廣闊，航班量持續(xù)增長(zhǎng)，扇區(qū)運(yùn)行環(huán)境愈加復(fù)雜。由于不同空域單元的運(yùn)行環(huán)境存在差異性，導(dǎo)致空中交通復(fù)雜性不同，扇區(qū)復(fù)雜程度的變化對(duì)空中交通管理系統(tǒng)的運(yùn)行效率和安全性產(chǎn)生較大的影響。因此，如何科學(xué)客觀分類空域單元的復(fù)雜性，成為空域和飛行流量管理的重要基礎(chǔ)，也成為空管單位關(guān)注的焦點(diǎn)。

Christien.Rapha?l等[1]和Arash Yousefi等[2]提煉扇區(qū)結(jié)構(gòu)、沖突類型、流量等指標(biāo)，通過聚類分析不同地區(qū)的扇區(qū)得到交通運(yùn)行模式分類。Song Zhuoxi等[3]通過仿真工具對(duì)扇區(qū)運(yùn)行情況進(jìn)行模擬，提取影響空域復(fù)雜性的指標(biāo)。張進(jìn)等[4]基于空域復(fù)雜度度量指標(biāo)體系分析了空中交通系統(tǒng)的運(yùn)行特征。復(fù)雜性與眾多影響因素相關(guān)，以上文獻(xiàn)度量空域復(fù)雜性的指標(biāo)還未十分完善。Geraldine M Flynn等[5]和Steve Penny等[6]利用決策樹和K均值法對(duì)空域單元復(fù)雜性按高、中、低進(jìn)行聚類分析，張建平等[7]，趙嶷飛等[8]和叢瑋等[9]采用K均值算法分別對(duì)終端區(qū)的運(yùn)行品質(zhì)、交通流運(yùn)行特性和扇區(qū)復(fù)雜程度進(jìn)行聚類分析，上述文獻(xiàn)采用傳統(tǒng)聚類算法運(yùn)行效率較高，但K-means算法易受極值影響產(chǎn)生局部最優(yōu)，對(duì)數(shù)據(jù)量較大的聚類問題會(huì)產(chǎn)生較高的難度，并且大多數(shù)學(xué)者對(duì)空域進(jìn)行簡(jiǎn)單的定性分析，未對(duì)聚類結(jié)果進(jìn)行驗(yàn)證，具有主觀隨意性。當(dāng)前，群智能聚類算法的研究受到學(xué)者關(guān)注，李可[10]通過蟻群算法對(duì)航線進(jìn)行聚類，但缺乏對(duì)聚類結(jié)果準(zhǔn)確性的驗(yàn)證。

因此，在扇區(qū)復(fù)雜性指標(biāo)體系的基礎(chǔ)上，選擇蟻群聚類算法對(duì)扇區(qū)的復(fù)雜性進(jìn)行聚類分析，利用螞蟻的生物屬性提高全局搜索能力和收斂速度，選擇Silhouette指標(biāo)評(píng)估聚類質(zhì)量，得到扇區(qū)復(fù)雜性的復(fù)雜程度分類，最終通過全空域與機(jī)場(chǎng)仿真軟件(TAAM,Total Airspace and Airport Modeler)對(duì)聚類結(jié)果進(jìn)行驗(yàn)證。

2 扇區(qū)復(fù)雜性指標(biāo)與分析

2.1 指標(biāo)體系

復(fù)雜性的相關(guān)研究甚多，借鑒已有研究成果[11]，結(jié)合空域結(jié)構(gòu)和動(dòng)態(tài)運(yùn)行特征，提取有利于定量分析空域運(yùn)行態(tài)勢(shì)的復(fù)雜性指標(biāo)，構(gòu)建能夠反映空域運(yùn)行特征的復(fù)雜性指標(biāo)體系見表1。

表1 復(fù)雜性指標(biāo)體系

綜上，根據(jù)空域結(jié)構(gòu)的特點(diǎn)和空域交通運(yùn)行確定復(fù)雜性指標(biāo)，該指標(biāo)體系主要功能是深入分析考慮空中交通復(fù)雜度與空域狀態(tài)變化，全面度量空域復(fù)雜性，在這一指標(biāo)體系的基礎(chǔ)上，進(jìn)一步將空中交通復(fù)雜性的方法進(jìn)行更深入研究。

2.2 主成分分析

扇區(qū)管制運(yùn)行態(tài)勢(shì)復(fù)雜，考慮因素多，需要結(jié)合實(shí)際運(yùn)行選取有效指標(biāo)進(jìn)行分析，提煉出能有效表征復(fù)雜性的指標(biāo)，通過主成分分析法(PCA,Principal Components Analysis)精簡(jiǎn)出可定量分析復(fù)雜性的指標(biāo)。主成分的數(shù)學(xué)模型如下：

∑=(σij)p=E[(X-E(X))(X-E(X))T]

(1)

(2)

4)樣本X的第q個(gè)主成分表示為

Yi=li1X1+li2X2+…+lipXp(q=1，2，…，p)

(3)

3 蟻群聚類算法

針對(duì)傳統(tǒng)K-means算法易產(chǎn)生局部最優(yōu)解的缺陷，蟻群聚類算法(ACCA,ant colony clustering algorithm)是一種基于種群尋優(yōu)的搜索算法[12]，螞蟻利用自身的生物特征屬性，通過信息素強(qiáng)度分布式尋優(yōu)，在搜索過程中不容易陷入局部最優(yōu)，同時(shí)貪婪式搜索有利于快速找出可行解。

3.1 聚類算法流程

螞蟻在群體進(jìn)化過程中主要是螞蟻的記憶、螞蟻之間的信息交流及群體向目標(biāo)靠近，最終尋找到食物源。

設(shè)X={Xi|Xi=(xi1，xi2，…，xin)|(i=1，2，…，N)是待聚類分析的樣品集合，N為樣品的特征數(shù)，聚類過程可表述如下：

1) 初始分配N個(gè)樣品各自為一類(ω1，ω2，…，ωN)。

2) 計(jì)算類ωi和ωj之間的歐式距離dij。

(4)

(5)

3) 計(jì)算各路徑上的信息素量。設(shè)r為聚類半徑，τij(t)是t時(shí)刻ωi到ωj路徑上殘留的信息素量，路徑(i，j)上的信息素量定義為

(6)

式中，r=A+dmin+(dmax-dmin)·B，A，B為常量參數(shù)，dmin=min(dij)，dmax=max(dij)。

4) 計(jì)算類ωi歸并到ωj的概率

(7)

式中，S={s|dij≤r，s=1，2，…，j-1，j+1，M}，s代表某一類號(hào)，S代表到第j類距離小于等于r的所有類號(hào)集合，M為當(dāng)前的總類數(shù),α表示信息素啟發(fā)因子，β期望啟發(fā)因子，ηij(t)=1/dij為啟發(fā)函數(shù)。

5) 判斷若Pij(t)≥p0，則ωi歸并到ωj鄰域，類別數(shù)減1。p0為一給定的概率值。

6) 判斷是否有歸并。若無(wú)歸并，則停止循環(huán)。否則，轉(zhuǎn)2)繼續(xù)迭代，直至達(dá)到最大迭代次數(shù)，返回最優(yōu)解為聚類結(jié)果[13]。

3.2 聚類評(píng)價(jià)指標(biāo)

由于聚類是無(wú)監(jiān)督學(xué)習(xí)過程，無(wú)法確定某種劃分結(jié)果是合理有效的，聚類評(píng)價(jià)指標(biāo)對(duì)數(shù)據(jù)集本身的內(nèi)部結(jié)構(gòu)、相似關(guān)系和簇類之間的緊湊與疏遠(yuǎn)關(guān)系進(jìn)行評(píng)價(jià)[14]，選擇Silhouette指標(biāo)分析評(píng)價(jià)聚類質(zhì)量。

假設(shè)某個(gè)樣本集合具有n個(gè)樣本點(diǎn)，被聚合為k個(gè)類別Ci(i=1，2，…，k)。a(t)為類別C中的樣本點(diǎn)t與t相同的群集中其他點(diǎn)的平均距離，b(t)是從第i個(gè)點(diǎn)到不同群集中的點(diǎn)的最小平均距離，d(t，Ci)為Cj的樣本t到另一個(gè)類Ci的所有樣本的平均不相似度或距離，則b(t)=min{d(t，Ci)}，其中i=1,2,…,k且i≠j。樣本t的Silhouette指標(biāo)的計(jì)算公式如下

(8)

輪廓值范圍是[-1，1]，如果樣本點(diǎn)的輪廓值越大，則聚類效果更好。

3.3 實(shí)例分析

針對(duì)扇區(qū)復(fù)雜性進(jìn)行聚類時(shí)，空域仿真模型的準(zhǔn)確性對(duì)最終的聚類結(jié)果有很大影響，TAAM仿真工具能夠還原空域動(dòng)態(tài)運(yùn)行的全過程。以西安和杭州進(jìn)近管制扇區(qū)作為對(duì)象，選擇某天的航班計(jì)劃數(shù)據(jù)，將航路點(diǎn)、航路、進(jìn)離場(chǎng)程序及扇區(qū)等錄入到仿真中，構(gòu)建空域復(fù)雜性模型，并對(duì)模型進(jìn)行校驗(yàn)，空域運(yùn)行效果與實(shí)際相符。

采集扇區(qū)復(fù)雜性仿真數(shù)據(jù)用于指標(biāo)分析，9個(gè)扇區(qū)作為分析樣本，用S1-S9表示，通過對(duì)交通流的時(shí)空分布進(jìn)行統(tǒng)計(jì)和分析，采集指標(biāo)分別為Z1～Z16見表2和表3。

表2 靜態(tài)復(fù)雜性指標(biāo)數(shù)據(jù)

表3 動(dòng)態(tài)復(fù)雜性指標(biāo)數(shù)據(jù)

通過PCA分析，靜態(tài)復(fù)雜性前兩個(gè)主成分貢獻(xiàn)率為0.9529+0.047=0.99，累計(jì)已達(dá)99%以上，提取Z1和Z2兩個(gè)主成分。動(dòng)態(tài)運(yùn)行復(fù)雜性前三個(gè)主成分貢獻(xiàn)率計(jì)算為0.726+0.164+0.082=0.972，累計(jì)已達(dá)97%，因此提取了Z6、Z7和Z8三個(gè)主成分。

通過主成分分析提取指標(biāo)數(shù)據(jù)，得到扇區(qū)的復(fù)雜性見表4。

表4 主成分分析

綜合兩類復(fù)雜性值對(duì)扇區(qū)分別通過K-means和ACCA進(jìn)行對(duì)比分析，結(jié)果見表5。初始化螞蟻個(gè)數(shù)為9，最大迭代次數(shù)為50，設(shè)置參數(shù)A=0.2，B=0.28，α=1，β=1。τij(0)=0，轉(zhuǎn)移概率p0=0.65，樣本數(shù)為9，當(dāng)K=2-8之間時(shí)，對(duì)應(yīng)不同的Silhouette值如圖1。

表5 聚類數(shù)據(jù)對(duì)比

圖1 Silhouette指標(biāo)評(píng)價(jià)圖

從表5和圖1中得到，K-means得到的質(zhì)心大致正確，但不精確，運(yùn)行時(shí)間較長(zhǎng)，受質(zhì)心位置影響容易產(chǎn)生局部最優(yōu)解；ACCA的質(zhì)心位置準(zhǔn)確，聚類有效性好，時(shí)間性能表現(xiàn)的較好。因此，采用的ACCA的聚類效果要比K-means好，分類更加合理。

從評(píng)價(jià)指標(biāo)來(lái)看，當(dāng)Silhouette值越大時(shí)，聚類效果越好。兩種算法對(duì)比來(lái)看，當(dāng)K=3時(shí)，通過蟻群聚類算法的輪廓值值最大，所以根據(jù)扇區(qū)復(fù)雜性將扇區(qū)分為3類，比較符合實(shí)際的管制情況。

當(dāng)K=3時(shí)蟻群聚類得到的復(fù)雜性結(jié)果如圖2。

圖2 K=3的聚類結(jié)果圖

根據(jù)復(fù)雜程度將扇區(qū)分為3類，分別為：Sector 3/7(復(fù)雜)；Sector2/5/6/8/9(中等)；Sector 1/4(低)。其中：

1)Sector3/7的復(fù)雜程度都屬于最大值。從靜態(tài)結(jié)構(gòu)來(lái)看，受地理位置的限制，可用空間小，矛盾點(diǎn)較多，可調(diào)配的機(jī)動(dòng)空域面積??；從運(yùn)行狀態(tài)看，該類扇區(qū)航空器分布最為密集，處于進(jìn)離場(chǎng)的交匯處，大部分航空器處于爬升、下降狀態(tài)。航空器對(duì)之間的平均時(shí)間間隔最少，存在潛在沖突多，管制員同時(shí)指揮架次較高，造成管制員負(fù)荷最大。

2)Sector2/5/6/8/9的復(fù)雜程度都屬于中等水平。從靜態(tài)結(jié)構(gòu)來(lái)看，扇區(qū)面積較大，靈活調(diào)配空間，航路匯聚交叉點(diǎn)多；從運(yùn)行狀態(tài)看，該類扇區(qū)的航空器數(shù)量分布較多，產(chǎn)生的沖突較多，對(duì)航空器引導(dǎo)機(jī)動(dòng)較多，航空器對(duì)之間的時(shí)間間隔分布有所提高。

3)Sector1/4的復(fù)雜程度屬于低水平。從靜態(tài)結(jié)構(gòu)來(lái)看，扇區(qū)結(jié)構(gòu)限制較少，航路分布較簡(jiǎn)單。從運(yùn)行狀態(tài)看，扇區(qū)內(nèi)航班流分布最少，航空器對(duì)之間的時(shí)間間隔最大，航空器之間的沖突較少。

4 仿真驗(yàn)證

TAAM仿真軟件中的空域復(fù)雜性可視化工具TAAM Viewer能夠以3D形式顯示模擬輸出報(bào)告數(shù)據(jù)。扇區(qū)復(fù)雜性信息分析航空器在空域運(yùn)行時(shí)的相互作用，以及它對(duì)管制員工作負(fù)荷和沖突等度量的影響。復(fù)雜性信息由扇區(qū)顏色的變化顯示，可以實(shí)時(shí)觀測(cè)到不同時(shí)段各個(gè)扇區(qū)的復(fù)雜程度，綠色表示扇區(qū)的復(fù)雜程度最低，黃色表示扇區(qū)復(fù)雜程度中等，紅色表示扇區(qū)復(fù)雜程度最高。

如圖3和圖4所示，將西安和杭州進(jìn)近管制扇區(qū)復(fù)雜性投影到一個(gè)平面中進(jìn)行動(dòng)態(tài)顯示，連續(xù)不斷地展示整個(gè)空域復(fù)雜性的傳播。

圖3 西安扇區(qū)復(fù)雜性

圖4 杭州扇區(qū)復(fù)雜性

仿真結(jié)果表明，不同時(shí)段的扇區(qū)顏色變化分類與ACCA聚類結(jié)果一致，扇區(qū)復(fù)雜程度分類結(jié)果與聚類結(jié)果相符，從客觀角度確認(rèn)了該聚類結(jié)果和方法的合理性。

5 結(jié)論

在扇區(qū)復(fù)雜性指標(biāo)體系的基礎(chǔ)上，采用蟻群聚類算法使用信息素強(qiáng)度作為判斷函數(shù)，實(shí)現(xiàn)了扇區(qū)的復(fù)雜程度分類，表明了ACCA算法的有效性和可靠性，準(zhǔn)確地揭示數(shù)據(jù)間的復(fù)雜關(guān)系，并通過TAAM仿真軟件對(duì)聚類結(jié)果準(zhǔn)確性進(jìn)行驗(yàn)證。研究成果有助于加強(qiáng)空域系統(tǒng)的運(yùn)行效率，提升空域運(yùn)行安全性，為其規(guī)劃與管理起到?jīng)Q策支持作用。

未來(lái)研究中，進(jìn)一步可以將聚類算法與其他群智能算法結(jié)合開展深入研究，構(gòu)造出更為優(yōu)良的聚類改進(jìn)方法，將實(shí)現(xiàn)更多指導(dǎo)意義。