李永新，甘旭升，周一葉，祝 捷

（1.西京學(xué)院理學(xué)院，西安 710123；2.空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051；3.解放軍95746 部隊，成都 611531）

0 引言

航空軍事運輸在提高現(xiàn)代戰(zhàn)爭支援保證能力方面起到舉足輕重的作用。而穿越走廊作為航空軍事運輸活動的載體，是指在具有全面制空權(quán)的我方控制區(qū)劃設(shè)的雙向空中走廊，是戰(zhàn)場空域空中通道的重要組成部分。它可使己方航空兵運輸機以最小風(fēng)險通過己方防空區(qū)和受空域限制的空域，滿足航空兵部隊休整換防、戰(zhàn)斗轉(zhuǎn)場、人員物資空運的需要［1-2］。因此，借鑒航線網(wǎng)絡(luò)設(shè)計概念，結(jié)合空防和空中作戰(zhàn)任務(wù)的要求和特點，深入研究空中穿越走廊網(wǎng)絡(luò)的優(yōu)化設(shè)計問題，具有重要的理論與現(xiàn)實意義。

從本質(zhì)上說，穿越走廊網(wǎng)絡(luò)優(yōu)化設(shè)計問題是一個航線網(wǎng)絡(luò)優(yōu)化問題。在現(xiàn)有相關(guān)研究中，1996 年，Gutirrez G J 等提出了基于不確定數(shù)據(jù)的無容量限制航線網(wǎng)絡(luò)設(shè)計問題，對航線網(wǎng)絡(luò)的魯棒性進(jìn)行了研究［3］；1998 年，Sohn J 等建立了考慮新辟航線成本的樞紐航線網(wǎng)絡(luò)混合整數(shù)模型，提出了已知樞紐機場集合下的求解方法［4］；2008 年，趙爽建立了限制空域避讓與關(guān)鍵節(jié)點優(yōu)化相結(jié)合網(wǎng)絡(luò)優(yōu)化設(shè)計方法［5］；2013 年，王卉對考慮擁堵成本的航線網(wǎng)絡(luò)優(yōu)化設(shè)計進(jìn)行了研究，并設(shè)計了相關(guān)算法［6］；2015年，王世錦等綜合考慮了各種約束條件構(gòu)建了航線網(wǎng)絡(luò)優(yōu)化模型，并結(jié)合元胞自動機理論對優(yōu)化模型進(jìn)行求解［7］。綜上研究，國內(nèi)外學(xué)者針對不確定環(huán)境下的航線網(wǎng)絡(luò)經(jīng)濟效益作了大量研究，也采用了最優(yōu)化問題求解思想，從節(jié)點交通流入手對局部航線網(wǎng)絡(luò)進(jìn)行了優(yōu)化，但針對存在限制空域的航線網(wǎng)絡(luò)優(yōu)化設(shè)計較少，對航線網(wǎng)絡(luò)的空域結(jié)構(gòu)安全性優(yōu)化研究還不夠，更缺少從軍事運輸角度去研究航線網(wǎng)絡(luò)優(yōu)化設(shè)計問題。

綜上分析，綜合權(quán)衡約束條件，將穿越走廊網(wǎng)絡(luò)優(yōu)化問題轉(zhuǎn)化為無干涉路徑點布局問題，為轉(zhuǎn)化的布局優(yōu)化問題設(shè)計了差分進(jìn)化（Differential Evolution，DE）求解算法，進(jìn)而在穿越走廊網(wǎng)絡(luò)初步規(guī)劃基礎(chǔ)上完成優(yōu)化設(shè)計。實例驗證了方法的有效性。

1 無干涉路徑點布局模型

穿越走廊網(wǎng)絡(luò)優(yōu)化設(shè)計的關(guān)鍵問題在于，某一個無干涉路徑點（即控制節(jié)點）的最優(yōu)空間位置取決于網(wǎng)絡(luò)中的其他無干涉路徑點，因此，必須將所有無干涉路徑點作為整體進(jìn)行優(yōu)化，使得所設(shè)計的穿越走廊網(wǎng)絡(luò)在保證軍事運輸支援保障任務(wù)需求的同時，也滿足戰(zhàn)場空域限制要求。

基于上述描述，在建立無干涉路徑點布局模型前，提出如下假設(shè)：

1）穿越走廊網(wǎng)絡(luò)為二維平面網(wǎng)絡(luò)，不考慮高度層信息；

2）節(jié)點之間的運輸機為無條件直線飛行，且起訖機場對間選擇網(wǎng)絡(luò)中的最短路徑作為運行穿越走廊；

3）各種類型限制空域等同看待且均不可穿越；

4）穿越走廊網(wǎng)絡(luò)運行成本取決于各穿越走廊航段長度。

由初步規(guī)劃得到的穿越走廊可行網(wǎng)絡(luò)可表示為N（V，D，T，B），其中：

1）V（N）表示穿越走廊網(wǎng)絡(luò)中的節(jié)點集合，包括滿足空域結(jié)構(gòu)或飛行需要所布設(shè)的無干涉路徑點和空間位置固定不變的機場節(jié)點。穿越走廊網(wǎng)絡(luò)中無干涉路徑點和機場節(jié)點的個數(shù)分別記為n和m：

由式（7）可知，通過初始穿越走廊可行網(wǎng)絡(luò)所經(jīng)過的自由鏈接線后，僅需給定比例參數(shù)（h1，h2，…，hn）就可對網(wǎng)絡(luò)進(jìn)行重規(guī)劃，且只要滿足任意hi∈（0，1），就不會出現(xiàn)穿越走廊與限制空域交匯沖突的情況，既能滿足穿越走廊網(wǎng)絡(luò)的安全性要求，又可為穿越走廊網(wǎng)絡(luò)提供可優(yōu)化空間。

圖1 無干涉路徑點調(diào)整示意圖

從以上最優(yōu)化數(shù)學(xué)模型可看出，無干涉路徑點布局優(yōu)化問題可以視為不可微連續(xù)空間的函數(shù)最小化問題，存在著非線性、大規(guī)模、強約束、不確定等復(fù)雜性。因此，常規(guī)的最優(yōu)化求解方法往往不是很理想，需要探索更為有效的智能算法求解該最優(yōu)化模型。基于此，本文嘗試采用差分進(jìn)化算法求解最優(yōu)化數(shù)學(xué)模型，并探討了其可行性和有效性。

2 差分進(jìn)化算法

DE 算法的基本原理是在種群中隨機選取或按照一定策略選取3 個個體，將其中2 個個體的差分向量進(jìn)行線性尺度變換，然后，與第3 個個體疊加以獲得新個體，最后，利用目標(biāo)函數(shù)對新個體與種群中預(yù)先選定個體進(jìn)行評價，保留較優(yōu)個體［8-9］。對于函數(shù)最小化問題：

式中，Rand 為區(qū)間［0，1］內(nèi)均勻分布的隨機數(shù)。

DE 算法基本操作包括變異、交叉和選擇，下面進(jìn)行逐一介紹。

2.1 變異操作

在第g 代進(jìn)化中，選取當(dāng)前種群個體xi（g），通過差分變異操作生成目標(biāo)個體ti（g）。在諸多變異策略中［10］，本文選取的變異策略為DE/rand/1，其過程描述為

其中，rand 表示變異操作的基為當(dāng)前種群中隨機選取1 個個體，1 表示線性尺度變換的差分向量個數(shù)，r1，r2，r3是從［1，N］中隨機選取的異于下標(biāo)i 且相互獨立的整數(shù)，F(xiàn)∈（0，1）為縮放差分向量的比例因子。圖2 為二維函數(shù)優(yōu)化中DE/rand/1 變異策略產(chǎn)生變異向量的過程。

圖2 二維參數(shù)空間中“DE/rand/1”變異策略

2.2 交叉操作

為改善種群多樣性，需對目標(biāo)個體進(jìn)行交叉操作。通過將目標(biāo)個體ti的部分變量替換為當(dāng)前種群中個體xi中對應(yīng)位置的變量，獲得測試個體vi。由此可看出，交叉操作能將個體中的優(yōu)良變量保留至下一代，增強了算法的局部搜索能力［11］。本文只介紹DE 算法中常用的二項交叉操作。

二項交叉操作是在區(qū)間［0，1］內(nèi)隨機生成若干均勻分布的rand，隨機數(shù)個數(shù)等于目標(biāo)個體ti中的變量個數(shù)，且各隨機數(shù)rand 與變量一一對應(yīng)。則可采用二項交叉操作生成測試個體vi：

式中，rnd 為區(qū)間［1，d］內(nèi)均勻分布的整數(shù)，以確保至少一維分量是從ti貢獻(xiàn)給vi；否則，可能會vi與ti相同，不利于新個體產(chǎn)生。圖3 演示了二項交叉操作過程。

圖3 二項交叉操作過程

2.3 選擇操作

DE 算法采用的選擇操作方式，僅當(dāng)vi的適應(yīng)度優(yōu)于xi，才會被選入下一代。選擇操作方式如下

這使得更多優(yōu)秀個體進(jìn)入下一代種群中，通過這種逐代提高種群多樣性的方法達(dá)到最優(yōu)解或滿意解。

為簡化穿越走廊網(wǎng)絡(luò)優(yōu)化設(shè)計過程，提高優(yōu)化效率，并易于算法的編程實現(xiàn)，本文選擇最常用的DE/rand/1/bin，其中，bin 表示二項交叉操作。

3 無干涉路徑點布局問題求解的DE算法設(shè)計

將DE 算法用于基于無干涉路徑點布局規(guī)劃的穿越走廊優(yōu)化設(shè)計時，需要解決以下5 個關(guān)鍵性問題：1）個體的編碼、解碼以及各類參數(shù)設(shè)置；2）變異和交叉操作后對個體的修復(fù)，使其成為可行解；3）預(yù)置評價個體的標(biāo)準(zhǔn)；4）設(shè)計合理進(jìn)化機制搜索問題的可行解，并對問題評價；5）無干涉路徑點布局約束的處理。

此外，初步規(guī)劃的穿越走廊可行網(wǎng)絡(luò)為消除與限制空域之間的交匯沖突，會利用無干涉路徑點進(jìn)行中轉(zhuǎn)，因此，也就出現(xiàn)了多條穿越走廊共用相同無干涉路徑點的情況。這種連接方式增加了穿越走廊網(wǎng)絡(luò)的連接度，在降低完成運輸任務(wù)所需總成本的同時，也使所涉及的穿越走廊中的飛行流量大幅上升（即相當(dāng)于多條穿越走廊的飛行流量匯集到一條穿越走廊中），容易造成飛行沖突，最終使穿越走廊網(wǎng)絡(luò)的安全性下降。出于對空戰(zhàn)場軍事活動安全要求這一剛性約束的考慮，穿越走廊網(wǎng)絡(luò)總運行成本的最小化不能依靠降低網(wǎng)絡(luò)安全性來實現(xiàn)。因此，本文采用構(gòu)造虛擬無干涉路徑點的方法，對重復(fù)利用的無干涉路徑點進(jìn)行分解，如圖4 所示，將該類無干涉路徑點分作兩個或者多個處理，盡量避免多條穿越走廊共用相同無干涉路徑點的情況。

圖4 無干涉路徑點分解示意圖

針對上述問題，基于DE 算法的無干涉路徑點布局模型優(yōu)化具體步驟為：

Step 1 編碼

Step 6 交叉操作

對變異操作產(chǎn)生的目標(biāo)個體ti（g），按式（13）執(zhí)行交叉操作，產(chǎn)生測試個體vi（g）。

Step 7 選擇操作

按式（16）計算vi（g）的適應(yīng)度值，并按式（14）執(zhí)行選擇操作，生成新的種群。

Step 8 更新當(dāng)前最優(yōu)解

將新生成種群的個體與上一代種群中的最優(yōu)個體作比較，保留比較后的最優(yōu)個體，并計算其適應(yīng)度值，更新best_fit 和best_ind。

Step 9 迭代

重復(fù)Step 4～Step 8，種群得到不斷進(jìn)化，不斷更新best_fit 和best_ind，直到適應(yīng)度函數(shù)最優(yōu)或達(dá)到最大迭代數(shù)。

4 實例仿真

實例數(shù)據(jù)源自一次穿越走廊可行網(wǎng)絡(luò)初始規(guī)劃結(jié)果［12］（通過Dijkstra 算法求解），如圖5 所示，包括10 個機場節(jié)點坐標(biāo)，4 個限制空域的頂點坐標(biāo)，31 個待優(yōu)化的無干涉路徑點（包括11 個虛擬節(jié)點）初始坐標(biāo)及其對應(yīng)的自由鏈接線，以及初步規(guī)劃后的穿越走廊可行網(wǎng)絡(luò)中各個節(jié)點之間的鄰接關(guān)系。在此初始規(guī)劃基礎(chǔ)上，采用設(shè)計的DE 算法對無干涉路徑點布局模型進(jìn)行求解，完成穿越走廊網(wǎng)絡(luò)的優(yōu)化設(shè)計。DE 算法參數(shù)設(shè)置如表1 所示。

圖5 考慮限制空域的穿越走廊可行網(wǎng)絡(luò)初始規(guī)劃結(jié)果

表1 DE 算法參數(shù)設(shè)置

據(jù)上述基本設(shè)置，基于無干涉路徑點布局模型特點的差分進(jìn)化算法用MATLAB 2014a 編程實現(xiàn)，對考慮限制空域影響的穿越走廊可行網(wǎng)絡(luò)規(guī)劃進(jìn)行優(yōu)化，優(yōu)化后的穿越走廊網(wǎng)絡(luò)如圖6 所示。

圖6 穿越走廊可行網(wǎng)絡(luò)優(yōu)化設(shè)計結(jié)果

在圖6 中，黑色圓點為優(yōu)化前無干涉路徑點位置，綠色圓點為優(yōu)化后無干涉路徑點及其虛擬路徑點位置。通過與圖5 對比可看出，優(yōu)化后的網(wǎng)絡(luò)中，穿越走廊拐點減少，路徑更為平滑，適合機動性相對較弱的大型運輸機飛行；且穿越走廊之間出現(xiàn)交叉或交匯的情況也明顯改善，一定程度上改善了流量擁堵的情況；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也變得更為簡單直觀，可以明顯看出樞紐軸輻式網(wǎng)絡(luò)的基本框架。為更好說明優(yōu)化效果，本文還對優(yōu)化前后的穿越走廊網(wǎng)絡(luò)性能作了定量對比。

穿越走廊網(wǎng)絡(luò)規(guī)劃設(shè)計方案要求符合航線網(wǎng)絡(luò)指標(biāo)評價體系。依據(jù)航線網(wǎng)絡(luò)指標(biāo)體系，采用網(wǎng)絡(luò)長度、航路利用率、網(wǎng)絡(luò)運行成本和非直線系數(shù)等具有代表性的航線網(wǎng)絡(luò)性能指標(biāo)，對優(yōu)化前后的穿越走廊網(wǎng)絡(luò)進(jìn)行評價，評價結(jié)果如表2 所示。

表2 穿越走廊網(wǎng)絡(luò)性能指標(biāo)對比

由表2 中優(yōu)化百分比可看出，優(yōu)化后的穿越走廊網(wǎng)絡(luò)每一項性能指標(biāo)均優(yōu)于初步規(guī)劃的穿越走廊可行網(wǎng)絡(luò)，其中，路徑點數(shù)目減少了60%，非直線系數(shù)降低了16.5%，網(wǎng)絡(luò)運行成本降低了12.6%，航路利用率提高了20.3 %，網(wǎng)絡(luò)可達(dá)性提高了38.4%。通過穿越走廊網(wǎng)絡(luò)優(yōu)化前后性能指標(biāo)對比定量分析，說明了優(yōu)化設(shè)計方法的必要性和有效性。

5 結(jié)論

為解決穿越走廊可行網(wǎng)絡(luò)的優(yōu)化設(shè)計問題，首先，將穿越走廊優(yōu)化問題轉(zhuǎn)化為無干涉路徑點布局問題，構(gòu)建了無干涉路徑點布局模型，以平衡戰(zhàn)場空域安全與運行成本并保持在可接受的水平。然后，根據(jù)無干涉路徑點布局模型的特點，設(shè)計了適于穿越走廊優(yōu)化問題的個體評價標(biāo)準(zhǔn)和個體修復(fù)算子，進(jìn)而采用DE 算法對無干涉路徑點布局優(yōu)化問題進(jìn)行求解。實例分析表明，較之于穿越走廊可行網(wǎng)絡(luò)初始規(guī)劃結(jié)果，基于DE 算法的無干涉路徑點布局優(yōu)化的各項性能指標(biāo)都得到了明顯改善，將其應(yīng)用于穿越走廊優(yōu)化設(shè)計是可行的，也是有效的。