基于差分進(jìn)化算法的穿越走廊可行網(wǎng)絡(luò)優(yōu)化問題

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

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

0 引言

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

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

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

1 無干涉路徑點(diǎn)布局模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 變異操作

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

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

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

2.2 交叉操作

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

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

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

圖3 二項(xiàng)交叉操作過程

2.3 選擇操作

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

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

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

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

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

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

圖4 無干涉路徑點(diǎn)分解示意圖

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

Step 1 編碼

Step 6 交叉操作

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

Step 7 選擇操作

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

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

將新生成種群的個(gè)體與上一代種群中的最優(yōu)個(gè)體作比較，保留比較后的最優(yōu)個(gè)體，并計(jì)算其適應(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í)例仿真

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

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

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

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

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

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

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

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

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

5 結(jié)論

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