基于模擬退火算法的兵力投送研究

王許來，盧天鳴，李宏偉

(1.解放軍理工大學 野戰(zhàn)工程學院，南京　210007； 2.南京理工大學 機械工程學院，南京　210094)

基于模擬退火算法的兵力投送研究

王許來1，盧天鳴2，李宏偉1

(1.解放軍理工大學 野戰(zhàn)工程學院，南京210007； 2.南京理工大學 機械工程學院，南京210094)

摘要：陸軍航空兵已經(jīng)成為我陸軍優(yōu)先發(fā)展的兵種，兵力投送則是陸軍航空兵重點發(fā)展之一，如何既能節(jié)省軍費又能快速投送兵力至指定地域；運用模擬退火算法的技術對其路徑進行優(yōu)化從而獲得最優(yōu)解；最后通過實例驗證了模擬退火算法在兵力投送中的應用價值，從結果可知，模擬退火算法對于兵力投送的最優(yōu)路徑選擇有其明顯的優(yōu)勢。

關鍵詞：兵力投送； 模擬退火； 最優(yōu)路徑

本文引用格式：王許來，盧天鳴，李宏偉.基于模擬退火算法的兵力投送研究[J].四川兵工學報，2015(12):126-129.

Citation format:WANG Xu-lai, LU Tian-ming, LI Hong-wei.Research of Force Projection Based on Simulated Annealing Algorithm[J].Journal of Sichuan Ordnance,2015(12):126-129.

Research of Force Projection Based on Simulated Annealing Algorithm

WANG Xu-lai1, LU Tian-ming2, LI Hong-wei1

(1.Field Engineering College, PLA University of Science and Technology, Nanjing 210007, China;

2.School of Mechanical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China)

Abstract:Army aviation has become a prior development arm of services in our army, force projection is one of the critical points in army aviation. How fast can we deliver forces to the designated area and saves military expenditure? By using simulated annealing algorithm technology, we optimized force delivery path and then acquired the optimization result. The simulated annealing algorithm in military application value delivery was verified by an example. From the result we can see that simulated annealing algorithm has its own advantage to solve the problem about force projection.

Key words:force projection; simulated annealing; optimal routine

我國作為陸疆和海疆大國，陸上與14個國家接壤，除北方邊界外，在其他所有方向上，我國都面臨著非常惡劣的潛在安全威脅[1]。為適應新軍事變革,陸軍航空兵成為我國優(yōu)先發(fā)展的軍種[1]。陸軍航空兵作為新興的兵種，具有快速反應、靈敏多能的優(yōu)點，對于應對突發(fā)事件和戰(zhàn)場兵力投送有重要意義[2]。戰(zhàn)場兵力投送是陸軍航空兵的重要戰(zhàn)略任務，對于兵力投送問題的研究，美軍最早提出了兵力投送理論，開發(fā)了一系列配套的兵力投送模型，為兵力投送的研究和實踐奠定了基礎[3]。美軍事交通管理司令部在1997年初基本建成了兵力投送模型，之后又有多個升級版本，其結構和功能都已趨健全[4]。法軍在80年代初期也著手在陸軍總部一級建成一個軍交自動化系統(tǒng)，根據(jù)作戰(zhàn)預案擬制部隊輸送計劃[5]。

國內(nèi)也開展了相應的研究，在兵力投送交通理論方面，軍械工程學院張?zhí)炱降妊芯苛斯繁ν端椭械亩匡L險分析模型[6],針對選擇的運輸路線進行了危險識別等。在軍運物資投送方面，后勤工程學院樊榮等設計了油料投送模型，分析了最優(yōu)投送方案[7]。兵力投送交通分析研究方面，郭樹桂教授等所編寫的《地理環(huán)境對陸上武器裝備影響的建模研究》中建立了部隊輪式車和履帶式車輛的速度模型[8]。以上研究這對分析最短時間有著極大的應用價值，但是可以看出，以上研究僅針對公路兵力投送的問題，并沒有談及陸航部隊的問題。由于直升機航程較短，載荷量小，在兵力投送過程具有其獨特的限定條件，因此如何有效地利用有限的航程完成兵力投送任務，成為陸軍航空兵部隊亟待解決的問題。

兵力投送問題實質(zhì)上就是最優(yōu)路徑問題，對于最優(yōu)路徑問題，模擬退火算法是一個比較高效的求解方式。因此，本文開展了基于模擬退火算法的陸航部隊兵力投送最優(yōu)路徑研究。

1兵力投送問題的描述及數(shù)學模型

兵力投送是指一個國家各個戰(zhàn)區(qū)為了遂行多樣化軍事行動將作戰(zhàn)人員、物資、裝備，向指定地區(qū)快速移動的行動，是一種戰(zhàn)略戰(zhàn)役范圍內(nèi)的兵力機動，具有規(guī)模大、距離遠、速度快等特點，是保障軍隊快速反應、搶占先機的首要選擇，也是保障我軍在廣闊空間完成多樣化軍事任務的有效支撐[9]。兵力投送可分為：從一點出發(fā)投送兵力至一個地點；從一點出發(fā)投送兵力至多個地點；從多點出發(fā)投送兵力至一個地點；從多點出發(fā)投送兵力至多個地點。第1種情況是最基礎的情況，也是最簡單的情況；第2種情況較為復雜，涉及到最優(yōu)路徑的選擇；第3種情況是第一種情況的簡單重復；第四種情況則是第二種情況的重復。因此，本文針對第二種情況進行研究。

如圖1所示，節(jié)點1為兵力補給站，假定執(zhí)行任務單位A的行軍計劃是將兵力投送至若干觀察站，要求選擇最優(yōu)路徑進行兵力投送，然后返回節(jié)點1。

圖1　兵力分布

(1)

由于在兵力投送中可能會遇到敵防空火力打擊的影響，有一定的風險，所以在計算最優(yōu)路徑時要考慮選擇路徑時的風險系數(shù)。假設敵偵察點的坐標為r0(x0,y0)，在作戰(zhàn)區(qū)域任一點坐標為r(x,y)，被探測概率為Pd(x,y)?？梢燥@見，被探測概率Pd與節(jié)點距敵偵察點距離l0有關，則

(2)

不同的危險系數(shù)在路徑選擇過程中，應當體現(xiàn)為不同的加權系數(shù)w(x,y)

(3)

其中：w∈[1,∞)。當被探測概率為0時，加權系數(shù)為1，即不加權；當被探測概率為1時，加權系數(shù)趨于無窮，即默認直升機被敵軍擊落。加權后的距離公式可定義為

(4)

其中：l代表投送順序相鄰兩點間的路徑。則基于危險系數(shù)的最優(yōu)路徑模型為

(5)

由于存在風險因素，所以兵力投送的最短路徑將發(fā)生變化，較不考慮風險因素的路徑而言，L′≥L。

在短時間間隔內(nèi)，作戰(zhàn)區(qū)域內(nèi)的戰(zhàn)場態(tài)勢不隨時間變化，作戰(zhàn)區(qū)域內(nèi)每一點距敵觀察點的距離固定不變，則每一點的危險系數(shù)不變，加權后的距離可由式(4)得到，此時基于危險系數(shù)的最優(yōu)路徑模型退化為式(1)的最優(yōu)路徑模型。

在實際作戰(zhàn)時，敵軍會采用包括偵察機在內(nèi)的多種手段進行偵察，這時就出現(xiàn)了敵軍的移動偵察點，作戰(zhàn)區(qū)域內(nèi)每一點距敵觀察點的距離是是時變的，相應的每一點的危險系數(shù)也在變化。式(2)改進為

(6)

加權系數(shù)、節(jié)點距離以及最優(yōu)路徑模型也隨之變化

(7)

(8)

(9)

時變最優(yōu)路徑模型的求解需要考慮許多影響因素，包括敵移動偵察點出發(fā)時間、速度，我軍直升機出發(fā)時間、速度等等，計算復雜，在這里不進行討論。由于基于危險系數(shù)的最優(yōu)路徑模型可以退化為如式(1)的最優(yōu)路徑模型，因此，以最基礎的式(1)所示的最優(yōu)路徑模型為例進行討論。

2兵力投送模擬退火算法求解方法步驟

模擬退火算法(Simulated Annealing,SA)是基于Monte Carlo 迭代解策略的一種隨機尋優(yōu)算法,其出發(fā)點是基于物理中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性。SA 算法由某一較高初溫開始,結合具有概率突跳特性的Metropolis抽樣策略在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解,伴隨溫度參數(shù)的不斷下降重復抽樣過程,最終得到問題的全局最優(yōu)解。從算法結構知,新狀態(tài)產(chǎn)生函數(shù)、新狀態(tài)接受函數(shù)、退溫函數(shù)、抽樣穩(wěn)定準則和退火結束準則( 簡稱三函數(shù)兩準則)以及初始溫度是直接影響算法優(yōu)化結果的主要環(huán)節(jié)[10-11]。

兵力投送的SA算法的計算步驟描述如下：

1) 初始化。任意選取初始路徑Oi∈S，S={O1,O2,…,On}是所有可能的路徑組成的集合。給定初始溫度T0、退溫參數(shù)α,一般取α∈[0.80, 0.95]和終止溫度Tf，令迭代指標k=0,Tk=T0。

2) 在第i次投送順序中任意變換其中兩個目標點的投送順序，隨機產(chǎn)生一個新路徑Oj∈N(Oi)(N(Oi)表示Oi的領域)，計算路徑增量ΔL=L(Oj)-L(Oi)。

4) 若達到熱平衡 (內(nèi)循環(huán)次數(shù)大于n(Tk))轉(zhuǎn)5)，否則轉(zhuǎn)2)。

5) 降低Tk，令Tk=Tk-1·α,k=k+1，若Tk

兵力投送的模擬退火算法流程如圖2所示。

圖2　模擬退火算法流程

3基于模擬退火算法的兵力投送求解

兵力補給站和觀察站的坐標如表1所示。如圖3所示為基于Matlab得到的兵力投送問題模擬退火算法求解結果。如圖3(a)所示，利用模擬退火算法可以求得兵力投送的路徑,由圖3(b)可以看出當模擬退火算法在對10個節(jié)點的路徑求解經(jīng)過40步后趨于穩(wěn)定，不再變化，說明在退火過程中溫度已達到我們所期望的最低，也就是路徑達到最優(yōu)?？梢钥闯觯媚M退火算法求解兵力投送問題是有效可行的。

表1　觀察站坐標

圖3　兵力投送最優(yōu)路徑結果

4結論

理論上，利用模擬退火算法能夠解決關于兵力多點投送的問題，并能得到近似最優(yōu)解，這不僅可以節(jié)省資金并且能夠充分的去保障作戰(zhàn)，還可以提高作戰(zhàn)的效率，在處理此種小規(guī)模組合優(yōu)化問題中，模擬退火算法的優(yōu)勢顯而易見。

兵力投送過程中，風險是隨著時間的變化而變化的，如何準確把握這種變化關系對實際作戰(zhàn)中的兵力投送有著實際意義的指導，不僅可以更大程度的規(guī)避風險，還可以節(jié)省更多的資金快速進行兵力投送，這也是下步需要解決的關于風險隨時間變化的情況下如何選擇最短路徑以便于快速的投送兵力問題。

參考文獻：

[1]王智忠.各國陸軍轉(zhuǎn)型重點 我國優(yōu)先發(fā)展兵種[J].國防科技工業(yè)，2010(9):37-38.

[2]新聞110,西路尖銳前線,解放軍陸軍航空兵：快速反應和強大突擊力新型陸軍[EB/OL].[2011-11-09].http://junshi.xilu.com/2010/1104/news_343_119282.html.

[3]Trovato K I,Dorst L.Differential A*[J].IEEE Transactions on Knowledge and Data Engineering,2002,14(6):1218-1219.

[4]羅相德.作戰(zhàn)力量投送[M].北京：軍事科學出版社,2003.

[5]寇世強.一體化聯(lián)合作戰(zhàn)兵力投送研究[D].北京：國防大學,2005.

[6]張?zhí)炱?，楊毅，李雪?公路兵力投送中的定量風險分析模型[J].兵工自動化,2007,26(8):18-19.

[7]樊榮，馮刊民，羅俊.軍隊油料投送方案模型化研究[J].物流技術，2006(2):93-95.

[8]郭樹桂.地理環(huán)境對陸上武器裝備影響的建模研究[M].北京：解放軍出版社,1998.

[9]李永軍.跨區(qū)機動公路運輸兵力投送問題研究[J].汽車運用，2011(8):12-13.

[10]馮劍、岳琪.模擬退火算法求解TSP問題[J].森林工程2008(1)：153-154.

[11]汪定偉，王俊偉，王洪峰.智能優(yōu)化方法[M].北京：高等教育出版社，2007.(責任編輯楊繼森)

【基礎理論與應用研究】

中圖分類號：O229

文獻標識碼：A

文章編號：1006-0707(2015)12-0126-04

doi:10.11809/scbgxb2015.12.031

作者簡介：王許來(1988—)，女，碩士研究生，主要從事作戰(zhàn)工程保障與國防工程系統(tǒng)分析研究。

收稿日期：2015-05-25