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

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

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

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

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

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

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

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

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

1 問題建模

1.1 沖突探測模型

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

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

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

1.2 數學優化模型

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

1.2.2 目標函數

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

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

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

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

（1）地面延誤成本

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

式中lorig為航空器計劃飛行高度層。

1.2.3 約束條件

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

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

2 多目標優化算法設計

2.1 改進的NSGA?Ⅱ算法

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

2.1.1 初始化種群

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

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

2.1.2 選擇

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

2.1.3 交叉

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

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

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

2.1.4 變異

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

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

2.2 多目標優化解的評價

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

2.2.1 覆蓋率

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

式中PFU、PFV分別為兩組Pareto 最優解集。分子表示解集V中被U中至少一個解支配的解的數目，分母表示解集V中所有解的個數。 若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個點與參考點圍成區域的超體積。超體積值越大，表示解集的效果越好。

2.2.4 平均理想距離

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

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

3 仿真驗證

3.1 運行場景

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

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

表1 算法參數設置Table 1 Parameter settings of algorithms

3.2 結果分析

3.2.1 算法性能評價

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

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

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

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

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

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

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

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

3.2.2 算法優化結果

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

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

4 結 論

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

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