基于神經網絡的部隊投送路徑優(yōu)化方法研究

汪 欣, 王廣東

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

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

1 建立神經網絡算法模型

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

1.1 選擇神經網絡類型

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

1.2 目標函數(shù)凸化處理

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

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

(1)

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

(2)

1.3 神經網絡求解

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

神經元狀態(tài)函數(shù)δij為1時弧在最優(yōu)路徑上，δij為0則不在最優(yōu)路徑上。

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

(3)

(4)

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

2 MATLAB軟件處理

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

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

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

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

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

3 任務想定及仿真實現(xiàn)

3.1 作戰(zhàn)想定及投送任務

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

3.2 仿真實現(xiàn)

3.2.1 路網拓撲處理

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

圖1 投送任務區(qū)域路網

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

表1 神經網絡的輸入數(shù)據(jù)

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

圖2 投送任務路網拓撲

3.2.2 神經網絡數(shù)據(jù)訓練

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

圖3 神經網絡訓練結果

3.2.3 最優(yōu)化路徑的確定

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

圖4 路徑選擇結果

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

3.2.4 輸出神經元質量分析

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

圖5 訓練、驗證、測試數(shù)據(jù)的最佳性能驗證

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

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

圖6 驗證數(shù)據(jù)的梯度與學習次數(shù)

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

圖7 訓練數(shù)據(jù)、驗證數(shù)據(jù)、測試數(shù)據(jù)回歸分析

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

圖8 訓練數(shù)據(jù)、驗證數(shù)據(jù)、測試數(shù)據(jù)誤差直方

3.2.5 與傳統(tǒng)算法優(yōu)化結果的對比

利用傳統(tǒng)算法如Dijkstra算法、Ford算法、SPFA算法、Floyd算法分別對路網進行最優(yōu)路徑求解，以不同算法的最優(yōu)路徑節(jié)點數(shù)為縱坐標、以運算時間為橫坐標，得到結果對比如表2所示?？梢园l(fā)現(xiàn)，神經網絡算法與Dijkstra算法、Ford算法、SPFA算法、Floyd算法相比，計算時間短，且最優(yōu)路徑節(jié)點數(shù)最少、優(yōu)化效果最好，具有較強的計算優(yōu)越性。

表2 不同算法結果對比

4 結論

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