基于差分進化算法的穿越走廊可行網絡優化問題

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

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

0 引言

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

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

綜上分析，綜合權衡約束條件，將穿越走廊網絡優化問題轉化為無干涉路徑點布局問題，為轉化的布局優化問題設計了差分進化（Differential Evolution，DE）求解算法，進而在穿越走廊網絡初步規劃基礎上完成優化設計。實例驗證了方法的有效性。

1 無干涉路徑點布局模型

穿越走廊網絡優化設計的關鍵問題在于，某一個無干涉路徑點（即控制節點）的最優空間位置取決于網絡中的其他無干涉路徑點，因此，必須將所有無干涉路徑點作為整體進行優化，使得所設計的穿越走廊網絡在保證軍事運輸支援保障任務需求的同時，也滿足戰場空域限制要求。

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

1）穿越走廊網絡為二維平面網絡，不考慮高度層信息；

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

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

4）穿越走廊網絡運行成本取決于各穿越走廊航段長度。

由初步規劃得到的穿越走廊可行網絡可表示為N（V，D，T，B），其中：

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

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

圖1 無干涉路徑點調整示意圖

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

2 差分進化算法

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

式中，Rand 為區間［0，1］內均勻分布的隨機數。

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

2.1 變異操作

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

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

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

2.2 交叉操作

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

二項交叉操作是在區間［0，1］內隨機生成若干均勻分布的rand，隨機數個數等于目標個體ti中的變量個數，且各隨機數rand 與變量一一對應。則可采用二項交叉操作生成測試個體vi：

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

圖3 二項交叉操作過程

2.3 選擇操作

DE 算法采用的選擇操作方式，僅當vi的適應度優于xi，才會被選入下一代。選擇操作方式如下

這使得更多優秀個體進入下一代種群中，通過這種逐代提高種群多樣性的方法達到最優解或滿意解。

為簡化穿越走廊網絡優化設計過程，提高優化效率，并易于算法的編程實現，本文選擇最常用的DE/rand/1/bin，其中，bin 表示二項交叉操作。

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

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

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

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

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

Step 1 編碼

Step 6 交叉操作

對變異操作產生的目標個體ti（g），按式（13）執行交叉操作，產生測試個體vi（g）。

Step 7 選擇操作

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

Step 8 更新當前最優解

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

Step 9 迭代

重復Step 4～Step 8，種群得到不斷進化，不斷更新best_fit 和best_ind，直到適應度函數最優或達到最大迭代數。

4 實例仿真

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

圖5 考慮限制空域的穿越走廊可行網絡初始規劃結果

表1 DE 算法參數設置

據上述基本設置，基于無干涉路徑點布局模型特點的差分進化算法用MATLAB 2014a 編程實現，對考慮限制空域影響的穿越走廊可行網絡規劃進行優化，優化后的穿越走廊網絡如圖6 所示。

圖6 穿越走廊可行網絡優化設計結果

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

穿越走廊網絡規劃設計方案要求符合航線網絡指標評價體系。依據航線網絡指標體系，采用網絡長度、航路利用率、網絡運行成本和非直線系數等具有代表性的航線網絡性能指標，對優化前后的穿越走廊網絡進行評價，評價結果如表2 所示。

表2 穿越走廊網絡性能指標對比

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

5 結論

為解決穿越走廊可行網絡的優化設計問題，首先，將穿越走廊優化問題轉化為無干涉路徑點布局問題，構建了無干涉路徑點布局模型，以平衡戰場空域安全與運行成本并保持在可接受的水平。然后，根據無干涉路徑點布局模型的特點，設計了適于穿越走廊優化問題的個體評價標準和個體修復算子，進而采用DE 算法對無干涉路徑點布局優化問題進行求解。實例分析表明，較之于穿越走廊可行網絡初始規劃結果，基于DE 算法的無干涉路徑點布局優化的各項性能指標都得到了明顯改善，將其應用于穿越走廊優化設計是可行的，也是有效的。