基于改進NSGA?Ⅱ算法的航班戰(zhàn)略沖突解脫研究

徐 滿，胡明華，張 穎，江 灝

（南京航空航天大學民航學院，南京 211106）

隨著經(jīng)濟的不斷發(fā)展，亞太地區(qū)將成為航空器客運量增長的主要動力，中國將在2022 年成為全球第一大航空運輸市場［1］。由于空中交通需求的不斷增長，當前的空域會變得越來越擁擠，空中交通的擁堵情況越來越嚴重。

航空器的沖突解脫問題是一個大規(guī)模組合優(yōu)化問題，且由于航空器之間沖突的存在使得航空器之間相互耦合［2］。有大量的文獻研究航空器在戰(zhàn)術(shù)及預戰(zhàn)術(shù)階段的沖突解脫問題，主要通過調(diào)整航空器的起飛時刻、調(diào)整航空器的飛行速度、修改航空器的水平航跡和分配高度層等方式解決相應的沖突［3?4］。但是，采用這些方式的短期內(nèi)的沖突解脫存在一定的缺點，即沒有從全局角度考慮航空器的沖突解脫。由于航空器之間的相互關系，短期內(nèi)的沖突解脫可能會產(chǎn)生“多米諾骨牌”效應，使得沖突解脫一直處于被動，危及空域安全。例如，采用地面等待策略解決沖突時，已經(jīng)延誤了的航空器仍然需要繼續(xù)等待其他航空器以滿足空域的容量要求［5］。而戰(zhàn)略沖突解脫研究，旨在根據(jù)航空器的飛行計劃在起飛前相當長一段時間內(nèi)解決潛在的飛行沖突，是確保航空器安全運行的一項關鍵技術(shù)。目前，戰(zhàn)略沖突解脫問題引起了大量的關注。

四維航跡的運用以及基于航跡運行概念的提出被認為是未來空中交通管理的運行基礎，在此基礎上戰(zhàn)略沖突解脫問題得到了進一步的研究。四維航跡將航空器航跡定義為三維空間加上時間，隨著運行技術(shù)的不斷發(fā)展，四維航跡可以有效降低航空器運行過程中的不確定性。這就為在一個較長時間范圍內(nèi)解決航空器之間潛在沖突提供了技術(shù)支持。

已有大量的文獻研究了航空器四維航跡戰(zhàn)略沖突解脫問題。沖突解脫由于問題本身的復雜度較高，常采用啟發(fā)式算法求解，并且在提高算法的求解效率上做了大量的研究。2019 年，Dai 等［6］提出了一種改進的模擬退火算法，將求解過程分成兩個階段：第一階段用于減少沖突數(shù)量；第二階段用于優(yōu)化航空器的飛行時間。同時，在沖突解脫時設計了一個均勻高度層策略，引導航空器均勻分布至各個可用高度層，引入滑動時間窗來降低問題復雜度以提高求解效率。但是其將沖突數(shù)量與航空器航跡偏移量進行線性組合，解決的仍是單目標優(yōu)化問題。除此之外，還有大量運用模擬退火算法及其改進算法的研究［7?9］。合作協(xié)同進化算法［10］在求解航空器沖突解脫問題也擁有良好的性能，合作協(xié)同進化算法采用分而治之的思想，將一個大規(guī)模組合優(yōu)化問題分解成若干個子問題，從而降低問題的維數(shù)，各個子問題采用特定的進化算法優(yōu)化得到部分可行解，通過各個小組之間的合作進化獲取全局可行解。在合作協(xié)同進化算法的框架下，采用遺傳算法進行優(yōu)化可以極大提高算法的優(yōu)化效率，其研究的仍是單目標優(yōu)化問題。

在實際運行過程中，空中交通管制員往往會在沖突數(shù)量和航空器航跡調(diào)整量之間尋求一個很好的平衡，將沖突解脫問題建模為多目標優(yōu)化問題更加 符 合 實 際。Su 等［11］于2017 年 采 用 多 目 標 文 化基因算法求解沖突解脫問題。算法采用經(jīng)典非支配排序遺傳算法（Non?dominated sorting genetic al?gorithm Ⅱ，NSGA?Ⅱ）進行全局搜索獲取可行解，同時結(jié)合局部搜索算法加強對當前最優(yōu)解的搜索，獲得更優(yōu)可行解，但是算法的復雜度較高。多目標合作協(xié)同進化算法［12］同樣被應用于沖突解脫問題，在協(xié)同進化算法的框架下，采用基于分解的多目標進化算法（Multi?objective evolutionary algo?rithm based on decomposition，MOEA/D）［13］進 行各個小組的內(nèi)部優(yōu)化。雖然采用了合作協(xié)同進化算法的框架，但是算法的求解效率較低。

針對以上問題，本文采用一種改進的NSGA?Ⅱ算法研究航空器沖突解脫中的多目標優(yōu)化問題，通過對算法內(nèi)部遺傳算子的設計，提高算法優(yōu)化效率，同時控制算法的復雜度。在解決航空器之間潛在沖突的同時考慮與航空器航跡調(diào)整量所引起的航跡調(diào)整成本。本文采用調(diào)整航空器起飛時刻和分配高度層的方式在戰(zhàn)略階段解決航空器之間的潛在沖突，沖突成本來自航班沖突解脫后的飛行計劃與初始飛行計劃之間的偏差。主要創(chuàng)新之處在于，本文為染色體中的基因賦予相應的局部適應度，設計了一種自適應交叉算子與變異算子，結(jié)合NSGA?Ⅱ框架進行全局優(yōu)化。

1 問題建模

1.1 沖突探測模型

本文研究巡航狀態(tài)下的航空器沖突解脫問題，因此假設航跡起終點為爬升和下降頂點。假設空域中有n架航空器，F(xiàn)=(f1，f2，f3，…，fn)按照航班計劃沿著特定的航路飛行，航空器處于巡航狀態(tài)，按照固定的高度層以恒定的速度運行。航空器的安全間隔在垂直方向上為Nv，水平方向為Nh，當航空器在空域中飛行時，它們的航跡相互影響。假設航班嚴格地按照計劃航線飛行，那么潛在的沖突會發(fā)生在兩條航路的交叉點附近，如圖1 所示。當兩架航空器的保護區(qū)發(fā)生重疊時，則認為兩架航空器存在潛在沖突，這種情況并不意味著兩架航空器一定會沖突，但是在運行過程中是需要避免出現(xiàn)的。當航空器fi和航空器fj的水平距離小于Nh且垂直距 離 小 于Nv時，‖Pfi(t)-Pfj(t)‖2

圖1 航空器沖突圖Fig.1 Aircraft conflict

為了表示航空器之間的沖突關系，本文定義了一個矩陣C來表示航空器之間是否有沖突，即

1.2 數(shù)學優(yōu)化模型

航路網(wǎng)絡范圍內(nèi)的戰(zhàn)略沖突解脫問題可以描述為：給定一個航路網(wǎng)絡范圍，對于航路網(wǎng)絡中的每一架航空器進行四維航跡規(guī)劃，在較低的航空器沖突解脫成本下盡可能減少航空器之間的沖突數(shù)量。在進行沖突解脫的過程中，應滿足空域容量限制、航空器機動性能限制等。航空器f的航跡由一組四維航跡采樣點組成，即有

1.2.2 目標函數(shù)

為保證航空器運行的安全性，必須盡可能地減少航空器之間的潛在沖突，由式（1）中的矩陣C可得航班之間的沖突關系。那么，航班fi的沖突數(shù)量可以由式（3）計算。

每一個沖突都被一對沖突航班重復計算兩次，所以航班間的沖突數(shù)量為

在求解過程中，為了盡可能避免與其他航班之間的潛在沖突，可能對航班的初始航跡做出重大修改，從而導致大量偏移其初始航班計劃。但是，這樣的方式可能會產(chǎn)生額外的成本。因此，沖突解脫還應從經(jīng)濟角度進行評估，即航班應盡可能小地偏離初始計劃，目標2 重點關注最小化航跡調(diào)整成本（Total trajectory amendment cost，TTAC）。本文采用調(diào)整航空器起飛時刻以及高度層分配解決航空器之間的潛在沖突，TTAC 由地面延誤成本（CostGH）和高度層分配成本（CostFL）構(gòu)成，那么目標2 可由式（5）計算。

式中：λGH為地面延誤成本系數(shù)；λFL為高度層分配成本系數(shù)。由于地面延誤成本與高度層分配成本單位不同，無法直接相加，因此需要進行歸一化處理，即將每個航班的地面延誤和高度調(diào)整量除以最大允許值。

（1）地面延誤成本

航空器實際離場時間與初始飛行計劃中離場時間之差為航空器的地面延誤，即

式中l(wèi)orig為航空器計劃飛行高度層。

1.2.3 約束條件

考慮到安全性、公平性和航空器的性能，軌跡中的每個元素應盡可能接近其計劃值。模型的約束集如下所示

?f∈F，e∈E，l∈L，t∈T均 應 滿 足 上 述 約 束，E是航段集合。其中，約束（8）保證航空器沿著單一可行航線飛行；約束（9）保證航空器的地面延誤不超出最大允許延誤，TfGH表示單個航空器最大允許延誤；約束（10）保證航空器的飛行高度層只能在允許的高度層內(nèi)，NfFL為最大高度調(diào)整量。

2 多目標優(yōu)化算法設計

2.1 改進的NSGA?Ⅱ算法

多目標優(yōu)化可以定義為尋找滿足約束條件的決策變量向量，并同時優(yōu)化多個目標函數(shù)的問題，目標函數(shù)之間往往是對立的。NSGA?Ⅱ根據(jù)目標函數(shù)特點，對可行解進行非支配排序，最終得到Pareto 前沿。與經(jīng)典的NSGA?Ⅱ算法及MOEA/D 相比，本文采用的算法根據(jù)問題特點設計了自適應交叉算子與變異算子［15］加快進化過程。

2.1.1 初始化種群

本文采用調(diào)整航空器起飛時刻與高度層分配兩種方式解決航空器間的潛在沖突，在生成初始種群時，根據(jù)當前航班計劃中各個航班沖突數(shù)量，采用輪盤賭隨機選擇一條航跡，沖突數(shù)量越多，航跡被選中的概率越大。以概率形式隨機修改起飛時刻與飛行高度層，獨立運行N次，生成初始種群，具體過程如圖2 所示。

圖2 種群初始化流程圖Fig.2 Flow chart of population initialization

2.1.2 選擇

本文采用錦標賽選擇法。從父代種群中隨機選擇兩個父代，首先比較兩個父代的非支配序，優(yōu)先選擇非支配序較低的父代個體；若父代的非支配序相同，則比較父代個體的擁擠距離，優(yōu)先選擇擁擠距離較大的父代個體。

2.1.3 交叉

本文采用的自適應交叉算子，在進行交叉操作時，對于選擇的父代個體，比較父代個體相同位置基因的適應度，即在兩個不同的航班計劃中比較同一架航班在該計劃下的沖突解脫成本。個體中每架航班的局部適應度由式（11）計算。

式中：AC和BC分別為線性重組生成的兩個子代，floor 表示向下取整，k為線形重組系數(shù)，交叉概率為Pc。自適應交叉算子如圖3 所示。

圖3 自適應交叉算子Fig.3 Adaptive crossover operator

2.1.4 變異

較高的局部適應度意味著該航班的飛行計劃產(chǎn)生較少的沖突和較低的飛行成本，所以當染色體某個位置基因適應度值小于ε時，才發(fā)生變異，其發(fā)生變異的概率為Pm。自適應變異算子如圖4所示。

圖4 自適應變異算子Fig.4 Adaptive mutation operator

2.2 多目標優(yōu)化解的評價

如何評價沖突解脫優(yōu)化解集的優(yōu)劣，在使航班盡可能小地偏離初始飛行計劃的情況下得到較少沖突數(shù)量的航班計劃是一個值得深究的問題。本文擬從Pareto 最優(yōu)解的收斂性和多樣性兩個方面進行評估，采用以下4 個指標［16］來評估本文提出的算法。

2.2.1 覆蓋率

覆蓋率（C?Metric，CM）是衡量Pareto 前沿的收斂性的指標，即

式中PFU、PFV分別為兩組Pareto 最優(yōu)解集。分子表示解集V中被U中至少一個解支配的解的數(shù)目，分母表示解集V中所有解的個數(shù)。 若CCM(PFU，PFV)=1，說明解集V完全被解集U支配，即解集V收斂性比解集U差。

2.2.2 空間分布

空間分布（Spacing，SP）是衡量Pareto 前沿的廣泛程度的指標，即

式中：up表示各個解到其他解的最小歐氏距離；-u為均值。CSP(PF)值越小，說明空間分布越均勻。

2.2.3 超體積

超體積（Hyper volume，HV）是衡量Pareto 前沿收斂性和多樣性的綜合指標，即

式中：δ代表Lebesgue 測度，用來衡量體積；Vp表示第p個點與參考點圍成區(qū)域的超體積。超體積值越大，表示解集的效果越好。

2.2.4 平均理想距離

平均理想距離（Mean ideal distance，MID）是衡量Pareto 前沿和理想點間距離的指標，即

式中表示第p個非支配解的第t個目標值。本文研究雙目標優(yōu)化問題，因為求解最小化問題，所以理想點可設置為坐標原點。

3 仿真驗證

3.1 運行場景

本文重點研究巡航階段沖突解脫問題，數(shù)據(jù)采用2019 年6 月8 日9：00 至12：00 中 國 航 路 網(wǎng) 絡 中1 472 架航班進行仿真驗證，在MATLAB R2019a平臺上運行，航班飛過的航路點如圖5 所示，涉及2 136 個航路點和186 個起降機場。本文對每條航跡采用等時間間隔采樣生成相應的航跡采樣點，采樣間隔為15 s，利用墨卡托投影將航跡采樣點從經(jīng)緯度坐標轉(zhuǎn)化為(x，y)坐標。允許的單個航班最大延誤TfGH為60 min，航班離場時隙為1 min；單個航班飛行高度最大調(diào)整量NfFL為1 200 m，遵循“東單西雙”的原則，允許的飛行高度范圍為8 900 m至11 600 m，以300 m 的間隔劃分高度層。采用網(wǎng)格法探測航空器之間的潛在沖突，網(wǎng)格在水平方向上大小為Nh，在垂直方向上為Nv，時間維度的網(wǎng)格大小與采樣時間間隔相等。本文采用的改進NS?GA?Ⅱ算法各項參數(shù)如表1 所示，其中，種群規(guī)模與進化代數(shù)等參數(shù)均通過多次對比實驗得到的最優(yōu)結(jié)果確定。

圖5 航路點圖Fig.5 Distribution of waypoints

表1 算法參數(shù)設置Table 1 Parameter settings of algorithms

3.2 結(jié)果分析

3.2.1 算法性能評價

本文將改進的NSGA?Ⅱ算法與經(jīng)典NSGA?Ⅱ算法以及MOEA/D 進行對比驗證算法的有效性，同時利用多目標優(yōu)化解的指標進行評價，具體結(jié)果如表2 所示。啟發(fā)式算法的優(yōu)化效果具有隨機性，因此，表2 中的結(jié)果均基于15 次獨立重復試驗得到。

表2 算法性能對比Table 2 Performance comparison between algorithms

由表2 可知，改進的NSGA?Ⅱ算法在各項性能上均優(yōu)于經(jīng)典的NSGA?Ⅱ算法及MOEA/D。覆蓋率指標，改進的NSGA?Ⅱ算法得到的Pareto前沿完全支配另外兩種算法。改進的NSGA?Ⅱ算法的Pareto 最優(yōu)解相對于經(jīng)典算法及MOEA/D而言，解集更占有支配地位（CM），解集的分布更均勻（SP），解集的收斂性更好（HV），解得質(zhì)量也更高（MID）。

算法的收斂性和多樣性可由反轉(zhuǎn)世代距離（Inverted generational distance，IGD）反映，本文將15 次獨立運行得到的Pareto 最優(yōu)解集P*作為參考集，計算參考點到最近的解的距離的平均值。IGD值越小，說明算法綜合性越好，即

IGD 值與進化代數(shù)的關系如圖6 所示，由于IGD 值在前100 代平穩(wěn)，所以圖中只選取了前100代的結(jié)果并做歸一化處理，以使變化趨勢更加明顯。

圖6 IGD 變化趨勢Fig.6 IGD changing trend

由圖6 可知，在當前參數(shù)條件下，3 種算法均可收斂。在3 種算法中，采用了自適應遺傳算子的改進NSGA?Ⅱ算法收斂速度最快。表3 給出了3 種算法在達到收斂代數(shù)和達到最大進化代數(shù)時的運行時間。對比MOEA/D 算法、經(jīng)典NSGA?Ⅱ算法與改進的NSGA?Ⅱ算法，本文所提算法在運算速度上提高了約8%。

表3 算法運行時間對比Table 3 Running time comparison between algorithms

3.2.2 算法優(yōu)化結(jié)果

圖7 是3 種算法的優(yōu)化結(jié)果對比圖。由圖可知，改進的NSGA?Ⅱ算法不僅在沖突解脫的效果上優(yōu)于兩種算法（Obj1），而且產(chǎn)生的航跡偏移量（Obj2）也更小。在最終的Pareto 最優(yōu)解集中，本文的改進算法目標1 最優(yōu)時可以將沖突數(shù)量減少至272，而經(jīng)典的算法沖突數(shù)量則多達422，MOEA/D沖突數(shù)量最小也為324 個，這反映了在引入改進了的交叉算子和變異算子后算法在沖突解脫方面的優(yōu)異性能。目標2 則反映出改進后的NSGA?Ⅱ算法，在解決沖突的時候產(chǎn)生的航跡調(diào)整量更少，使航空器在沖突解脫時產(chǎn)生更小的調(diào)整成本，符合航空公司的利益。

圖7 Pareto 前沿對比圖Fig.7 Comparison chart of Pareto front

4 結(jié) 論

本文主要研究了沖突解脫中的多目標優(yōu)化問題。針對問題的特點，本文將航空器沖突解脫建模為以沖突數(shù)量和航空器航跡調(diào)整量為目標的雙目標優(yōu)化問題。針對所求解的沖突解脫問題的特點，采用了一種改進的NSGA?Ⅱ算法，設計了自適應交叉算子與變異算子，旨在提高算法搜索最優(yōu)解的效率。與經(jīng)典的NSGA?Ⅱ算法以及MOEA/D 相比，改進了的算法具有沖突解脫的有效性和求解的高效性，不僅可以同時兼顧航跡調(diào)整成本解決大量沖突，而且能更快收斂，有很強的參考價值。

下一步的工作主要集中對更復雜沖突解脫方式的建模以及進一步提高算法的效率上：沖突解脫方式除了考慮起飛時間和高度層優(yōu)化分配，還可以考慮航跡的水平調(diào)整以及高度層的分航段優(yōu)化；算法在求解大規(guī)模航班時缺乏時效性，可能需要大量的計算時間。采用更加多樣化的沖突方式和將算法與局部搜索算法相結(jié)合以提高搜索效率預期將有助于提高算法的效率。