基于神經網絡的部隊投送路徑優化方法研究

汪 欣, 王廣東

(1.陸軍軍事交通學院學員五大隊研究生隊，天津 300161；2.陸軍軍事交通學院軍事交通運輸研究所，天津 300161)

現代戰爭凸顯速度制勝，快速投送是決定戰爭勝負的關鍵因素。我軍目前正在大力發展投送力量的建設，以提升部隊全域機動、立體攻防的作戰能力[1]。隨著我國國家利益的拓展和戰略投送能力的提高，部隊投送范圍逐漸由本土向跨區、跨境延伸，投送環境發生了巨大改變，日益呈現出路網大規模化和動態化特點，并且對最優化路徑計算的時效性有較高的要求。對路徑優化方法的研究應主動適應變化，在充分考慮約束條件的前提下結合搜索空間大小建立合適的搜索模型[2]。由于戰場環境復雜多變，部隊在龐大、復雜的路網體系中實施投送，需要運用高靈敏性、智能化方法來選出最優投送路徑，傳統的Dijkstra算法、Ford算法、SPFA算法、Floyd算法[3]在求解最短路徑時，運算量較大、得出優化結果時間較長，不能并行計算且一般只適用于解決線性問題，而神經網絡算法作為一種模擬人腦工作原理的算法，具有并行性、非線性運算等能力，可方便地用于大規模復雜問題求解。

1 建立神經網絡算法模型

建立神經網絡算法模型第1步是選擇合適的神經網絡類型，第2步是進行凸優化處理，第3步是利用MATLAB拓撲處理路網并進行神經網絡數據訓練。

1.1 選擇神經網絡類型

神經網絡的結構可分為兩類：一類是前饋式神經網絡，一類是遞歸式神經網絡[4]。前饋式神經網絡神經元的輸出不對自身改變做出影響；遞歸式神經網絡神經元的輸出會反饋到神經元的輸入上，神經元可根據自身情況進行調節。分析二者的差別，在解決投送路徑優化問題時，遞歸式神經網絡更適合。本文選取遞歸式神經網絡中的Hopfield神經網絡建立算法模型[4，5]。

1.2 目標函數凸化處理

在尋找投送最優路徑時，應先將問題轉化為凸優化問題。構建路徑選擇函數作為目標函數，此時目標函數為凸函數，再進行優化求解。

Hopfield神經網絡搜索路徑時會出現陷入極小值點的情況，因此描述平衡點穩定性時要引入能量函數[6]，將能量函數作為目標函數，則目標函數E(V)表示為：

(1)

因此，經處理之后變成帶約束的凸優化問題：

(2)

1.3 神經網絡求解

路網有n個點時需要用n(n- 1)個神經單元，路網鄰接矩陣中除對角元素外，每個元素都對應一個神經元。神經元只取值0或1兩個狀態，當Hopfield網絡收斂到穩定的平衡狀態時神經元狀態函數δij:

神經元狀態函數δij為1時弧在最優路徑上，δij為0則不在最優路徑上。

神經網絡求解關鍵一步是要設置參數標準，這里可得最優路徑的動力學方程為[7]：

(3)

(4)

式中：mij是路網各節點之間的權重，a1,a2,a3,a4是懲罰系數。求解式(3)和式(4)組成的方程組，當神經網絡收斂到穩定平衡狀態時，此時輸出神經元即是所要求的一條最優路徑。

2 MATLAB軟件處理

MATLAB軟件有著強大的數值分析、工程繪圖、設計仿真和可視化功能[8-9]，用軟件進行路網拓撲化處理，然后調用神經網絡工具箱，輸入路段參數進行數據訓練，最后對輸出神經元質量進行分析。軟件處理步驟：路網拓撲處理→Hopfield神經網絡實現→調用神經網絡工具箱→輸入數據進行訓練。

(1)路網拓撲化處理后不影響路段屬性，并且可以將復雜公路網簡化為節點互聯的拓撲圖，以便于問題求解。

(2)Hopfield神經網絡要實現網絡的穩定性，而能量函數是判定網絡穩定性的基本方法，此處能量函數為E(V)。

(3)MATLAB神經網絡工具箱中的神經網絡分3類：第1類是有輸入有輸出且有反饋，第2類是無輸入有輸出，第3類是有輸入有輸出無反饋，顯然這里應選第1類。

(4)路網拓撲圖建立后，目標函數也隨之確定，將路段實際值作為神經網絡的訓練數據來源。此時還需調整三種數據比例，即訓練數據、驗證數據以及測試數據比例；然后選取隱層神經元數量，一般取10；最后選擇訓練算法，從Levenberg-Marquardt、Bayesian Regularization、Scaled Conjugate Gradient中選擇算法，一般選取L-M(Levenberg-Marquardt)算法[9-10]。

3 任務想定及仿真實現

3.1 作戰想定及投送任務

基本作戰想定：××部隊奉命從貴陽出發，向徐州集結，遂行跨域特種打擊任務。投送任務想定：投送人員共計5 000余人、各型裝備1 000余件，采用公路投送方式。要求在×月×日×時×分前，完成全部投送任務，到達集結地域待命。

3.2 仿真實現

3.2.1 路網拓撲處理

根據投送任務想定，在實施部隊投送時一般應選擇高速公路或高等級公路進行，結合各戰區范圍內主要公路情況[11]，投送任務區域路網范圍如圖1所示。

圖1 投送任務區域路網

對此路網中有高速公路連接的重要城市進行編號，根據路網中節點相對位置和相關屬性值，神經網絡的輸入節點為路網區域中的100個節點，將路網節點距離作為神經網絡的輸入數據，如表1所示。

表1 神經網絡的輸入數據

利用MATLAB進行拓撲處理，出發地貴陽標記為節點1，目的地徐州標記為節點100。拓撲圖如圖2所示。

圖2 投送任務路網拓撲

3.2.2 神經網絡數據訓練

在神經網絡中，只有網絡有良好的收斂性，才能避免陷入極小值點而出現局部最優解的情況[12]。在尋優過程中，同一個神經網絡對數據的訓練會出現不同的結果，這是局部的極值，隨著訓練次數增多，最終可以找到全局的極值，這個極值就是最優結果。MATLAB中神經網絡訓練結果如圖3所示。

圖3 神經網絡訓練結果

3.2.3 最優化路徑的確定

從圖3中看出，該神經網絡經過58個迭代期后達到最優解。根據梯度與偏差值表現，輸出神經元大致可分為4個階段，即從局部最優到全局最優經歷了4個階段，分別如圖4所示。

圖4 路徑選擇結果

可知最優化的投送路徑為：1-9-11-41-44-46-65-68-60-67-82-81-87-100，即沿著貴陽-遵義-同仁-吉首-常德-長沙-岳陽-鄂州-黃岡-阜陽-商丘-濟寧-棗莊-徐州的方向進行投送。

3.2.4 輸出神經元質量分析

神經網絡訓練輸出數據的質量分析影響著最終優化結果，對輸出神經元質量的分析要從三類數據最佳性能驗證、驗證梯度與學習次數關系分析、三類數據回歸分析、數據誤差分析等四個方面進行，分析結果如圖5～圖8所示。

圖5 訓練、驗證、測試數據的最佳性能驗證

(1)分析三類數據的最佳性能驗證曲線(圖5)可知，可知最佳性能迭代次數為52次，迭代次數不少于52次時可以達到最佳性能，所以第58次迭代時最優結果可信度很高。從大的趨勢上看，隨著迭代次數的增加，模型在訓練集上的誤差會越來越小，但是次數顯然不會無限增大，在某個值時會不再發生明顯變化。

(2)分析驗證數據的梯度與學習次數(圖6)可知，可知迭代次數到58代時，驗證數據可信度較高。由于波動，因此會使得學習次數增多，即收斂速度變慢，不過最終其會和全量梯度下降算法一樣，具有相同的收斂性。由于目標函數為凸函數，則收斂于全局極值點。

圖6 驗證數據的梯度與學習次數

(3)根據圖7得到的結果可知，此時R值分別為0.999 50、0.998 83、 0.999 22，總體R值0.999 37，可知R值非常接近1，即MSE的值越小，其訓練效果和模型擬合的更好。由此可見，此時訓練得出的數據與模型吻合度較高，訓練效果很好。

圖7 訓練數據、驗證數據、測試數據回歸分析

(4)分析圖8誤差直方結果可知，三類數據的誤差集中在零點附近，即可認為可信度較高，得到的輸出神經元質量較好。

圖8 訓練數據、驗證數據、測試數據誤差直方

3.2.5 與傳統算法優化結果的對比

利用傳統算法如Dijkstra算法、Ford算法、SPFA算法、Floyd算法分別對路網進行最優路徑求解，以不同算法的最優路徑節點數為縱坐標、以運算時間為橫坐標，得到結果對比如表2所示。可以發現，神經網絡算法與Dijkstra算法、Ford算法、SPFA算法、Floyd算法相比，計算時間短，且最優路徑節點數最少、優化效果最好，具有較強的計算優越性。

表2 不同算法結果對比

4 結論

由于未來部隊投送會呈現距離更遠、范圍更大、路網更復雜的特點，本文采取的方法可推廣至更加復雜的公路網絡。在實際應用中還可充分利用神經網絡算法大規模并行計算優勢，組建適當規模的集群，解決更復雜、距離更遠、環節更多的路徑優化問題。