基于遺傳粒子群算法的飛行沖突解脫

崔莉薇，石為人，劉祥明，吳文政

重慶大學(xué) 自動(dòng)化學(xué)院，重慶 400030

隨著民航運(yùn)輸事業(yè)的高速發(fā)展，空中交通流量不斷增加，為了改善日益擁擠的空中交通狀況，國(guó)際民航界提出了“自由飛行”的概念，所謂自由飛行就是指說(shuō)駕駛員可以選擇最合適的飛行路線和飛行速度進(jìn)行飛行。在自由飛行環(huán)境下，航路擁擠問(wèn)題將得到改善，但航路結(jié)構(gòu)限制的取消，使得航空器間沖突問(wèn)題的解決將變得異常復(fù)雜，管制員的工作也將變得更加復(fù)雜困難。自由飛行條件下的沖突探測(cè)與解脫近年來(lái)成為空中交通管理領(lǐng)域的一個(gè)研究熱點(diǎn)。

各國(guó)的研究人員進(jìn)行了大量沖突解脫算法的研究工作。ALLIOT[1]論述了基于遺傳算法的解脫方法，該算法可以獲得最短航跡的無(wú)沖突飛行方案，但當(dāng)飛機(jī)數(shù)目增多時(shí)計(jì)算比較復(fù)雜、耗費(fèi)時(shí)間多。Durand[2]運(yùn)用簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)來(lái)解決兩機(jī)間的沖突，可以得到滿意的結(jié)果，但當(dāng)沖突的飛機(jī)多于兩架時(shí)，神經(jīng)網(wǎng)絡(luò)拓展十分困難，三機(jī)比兩機(jī)的學(xué)習(xí)結(jié)構(gòu)適應(yīng)性差，而且三機(jī)以上的拓展使神經(jīng)網(wǎng)絡(luò)的規(guī)模增加，學(xué)習(xí)更困難。Ghosh[3]采用勢(shì)能法解決飛行沖突，算法簡(jiǎn)單，計(jì)算速度快，但該算沒(méi)有考慮解脫航跡長(zhǎng)度與燃油消耗等因素，且隨著飛機(jī)架數(shù)的增加，可能會(huì)規(guī)劃出不適合實(shí)際飛機(jī)航行的航跡。國(guó)內(nèi)對(duì)飛行沖突解脫的研究也取得了一定的成果，嘗試應(yīng)用了線性規(guī)劃法[4]、模擬退火遺傳算法[5]、自適應(yīng)遺傳算法[6]等方法解決飛行沖突解脫問(wèn)題，這些方法各有特點(diǎn)，并取得了一定效果。本文在參考國(guó)內(nèi)外有關(guān)文獻(xiàn)和的基礎(chǔ)上，采用一種遺傳粒子群算法解決多機(jī)的飛行沖突解脫問(wèn)題，并與文獻(xiàn)[6]和粒子群算法的規(guī)劃結(jié)果進(jìn)行了比較。

1 問(wèn)題的描述與建模

本文根據(jù)我國(guó)的空管安全規(guī)定，對(duì)多機(jī)沖突解決問(wèn)題進(jìn)行簡(jiǎn)化[7]：

（1）由于民用飛機(jī)一般除了在起飛和降落階段外，都是在固定的高度飛行，且考慮到乘客的舒適要求和燃油消耗要求，飛機(jī)之間在改變航路以避免沖突時(shí)，只是在水平面內(nèi)改變方向。因此可以把三維立體問(wèn)題簡(jiǎn)化為二維平面問(wèn)題。

（2）現(xiàn)實(shí)飛行中，民用飛機(jī)特別是民用運(yùn)輸機(jī)是一種非高機(jī)動(dòng)性能飛機(jī)，且飛機(jī)在高空巡航飛行時(shí)速度無(wú)太大變化，因此假設(shè)飛機(jī)的飛行速度不變。

（3）按照我國(guó)的空管安全規(guī)定，當(dāng)兩架飛機(jī)之間間隔大于20 km時(shí)不存在飛行沖突。本文為提高沖突識(shí)別的準(zhǔn)確性，采用10 km作為飛機(jī)移動(dòng)的步長(zhǎng)。

（4）民用飛機(jī)在巡航階段正常飛行時(shí)，一般沒(méi)有大角度轉(zhuǎn)彎或轉(zhuǎn)向飛行，且固定的航向改變使飛行員能夠更好地執(zhí)行沖突解決方案，并減少反應(yīng)時(shí)間。這里假設(shè)飛機(jī)在飛行中任何位置只能選擇3個(gè)飛行方向，即保持原有航向、左轉(zhuǎn)30°、右轉(zhuǎn)30°。

（5）避免沖突時(shí)，通過(guò)篩選路徑最短和飛行延誤最小的航路來(lái)實(shí)現(xiàn)最省油，也最省時(shí)。

在以上的前提條件下，假設(shè)有N架飛機(jī)同時(shí)進(jìn)入一個(gè)正方形的沖突區(qū)，飛機(jī)不作任何航向調(diào)整時(shí)，保持直線飛行，飛離沖突區(qū)的點(diǎn)，稱(chēng)之為理論上的退出點(diǎn)。算法把飛機(jī)在沖突內(nèi)的飛行時(shí)間分為K步，在每一步中，飛機(jī)保持一定的航向。在進(jìn)入每一步時(shí)，飛機(jī)進(jìn)行航線調(diào)整，以避免發(fā)生沖突。

約束條件為沖突區(qū)內(nèi)任意兩架飛機(jī)之間的距離D大于飛行安全間距δ：

航線的改變不可避免地會(huì)造成飛行路徑長(zhǎng)度的增加，飛機(jī)飛離沖突區(qū)時(shí)偏離理論上的退出點(diǎn)。因此，本文的優(yōu)化目標(biāo)有兩個(gè)，分別是在保證不發(fā)生飛行沖突的情況下，使飛機(jī)的總航線長(zhǎng)度最短且飛行延誤最?。w行延誤是指每架飛機(jī)的理論退出點(diǎn)與實(shí)際退出點(diǎn)之間的距離）。

兩個(gè)目標(biāo)函數(shù)如下：

其中，Si為第i架飛機(jī)在沖突區(qū)內(nèi)飛行路徑的長(zhǎng)度，di為第i架在沖突區(qū)內(nèi)的延誤。

本文使用線性加權(quán)法確定評(píng)價(jià)函數(shù)，線性加權(quán)法是最簡(jiǎn)單、最基本，也是應(yīng)用最廣泛的多目標(biāo)優(yōu)化方法。

對(duì)每架飛機(jī)根據(jù)其進(jìn)入沖突解脫域的入口點(diǎn)，起始航向和每一步的航向變化，計(jì)算其整個(gè)航跡，并檢查初始種群生成的實(shí)驗(yàn)航跡是否存在飛機(jī)沖突。如果發(fā)現(xiàn)飛行沖突，該個(gè)體的適應(yīng)值將設(shè)置為0。如果沒(méi)有沖突，對(duì)每一架飛機(jī)i,計(jì)算其在空域內(nèi)飛機(jī)的總航線長(zhǎng)度和飛行延誤，并使用線性加權(quán)法確定評(píng)價(jià)函數(shù)。

適應(yīng)值函數(shù)如下：

其中，n為沖突區(qū)內(nèi)的飛機(jī)數(shù)量，di為第i架的飛行延誤，Si為第i架飛機(jī)在沖突區(qū)內(nèi)的飛行路徑長(zhǎng)度，k1和k2為常數(shù)。

為簡(jiǎn)單起見(jiàn)采用二進(jìn)制編碼，如果在空域里有N架飛機(jī)，則將構(gòu)造一個(gè)N×K×2維的解空間，將每個(gè)個(gè)體對(duì)應(yīng)的解空間，分解成N個(gè)K維向量：Xn=( )xn1,xn2,L,xnk(k=1,2,…,K)，表示第k架航班在沖突區(qū)內(nèi)的航線調(diào)整。其中：

通過(guò)合理的數(shù)學(xué)建模，將多機(jī)的沖突解脫問(wèn)題簡(jiǎn)化為帶約束的整數(shù)規(guī)劃問(wèn)題。

2 基于遺傳粒子群算法的飛行沖突解脫

2.1 標(biāo)準(zhǔn)遺傳算法（SGA）

標(biāo)準(zhǔn)遺傳算法（Simple Genetic Algorithm，SGA）是Holland于20世紀(jì)60年代提出一種計(jì)算模型[8]，它是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程形成的一種全局優(yōu)化概率搜索算法。對(duì)于一個(gè)特定的問(wèn)題，遺傳算法從代表問(wèn)題可能潛在解集的一個(gè)種群開(kāi)始，種群由經(jīng)過(guò)基因編碼的一定規(guī)模的個(gè)體組成，之后按照適者生存和優(yōu)勝劣汰的競(jìng)爭(zhēng)原理，在每一代，采納了自然進(jìn)化模型，根據(jù)問(wèn)題域個(gè)體的適應(yīng)度大小選擇優(yōu)良個(gè)體，并借助自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，逐代進(jìn)化以產(chǎn)生代表新的解集的種群。周而復(fù)始，反復(fù)迭代，直到滿足終止準(zhǔn)則，最后將運(yùn)算結(jié)果作為問(wèn)題最優(yōu)解。

經(jīng)過(guò)多年的發(fā)展，遺傳算法理論逐漸成熟，已經(jīng)被成功應(yīng)用于優(yōu)化設(shè)計(jì)、模糊邏輯控制、神經(jīng)網(wǎng)絡(luò)、專(zhuān)家系統(tǒng)等領(lǐng)域。

2.2 粒子群算法（PSO）

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是由Eberhart與Kennedy提出的一種新的模擬鳥(niǎo)類(lèi)捕食行為的全局優(yōu)化進(jìn)化算法[9]。該算法首先初始化一群隨機(jī)粒子，然后通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己：一個(gè)是粒子本身所找到的最優(yōu)解；另一個(gè)是整個(gè)種群目前找到的最優(yōu)解。

粒子群算法結(jié)構(gòu)非常簡(jiǎn)單，參數(shù)少，只需簡(jiǎn)單的數(shù)學(xué)運(yùn)算便可以實(shí)現(xiàn)，自出現(xiàn)以來(lái)受到了廣泛的關(guān)注，在組合優(yōu)化[10-11]、控制器參數(shù)調(diào)節(jié)[12]等領(lǐng)域得到了大量的應(yīng)用。

2.3 基于遺傳粒子群算法的飛行沖突解脫

PSO與GA有很多共同之處：它們都起源于人類(lèi)對(duì)生物學(xué)的研究，屬于仿生計(jì)算范疇；都使用適應(yīng)度函數(shù)來(lái)評(píng)價(jià)系統(tǒng)，群體根據(jù)適應(yīng)度值進(jìn)行復(fù)制；兩種算法都經(jīng)過(guò)不斷的搜索，找到最優(yōu)解。它們又有所不同，遺傳算法具有交叉和變異操作，具有廣泛的空間搜索能力，在搜索過(guò)程中不容易陷入局部最優(yōu)，但是算法復(fù)雜，搜索速度慢，沒(méi)有種群的移動(dòng)，缺乏記憶功能，不能參考?xì)v史信息。粒子群算法結(jié)構(gòu)簡(jiǎn)單，僅僅根據(jù)自己的速度來(lái)決定搜索，沒(méi)有GA明顯的選擇、交叉和變異操作，具有運(yùn)行速度快，擁有記憶功能等特點(diǎn)。本文將遺傳算法和粒子群算法相結(jié)合，提出一種遺傳粒子群算法解決多機(jī)沖突解脫問(wèn)題。該算法既保持了個(gè)體之間信息交流，避免陷入早熟收斂與局部最優(yōu)，又提高了搜索效率與加快計(jì)算速度。該算法步驟描述如下：

圖1 算法編碼機(jī)制示意圖

步驟1隨機(jī)產(chǎn)生初始種群Pop。算法采用二進(jìn)制編碼機(jī)制，種群中的任意個(gè)體Xi的維度為Q,Q=N×K×2,N為飛機(jī)數(shù)目，K為每架飛機(jī)在沖突區(qū)內(nèi)航向調(diào)整的次數(shù)。編碼機(jī)制如圖1所示。

步驟2設(shè)定參數(shù)，確定遺傳交叉概率pc,變異概率pm,粒子群慣性因子w,加速度系數(shù)c1、c2和最大迭代次數(shù)NCmax。

步驟3計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)值，采用輪盤(pán)賭選擇方法挑選出染色體對(duì)，以確定的概率進(jìn)行交叉和變異操作，得到種群Pop′。

步驟4對(duì)Pop′中的個(gè)體進(jìn)行適應(yīng)度評(píng)估，得到個(gè)體最優(yōu)位置pim和全局最優(yōu)位置pgm,并按照式（5）和式（6）分別對(duì)種群速度和位置進(jìn)行更新，產(chǎn)生下一代種群Pop。

步驟5判斷是否已經(jīng)達(dá)到最大迭代次數(shù)，如果到達(dá)，結(jié)束進(jìn)程，輸出結(jié)果；否則轉(zhuǎn)至步驟3。

該算法的流程圖如圖2所示。

圖2 遺傳粒子群算法流程圖

圖3 （a）實(shí)例1的沖突解脫路徑圖

圖3 （b）1到10步的沖突解脫路徑圖

圖3 （c）11到20步的沖突解脫路徑圖

3 仿真及驗(yàn)證

在仿真實(shí)驗(yàn)中，4架飛機(jī)以相同的速度飛行，把飛機(jī)的飛行時(shí)間分為20步，如不進(jìn)行航線調(diào)整，在第10步時(shí)4架飛機(jī)將同時(shí)發(fā)生沖突。算法中，群體大小設(shè)480，對(duì)應(yīng)著480條隨機(jī)航路。交叉運(yùn)算的概率設(shè)置為0.7，變異概率為0.01。粒子群的慣性因子w=0.8，加速度系數(shù)c1=c2=0.7。

實(shí)例1 4架飛機(jī)直線交叉通過(guò)沖突區(qū)，其中A飛機(jī)從西向東飛行，B飛機(jī)從南向北飛行，C飛機(jī)從東向西飛行，D飛機(jī)從南向北飛行。

經(jīng)10次抽樣記錄，此算法平均在運(yùn)行10次迭代后能收斂于理想的結(jié)果，平均耗時(shí)為2.31 s。圖3（a）為實(shí)例1的沖突解脫路徑，圖 3（b）和3（c）分別為1到10步和 11到20步的解脫路徑。圖4為算法適應(yīng)度函數(shù)值曲線。

圖4 實(shí)例1的適應(yīng)度函數(shù)值曲線圖

為了評(píng)價(jià)本文算法的性能，將該算法所得到結(jié)果與文獻(xiàn)[6]中的算法，以及二進(jìn)制粒子群算法的規(guī)劃結(jié)果進(jìn)行了比較。表1列出了三種算法運(yùn)行結(jié)果對(duì)比。

表1 實(shí)例1三種算法結(jié)果對(duì)比

圖5 （a）實(shí)例2的沖突解脫路徑圖

圖5 （b）1到10步的沖突解脫路徑圖

圖5 （c）11到20步的沖突解脫路徑圖

實(shí)例2 4架飛機(jī)以45°交叉飛過(guò)沖突區(qū)，每架飛機(jī)的起始位置到?jīng)_突區(qū)的中心的距離為100 km，其中A飛機(jī)從西北向東南方向飛行，B飛機(jī)從西向東飛行，C飛機(jī)從西南向東北飛行，D飛機(jī)從南向北飛行。

經(jīng)10次抽樣記錄，此算法平均在運(yùn)行29次迭代后能收斂于理想的結(jié)果，平均耗時(shí)為7.12 s。圖5（a）為實(shí)例2的沖突解脫路徑，圖5（b）和5（c）分別為 1到10步和11到20步的解脫路徑。飛機(jī)間的安全飛行間距為20 km，圖5中的4架飛機(jī)經(jīng)過(guò)20步航向調(diào)整后，任意兩架之間的間距都大于安全間距。圖6為算法適應(yīng)度函數(shù)值曲線。

表2為實(shí)例2中，本文算法與文獻(xiàn)[1]中的遺傳算法、文獻(xiàn)[6]中的自適應(yīng)遺傳算法的規(guī)劃結(jié)果對(duì)比。

表2 實(shí)例2三種算法運(yùn)行結(jié)果對(duì)比

仿真實(shí)驗(yàn)證明，本文算法能夠快速有效地解決同一沖突區(qū)內(nèi)4架飛機(jī)的沖突解脫。由表1、表2對(duì)比結(jié)果可以看出，遺傳粒子群算法在收斂代數(shù)和計(jì)算速度都優(yōu)于其他兩種方法，且收斂時(shí)的適應(yīng)度值更高，規(guī)劃出的路線更接近原航線，這就減少了飛機(jī)的燃油消耗和管制員的工作負(fù)荷。實(shí)驗(yàn)證明，遺傳粒子群算法解決同一沖突區(qū)內(nèi)4架飛機(jī)的飛行沖突問(wèn)題效果更好。

4 結(jié)論

本文采用遺傳粒子群算法有效地解決了4架飛機(jī)的飛行沖突。該算法綜合了遺傳算法的全局搜索能力與粒子群算法記憶功能和快速收斂的特點(diǎn)，計(jì)算速度快，搜索效率高，可以在相當(dāng)短的時(shí)間內(nèi)規(guī)劃出飛行解脫航跡，且解脫后的飛機(jī)航跡平滑，更接近于原航線。本文假設(shè)飛機(jī)在固定高度層飛行，將飛行的運(yùn)動(dòng)限制在二維平面中，對(duì)于三維空間中的沖突解脫問(wèn)題的研究，將是下一步的工作重點(diǎn)。

[1]Alliot J M，Gruber H，Joly G.Genetic algorithms for solving air traffic control conflicts[C]//Proceedings of the 9th Conference on Artificial Intelligence for Applications，Orlando，F(xiàn)L，USA，1993：338-344.

[2]Burdun I Y.An AI situational pilot model for real-time applications[C]//Proceedings of the 20th Congress on the International Council of the Aeronautical Sciences，Sorrento，Napoli，Italy，September 8-13，1996：210-237.

[3]Ghosh R，Tomlin C.Maneuver design for multiple aircraft conflict resolution[C]//Proceedings of the American Control Conference，Chicago，Illinois，2000，9：672-676.

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

[5]裴志剛，李華星，王慶勝.模擬退火遺傳算法在飛行沖突解脫中的應(yīng)用[J].交通與計(jì)算機(jī)，2005，23（1）：115-117.

[6]趙源.航路飛行輔助決策仿真系統(tǒng)關(guān)鍵問(wèn)題研究[D].西安：西北工業(yè)大學(xué)，2005：33-37.

[7]中國(guó)民航局.CCAR-91-R2一般運(yùn)行和飛行規(guī)則[S].2007-11-22.

[8]Holland J H.Adaption in nature and artificial system[M].Ann Arbor：The University of Michigan Press，1975.

[9]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of IEEE International Conferenceon Neural Networks，Perth，Australia，1995.

[10]陳自郁，何中市，何靜媛.一種求解集合組合問(wèn)題的離散粒子群優(yōu)化模型[J].華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（4）：141-145.

[11]魏靜黃，王宇平.求解約束優(yōu)化問(wèn)題的改進(jìn)粒子群算法[J].系統(tǒng)工程與電子技術(shù)，2008，30（4）：739-742.

[12]Kim T H，Maruta I，Sugie T.Robust PID controller tuning based on the constrained particle swarm optimization[J].Automatica，2008，44（4）：1104-1110.