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

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

（南京航空航天大學(xué)民航學(xué)院，南京 211106）

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

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

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

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

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

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

1 問題建模

1.1 沖突探測模型

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

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

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

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

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

1.2.2 目標(biāo)函數(shù)

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

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

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

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

（1）地面延誤成本

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

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

1.2.3 約束條件

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

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

2 多目標(biāo)優(yōu)化算法設(shè)計(jì)

2.1 改進(jìn)的NSGA?Ⅱ算法

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

2.1.1 初始化種群

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

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

2.1.2 選擇

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

2.1.3 交叉

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

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

圖3 自適應(yīng)交叉算子Fig.3 Adaptive crossover operator

2.1.4 變異

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

圖4 自適應(yīng)變異算子Fig.4 Adaptive mutation operator

2.2 多目標(biāo)優(yōu)化解的評價(jià)

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

2.2.1 覆蓋率

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

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

2.2.2 空間分布

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

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

2.2.3 超體積

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

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

2.2.4 平均理想距離

平均理想距離（Mean ideal distance，MID）是衡量Pareto 前沿和理想點(diǎn)間距離的指標(biāo)，即

式中表示第p個(gè)非支配解的第t個(gè)目標(biāo)值。本文研究雙目標(biāo)優(yōu)化問題，因?yàn)榍蠼庾钚』瘑栴}，所以理想點(diǎn)可設(shè)置為坐標(biāo)原點(diǎn)。

3 仿真驗(yàn)證

3.1 運(yùn)行場景

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

圖5 航路點(diǎn)圖Fig.5 Distribution of waypoints

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

3.2 結(jié)果分析

3.2.1 算法性能評價(jià)

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

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

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

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

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

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

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

表3 算法運(yùn)行時(shí)間對比Table 3 Running time comparison between algorithms

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

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

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

4 結(jié) 論

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

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