王潔寧，袁志娟

（中國(guó)民航大學(xué)空中交通管理研究基地，天津 300300）

基于粒子群算法的飛行沖突解脫問題

王潔寧，袁志娟

（中國(guó)民航大學(xué)空中交通管理研究基地，天津 300300）

自由飛行可有效解決航線日益加劇的擁擠問題，但同時(shí)也增加了管制員管制監(jiān)控的難度，從而使飛行沖突探測(cè)和解脫成為自由飛行的關(guān)鍵問題。粒子群算法（particle swarm optimization）是一種群智能優(yōu)化算法，嘗試將其應(yīng)用于飛行沖突解脫問題，構(gòu)造了適合飛行沖突解脫問題的粒子表達(dá)方式，建立了沖突解脫問題的粒子群算法，成功解決了飛行沖突，并將其運(yùn)行結(jié)果與遺傳算法結(jié)果作了對(duì)比試驗(yàn)。實(shí)驗(yàn)結(jié)果表明，粒子群算法是求解飛行沖突解脫問題的一個(gè)較好方案。

空中交通管理；飛行沖突探測(cè)與解脫；粒子群算法；自由飛行；遺傳算法

隨著民航運(yùn)輸業(yè)的快速發(fā)展，空中交通流量不斷增加，導(dǎo)致由扇區(qū)和航路組成的空域嚴(yán)重超載。為了從根本上解決空中交通的擁擠狀況，從20世紀(jì)90年代開始，美國(guó)等一些航空發(fā)達(dá)國(guó)家提出了“自由飛行”的概念，即飛行員可自主選擇飛行速度、飛行高度和飛行航線。自由飛行能夠使航班自由選取最快、最直接的路徑，提高空域利用率。但自由飛行使空中交通管制變得復(fù)雜，增加了空中交通管制的難度。因此，飛行沖突的探測(cè)和解脫問題的研究變得異常重要。世界各國(guó)的研究者做了大量這方面的研究工作并提出了幾種方法，概括起來大致可分為6類：①基于遺傳算法的沖突探測(cè)與解脫[1-4]；②神經(jīng)網(wǎng)絡(luò)模型[5]；③非結(jié)構(gòu)網(wǎng)格生成的沖突探測(cè)方法[6]；④人工勢(shì)場(chǎng)法解決飛行沖突[7]；⑤Delaunay方法用于沖突探測(cè)[8]；⑥線性規(guī)劃法用于沖突解脫[9]。本文提出使用粒子群優(yōu)化算法解決自由飛行中的飛行沖突問題，并與GA（遺傳算法）[4]進(jìn)行了比較。

1 粒子群算法

粒子群算法（particle swarm optimization，PSO）于1995年由Kennedy和Eberhart提出，該算法模擬鳥群飛行覓食的行為，通過鳥的集體協(xié)作使群體達(dá)到最優(yōu)[10]。在PSO系統(tǒng)中，每個(gè)可行解被稱為一個(gè)“粒子”（particle），多個(gè)粒子共存、合作尋優(yōu)。每個(gè)粒子根據(jù)自身經(jīng)驗(yàn)和群體最優(yōu)經(jīng)驗(yàn)在問題域中向更好的位置“飛行”，搜索最優(yōu)解。

PSO算法解析如下[11]：

設(shè)搜索空間為D維，總粒子數(shù)為n。第i個(gè)粒子位置表示為向量 Xi=（xi1，xi2，…，xiD）；第 i個(gè)粒子“飛行”歷史中的最優(yōu)位置為 Pi=（pi1，pi2，…，piD），其中第 g 個(gè)粒子的歷史最優(yōu)位置Pg為所有Pi（i=1，2，…，n）中的最優(yōu)；第i個(gè)粒子的位置變化率（速度）為向量Vi=（vi1，vi2，…，viD）。每個(gè)粒子的位置按如下公式進(jìn)行變化

式中：c1、c2為正常數(shù)，稱為加速因子；rand（）為[0，1]之間的隨機(jī)數(shù)；w稱為慣性因子。第d（1≤d≤D）維的位置變化范圍為[-Xmaxd，Xmaxd]，速度變化范圍為[-Vmaxd，Vmaxd]，迭代中若位置和速度超過邊界范圍則取邊界值。

粒子群初始位置和速度隨機(jī)產(chǎn)生，然后按式（1）、式（2）進(jìn)行迭代，直至找到滿意的解。目前，常用的粒子群算法將全體粒子群（global）分成若干個(gè)有部分粒子重疊的相鄰子群（1ocal）。Kennedy提出了多種鄰接子群拓?fù)浣Y(jié)構(gòu)[12]，如 Ring 型、Wheel型、Star型等，并做了相關(guān)分析。每個(gè)粒子根據(jù)各子群的歷史最優(yōu)Pp調(diào)整速度和位置，即將式（1）中pgd換為ppd。PSO算法基本流程如下：

1）隨機(jī)初始化粒子群的位置和速度。

2）計(jì)算每個(gè)粒子的適應(yīng)值。

3）對(duì)于每個(gè)粒子將其適應(yīng)值與其所經(jīng)歷過的最好位置Pi的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前最好位置。

4）對(duì)于每個(gè)粒子將其個(gè)體歷史最優(yōu)適應(yīng)值與群體歷史最優(yōu)位置Pg（或Pp）的適應(yīng)值進(jìn)行比較，若更好，則將其作為群體最優(yōu)位置。

5）按式（1）更新粒子速度，按式（2）更新粒子位置，超出邊界按邊界取值。

6）未滿足停止條件，則返回步驟2）。

近些年的研究和實(shí)踐表明，PSO在多維空間多峰問題尋優(yōu)、動(dòng)態(tài)目標(biāo)尋優(yōu)方面有著速度快、解質(zhì)量高、魯棒性好等優(yōu)點(diǎn)[11]。

2 問題描述

根據(jù)中國(guó)空管安全規(guī)定，雷達(dá)管制條件下，巡航階段兩架航班之間的間隔不小于20 km時(shí)，不存在飛行沖突。飛行沖突問題的一種常見描述為：在一個(gè)邊長(zhǎng)為200 km的正方形扇區(qū)內(nèi)，一架飛機(jī)由南向北飛行，而另一架飛機(jī)由西向東飛行。在保證間隔的條件下，對(duì)問題進(jìn)行簡(jiǎn)化[4，9，13]，即：在巡航階段，通常航班只采用改變水平方向進(jìn)行避障，因此問題可簡(jiǎn)化為一個(gè)二維問題。同時(shí)為了避障時(shí)不做大角度轉(zhuǎn)彎的機(jī)動(dòng)動(dòng)作，在此假設(shè)航班只選擇左偏30°、右偏30°和直飛3個(gè)機(jī)動(dòng)動(dòng)作飛行。假設(shè)飛行速度不變，本文對(duì)于該假設(shè)條件在問題求解時(shí)做了適當(dāng)?shù)膬?yōu)化，即文獻(xiàn)中假設(shè)的飛行速度不變[4，9，13]，只表示飛機(jī)在所飛方向上的速度分量不變。為了保持該速度分量不變，航班右偏或左偏都會(huì)導(dǎo)致實(shí)際飛行速度的增大，也就是航班的速率隨航班的偏轉(zhuǎn)而發(fā)生變化，本文采用嚴(yán)格按照實(shí)際飛行速度不變的假設(shè)對(duì)問題進(jìn)行分析。

為計(jì)算方便，每架航班在在扇區(qū)內(nèi)都設(shè)一個(gè)理論進(jìn)入點(diǎn)和退出點(diǎn)，為簡(jiǎn)化問題，假設(shè)所有飛機(jī)在同一時(shí)間進(jìn)入扇區(qū)。設(shè)步長(zhǎng)為s=10 km，每一步在起始點(diǎn)處調(diào)整好航向。任意兩架航班在任何時(shí)候的間隔小于20 km即為飛行沖突。為避免沖突，需進(jìn)行航線調(diào)整，此時(shí)飛行軌跡最優(yōu)化的目的是所有航班通過該扇區(qū)的總距離最短。

3 飛行沖突解脫問題粒子群算法

3.1 模型建立

本文采用文獻(xiàn)[4]所提出的K架航班進(jìn)入扇區(qū)的數(shù)學(xué)模型。目標(biāo)是在保證不發(fā)生飛行沖突的情況下，總航線長(zhǎng)度最短，即

在此任意兩架航班滿足

式（3）中：K為同時(shí)進(jìn)入扇區(qū)的航班架次；Si為第i架航班在該扇區(qū)內(nèi)的航線長(zhǎng)度。式（4）中：（xi，yi）和（xj，yj）分別表示第i架和第j架航班在該扇區(qū)內(nèi)的位置。

3.2 構(gòu)造粒子表達(dá)方式及其約束下模型的改進(jìn)

本文構(gòu)造一個(gè)K×L維空間，其中：K為航班數(shù)，L=20為各航班在本扇區(qū)內(nèi)的步長(zhǎng)數(shù)。將每個(gè)粒子對(duì)應(yīng)的K×L維向量X分解成K個(gè)L維向量：Xk=（xk1，xk2，…，xkL）（k=1，2，…，K），表示第 k 架航班在本扇區(qū)內(nèi)的飛行軌跡。每個(gè)粒子的速度向量V與之對(duì)應(yīng)表示為：Vk=（vk1，vk2，…，vkL）（k=1，2，…，K）。其中

需滿足式（6）～式（9）的約束條件

分別表示第l步時(shí)兩架航班的位置。

其中：式（7）限制所有航班均在扇區(qū)理論退出點(diǎn)離開扇區(qū)；式（8）、式（9）限制連續(xù)兩步的最大轉(zhuǎn)彎角度為30°。因式（9）限制 xkl只能取 1、0 或 －1，所以式（5）～式（9）所描述的飛行沖突解脫模型為整數(shù)規(guī)劃模型。

3.3 算法實(shí)現(xiàn)過程

由于前文所介紹的PSO算法為連續(xù)空間算法，而兩個(gè)航班的沖突解脫問題是整數(shù)規(guī)劃問題，因此對(duì)算法實(shí)現(xiàn)過程做了適當(dāng)修改。

步驟1 初始化粒子群。

1）將粒子群劃分成兩兩重疊的子群；

2）每個(gè)粒子的Xk（k=1，2）的每一維隨機(jī)取{－1，0，1}；

3）每個(gè)速度向量 Vk（k=1，2）的每一維隨機(jī)?。?～2之間的實(shí)數(shù)；

4）用評(píng)價(jià)函數(shù)EVAL評(píng)價(jià)所有粒子，即計(jì)算各個(gè)粒子的目標(biāo)函數(shù)值；

5）將初始值作為個(gè)體歷史最優(yōu)Pi和各子群歷史最優(yōu)Pp及群體歷史最優(yōu)Pg。

步驟2 循環(huán)以下步驟，直到滿足終止條件。

1）對(duì)每個(gè)粒子按照式（1）計(jì)算 V，按式（2）計(jì)算 X；

2）用評(píng)價(jià)函數(shù)EVAL評(píng)價(jià)所有粒子；

3）若某個(gè)粒子的當(dāng)前評(píng)價(jià)值優(yōu)于其歷史最優(yōu)評(píng)價(jià)值，則記當(dāng)前評(píng)價(jià)值為該歷史最優(yōu)評(píng)價(jià)值，同時(shí)記當(dāng)前位置為該粒子歷史最優(yōu)位置Pi；

4）尋找當(dāng)前各子群最優(yōu)解和總?cè)后w最優(yōu)解，若優(yōu)于歷史最優(yōu)解則更新Pp、Pg。

其中，評(píng)價(jià)函數(shù)EVAL完成的任務(wù)為：

1）計(jì)算該粒子代表方案的轉(zhuǎn)彎次數(shù)Z。若某個(gè)粒子所代表的路徑為不可行解，則把該方案的評(píng)價(jià)值置為不可達(dá)到的大值，如該問題總的步驟數(shù)為K×L=40，則置不可行解的評(píng)價(jià)值為大于40的值。實(shí)驗(yàn)中取不可達(dá)到的大值為100。

2）對(duì)于迭代計(jì)算中的X，若X中某一維的值大于等于1時(shí)取值為1，值在（－1，1）之間時(shí)取0，值小于等于－1時(shí)取值為－1。

4 實(shí)驗(yàn)結(jié)果及分析

為便于比較結(jié)果，用Matlab 7.0編寫飛行沖突解脫問題的PSO和GA程序。其中參數(shù)取值如下：

GA參數(shù)[4]：群體規(guī)模n=1000；交叉因素Pc=40%；突變因素Pm=5%。

PSO參數(shù)[12]：粒子數(shù)n=40；分為2個(gè)子群，群體規(guī)模為 21，重疊粒子為 2；w=0.729；c1=c2=1.494 45；最大迭代次數(shù)為200。

將GA算法和PSO算法實(shí)現(xiàn)過程分別在Matlab 7.0中運(yùn)行100次，結(jié)果對(duì)比如表1所示，兩種算法的最優(yōu)運(yùn)行結(jié)果如圖1和圖2所示。

從表1可以看出，PSO搜索成功率在轉(zhuǎn)彎次數(shù)≤12時(shí)高達(dá)68%，而GA只成功搜索22次，比率為22%；且兩者搜索總時(shí)間差距不大。由圖1、圖2顯示的算法最優(yōu)運(yùn)行結(jié)果可知：①本文通過對(duì)問題的優(yōu)化改進(jìn)使其更符合實(shí)際情況、更直觀，粗實(shí)線部分即為調(diào)整后航班比直線飛行時(shí)多飛的距離；②扇區(qū)內(nèi)遺傳

表1GA和PSO運(yùn)行結(jié)果對(duì)比Tab.1 Comparison of GA and PSO algorithm′s running results

5 結(jié)語

本文針對(duì)自由飛行條件下扇區(qū)內(nèi)的飛行沖突問題，提出利用粒子群算法的思想，構(gòu)造了適合該問題的粒子表達(dá)方式，同時(shí)建立了在該粒子表達(dá)方式下的數(shù)學(xué)模型，從而構(gòu)建了飛行沖突解脫問題的粒子群算法，有效解決了兩架航班在扇區(qū)內(nèi)的飛行沖突。

分析粒子群算法實(shí)現(xiàn)過程可以看出，每個(gè)粒子均能夠直接獲取群體和個(gè)體歷史經(jīng)驗(yàn)，比遺傳算法更有效；把粒子劃分為幾個(gè)子群，且子群之間相互重疊，從而降低了收斂于局部最優(yōu)的可能性。因此，把粒子群算法應(yīng)用到飛行沖突解脫問題的求解中，取得了比較好的效果。但隨著航班數(shù)量的增加，將會(huì)出現(xiàn)許多新的問題，有待不斷深入研究和探索。

[1]ALLIOT J M，GRUBER H，JOLY G，et al．Genetic Algorithms for Solving Air Traffic Control Conflicts[C]//The Ninth Conference on Artificial Intelligence for Applications，1993：338-344.

[2]NEERASOOD，SANDEEP MULGUND，CRAIG WANKE，et al．A Multi-Objective Genetic Algorithm for Solving Airspace Congestion Problems[C]//AIAA Guidance，Navigation and Control Conference，2007.

[3]VORMER F J，MULDER M，VAN PAASSEN M M，et al．Optimization of flexible approach trajectories using a genetic algorithm[J].Journal of Aircraft，2006，43（4）：941-952.

[4] 劉 星，胡明華，董襄寧．遺傳算法在飛行沖突解脫中的應(yīng)用[J]．南京航空航天大學(xué)學(xué)報(bào)，2002，34（1）：35-38.

[5] BURDUN I Y．An AI Situational Pilot Model for Real-Time Applications[C]//Proceedings of the 20th Congress of the International Council of the Aeronautical Sciences，Sorrento，Napoli，Italy，September 8-13，1996：210-237.

[6] FULTON N L．Airspace design：towards a rigorous specification of complexity based on computational geometry[J]．Aeronautical Journal，1999，103（1020）：75-84.

[7] 郭 茜，聶潤(rùn)兔.改進(jìn)人工勢(shì)場(chǎng)法在解決飛行沖突問題中的應(yīng)用[J].交通與計(jì)算機(jī)，2008，26（5）：103-106.

[8] 劉 星，韓松臣．用于自由飛行沖突探測(cè)的Delaunay方法[J]．?dāng)?shù)據(jù)采集與處理，2002，17（4）：446-449．

[9] 靳學(xué)梅，韓松臣，孫樊榮．自由飛行中沖突解脫的線性規(guī)劃法[J]．交通運(yùn)輸工程學(xué)報(bào)，2003，3（2）：75-79．

[10]KENNEDY J，EBERHART R C．Particle Swarm Optimization[C]//Proc IEEE International Conference on Neural Networks：Ⅳ．Piscataway，NJ：IEEE Service Center，1995：1942-1948．

[11] EBERHART R C，SHI Y．Particle Swarm Optimization：Developments，Applications and Resources[C]//Proc Congress on Evolutionary Computation 2001．Piscataway，NJ：IEEE Press，2001：81-86．

[12] KENNEDY J．Small Worlds and Mega-Minds：Effects of Neighborhood Topology on Particle Swarm Performance[C]//Proceedings of the Congress on Evolutionary Computation．Piscataway，NJ：IEEE Press，1999：1931-1938．

[13]楊尚文，戴福青.基于一種免疫遺傳算法的自由飛行沖突解脫[J].航空計(jì)算技術(shù)，2007，37（1）：41-43.

Study on Resolution of Flight Conflicts Based on Particle Swarm Optimization

WANG Jie-ning，YUAN Zhi-juan
（Air Traffic Management Research Base，CAUC，Tianjin 300300，China）

Free flight is a conceptual operation in solving the increasing air traffic congestions；however it would make the air controller more difficult to make decisions to optimize conflict resolution.PSO（particle swarm optimization）is a swarm intelligence optimization.In this paper，PSO is attempted to be used to solve the conflict resolution.This paper proposes a novel particle presentation for the conflict resolution，establishes a PSO algorithm for this kind of problem，solves the conflict in flight successfully，and compares with GA in the same conflict resolution experiments.Experimental results show that the PSO is an effective method in solving the conflict resolution problem.

air traffic management；conflict detection and resolution；particle swarm optimization；free flight；genetic algorithm

V355.1

A

1674－5590（2010）04－0001－04

2009-12-04；

2010-03-11

國(guó)家自然科學(xué)基金項(xiàng)目（60832011）；中國(guó)民航大學(xué)博士啟動(dòng)基金項(xiàng)目（06QD07S）

王潔寧（1966—），男，甘肅蘭州人，研究員，博士，研究方向?yàn)榭罩薪煌髁抗芾?、空管信息系統(tǒng).

（責(zé)任編輯：黨亞茹）