目標火力分配的優(yōu)化算法

文/陳龍馬亞平

目標火力分配的優(yōu)化算法

文/陳龍1馬亞平2

火力分配問題是一個規(guī)劃問題，火力分配優(yōu)化問題是作戰(zhàn)仿真中的一個重要內(nèi)容，其算法的優(yōu)劣決定了火力分配優(yōu)化結(jié)果，該結(jié)果是影響戰(zhàn)爭勝敗的關(guān)鍵因素。本文通過分析目標火力分配優(yōu)化算法發(fā)展歷程，將火力分配優(yōu)化算法歸納總結(jié)為常規(guī)解析火力分配法、智能進化火力分配法、混合式火力分配法三種方法，并分析總結(jié)各自的特點，最后對MOEA/D優(yōu)化算法進行了初步研究。

火力分配 優(yōu)化算法 MOEA/D算法

集中優(yōu)勢兵力，以多擊少，這是戰(zhàn)爭中一條基本作戰(zhàn)原則。偉大的軍事家毛澤東說過：“集中優(yōu)勢兵力，各個殲滅敵人。”克勞塞維茨也指出：“數(shù)量上的優(yōu)勢應(yīng)該看作是基本原則，不論在什么地方都應(yīng)該是首先和盡量爭取的。”時至今日，如何精確用兵，做到戰(zhàn)斗效能精確匹配、數(shù)量規(guī)模合理夠用，量敵用兵，保存戰(zhàn)力，以最小代價奪取最大作戰(zhàn)效果是對這一基本原則的發(fā)展和延伸。隨著信息化武器裝備的不斷更新?lián)Q代，其相應(yīng)的打擊能力也不斷提高，火力分配的優(yōu)化直接影響著戰(zhàn)爭的進程和勝負。實際作戰(zhàn)中，由于作戰(zhàn)火力單元資源有限，難以做到對所有目標進行均勻打擊和有效覆蓋。因此需要在滿足火力資源約束條件下，緊緊圍繞作戰(zhàn)使命，合理分配火力，以綜合效能作用于敵要害和關(guān)節(jié)，爭取以最小的代價最大限度地達成作戰(zhàn)使命。火力分配問題實際上是一個多目標優(yōu)化問題，國內(nèi)外針對火力分配問題的研究非常廣泛，而且根據(jù)不同的火力和目標提出相應(yīng)的優(yōu)化算法。很多算法已經(jīng)被運用于火力分配優(yōu)化中，大致可以分為常規(guī)解析火力分配法、智能進化火力分配法、混合式火力分配法三種方法。

1 常規(guī)解析火力分配法

常規(guī)解析火力分配法是將求解問題抽象化、形象化形成數(shù)學(xué)表達式，利用若干個數(shù)學(xué)表達式建立相應(yīng)的數(shù)學(xué)模型，用數(shù)學(xué)的方法進行求解得出最優(yōu)解。常規(guī)解析法常見的有線性規(guī)劃法、動態(tài)優(yōu)化法、序列算法、馬兒可夫動態(tài)決策、模糊AHP、可行方向法等。

1970年，Matlin S[1]、1986年，Lloyd S P等[2]通過將分配問題按序排列，選取各火力單元的失敗概率，使用最小失敗概率進行優(yōu)化選取目標與火力分配組合，該方法得到結(jié)果比較理想，但是算法的收斂慢、效率不高。

1977年，Nash[3]最早嘗試解決有約束條件下資源優(yōu)化配置問題。1993年，Libby V[4]通過大量計算采用線性規(guī)劃研究火力分配問題，獲得火力分配的最佳決策方法。2001年，Dasarathy B V[5]總結(jié)前人的基礎(chǔ)上提出啟發(fā)式近似法，試圖減小線性規(guī)劃的復(fù)雜計算問題，但是問題沒有得到很好解決，精度也有待提高。

2004年，楊建兵等[6]結(jié)合層次分析法和線性規(guī)劃法，分析坦克連沖擊火力分配問題，最后使用軟件以報告文件或圖形的方式顯示火力分配結(jié)果。

2006年，紀兵等[7]利用馬爾可夫決策理論建立坦克連的動態(tài)火力分配模型, 使結(jié)果更符合戰(zhàn)場動態(tài)環(huán)境情況的隨機問題；2009年，陳偉兵等[8]將馬爾可夫決策理論運用到炮兵群火力分配中，建立了炮兵群動態(tài)火力分配模型，通過例子驗證該方法的可行性。

2007年，黃力偉等[9]針對目標函數(shù)是線性或非線性的一類火力分配問題, 提出了虛擬火力單位或目標的方法, 將問題轉(zhuǎn)化為能夠用匈牙利算法求解的指派問題, 該方法簡單、易于計算, 有一定的應(yīng)用價值。

2011年，王凈等[10]基于動態(tài)規(guī)劃算法對艦空導(dǎo)彈火力分配模型進行研究, 給出了動態(tài)規(guī)劃的算法，得到最優(yōu)火力分配結(jié)果。

2013年，丁紅巖等[11]針對水面艦艇編隊攻潛火力分配問題，運用模糊AHP 方法，通過構(gòu)建攻潛火力分配模型，進而建立模糊評判矩陣，確定各個評價因素的權(quán)重，最后制定最優(yōu)的火力分配方案。該方法可操作性較強，為反潛作戰(zhàn)提供一定的輔助決策。同年，梁波等[12]考慮目標價值指標、武器對目標的單位毀傷概率以及目標防衛(wèi)能力, 提出了基于可行方向法的火力分配模型。通過仿真實例驗證模型及其算法有效。

2016年，譚樂祖等[13]考慮分析多目標規(guī)劃模型的約束條件和目標函數(shù)基礎(chǔ)上，建立多目標整數(shù)規(guī)劃模型，求解火力分配問題。

圖1

常規(guī)解析火力分配法要求數(shù)學(xué)邏輯嚴謹、有明確的數(shù)學(xué)表達式，能夠分析建立適當(dāng)?shù)臄?shù)學(xué)模型，而且其龐大的計算量影響到計算的效率不高，在解決大規(guī)模火力分配問題時，問題更加突出，難以滿足現(xiàn)代戰(zhàn)爭實時性的要求。

2 智能進化火力分配法

隨著科學(xué)技術(shù)的不斷發(fā)展，常規(guī)解析火力分配法的缺陷得到一定程度得到解決，智能進化算法的運用使得火力分配優(yōu)化問題解決空間得到迅速擴展， 不斷發(fā)展完善的優(yōu)化算法通過計算機得以實現(xiàn)，這些智能的進化算法為解決復(fù)雜、非線性優(yōu)化問題開辟了新的路徑。其中常見的有粒子群算法、人工神經(jīng)網(wǎng)絡(luò)法、差分進化算法、遺傳算法、禁忌搜索算法和影響網(wǎng)絡(luò)[14]等。

智能進化算法是以模擬自然界生物進化過程的優(yōu)化算法，出發(fā)點是模擬自然界生物群體生活時，個體之間的互相交流與合作，利用個體的簡單、有限行為拓展到群體的、完成復(fù)雜任務(wù)的整體能力。如鳥群算法、蟻群算法、蜂群算法、粒子群算法、螢火蟲算法等，以固體退火理論及系統(tǒng)穩(wěn)定性理論為基礎(chǔ)的模擬退火算法、Hop fi eld 神經(jīng)優(yōu)化算法，以及遺傳算法、免疫算法、禁忌搜索算法等，都可以歸結(jié)為智能進化算法。進化計算在發(fā)展的過程中形成了進化策略、進化編程和遺傳算法三類主要的算法。這些算法都是基于種群的啟發(fā)式算法，使用交叉算子、變異算子和選擇算子搜索問題。進化算法的一般執(zhí)行過程如圖1所示。

不同的進化算法主要的區(qū)別在于編碼形式和算子的執(zhí)行方式不同。由于不同生物個體之間差異較大，個體的功能描述也千差萬別，但在進化算法方面有其統(tǒng)一的框架模式，都是基于概率的隨機搜索方式，各種不同算法在結(jié)構(gòu)、內(nèi)容和計算方法等方面具有較大的相似性。

1991年，Dorigo等[15]受到自然界螞蟻覓食行為的啟發(fā)，通過模擬螞蟻覓食行為，提出了蟻群優(yōu)化算法。

1995年，Kennedy J等[16]基于對鳥群捕食行為的研究第一次提出了粒子群優(yōu)化算法,該算法具有操作、編程簡單的特點。

2005年，余有明等[17]提出了多種群偽并行混沌遺傳算法。結(jié)合多群體偽并行性和混沌運動隨機性, 將混沌變尺度映射機理應(yīng)用到種群優(yōu)化進化。 一定程度提高了收斂速度和最優(yōu)解搜索成功率。

2006年，丁鑄等[18]將改進型微粒群算法運用到防空火力分配問題中，并和其他算法對比，該算法具有較快收斂性和較高收斂精度。同年，李丹等[19]基于神經(jīng)網(wǎng)絡(luò)TSP 算法解決防空作戰(zhàn)火力分配問題。

2008年，陳華東等[20]使用混合粒子群算法的求解多平臺多武器的火力分配問題, 該算法在規(guī)模復(fù)雜問題中體現(xiàn)算法的優(yōu)越性。

2010年，傅調(diào)平等[21]提出基于自適應(yīng)編碼的遺傳算法解決火力分配問題, 自適應(yīng)選擇、交叉和變異, 具有較快的收斂速度，較好地避免陷入局部最優(yōu)。

2012年，隋永華等[22]提出了一種新的基于微分進化算法的求解方法。在分析基本微分進化算法的基礎(chǔ)上，改進利用自由差分提高算法收斂速度，增設(shè)單體隨機變異彌補種群多樣性降低的缺陷，最后進行了遺傳算法、基本微分進化算法對比測試，結(jié)果表明改進的微分進化算法更加有效；同年，韓占朋等[23]結(jié)合混合蛙跳算法對防空作戰(zhàn)火力分配問題進行了研究，通過引入可變步長，使多點變異方式轉(zhuǎn)換到單點變換方式進行改進混合蛙跳算法求解模型，取得較好的收斂速度和精度。

2016年，董朝陽等[24]提出一種改進遺傳算法。通過構(gòu)造改進的適應(yīng)度函數(shù)，從而提高算法的收斂精度，通過計算染色體的相似度來選擇交叉或變異操作，提高了算法的尋優(yōu)性和效率。

智能進化火力分配法拓寬了火力分配問題的廣度和深度，一定程度上提高了速度和精度，為現(xiàn)代復(fù)雜戰(zhàn)場環(huán)境下的火力分配問題提供了新的研究思路和手段。

3 混合式火力分配法

混合式火力分配法是結(jié)合了常規(guī)解析火力分配法和智能進化火力分配法這兩種方法，通過有效組合運用常規(guī)解析火力分配法和智能進化火力分配法，使得火力分配優(yōu)化問題得到進一步完善的解決，該混合式火力分配法具有上述兩種不具有的收斂速度較快、尋優(yōu)能力強、魯棒性強的優(yōu)勢，是目前解決火力分配優(yōu)化問題的可靠方法，也是現(xiàn)階段專家學(xué)者研究和關(guān)注較多的方法。常見的混合式火力分配法有如下。

2007年，馬宏斌等[25]采用改進型遺傳和蟻群混合算法對防空兵群火力分配問題進行研究，將蟻群算法的雙向圖引入改進型的遺傳算法中，將武器分配優(yōu)化轉(zhuǎn)化為雙向?qū)ふ易罴崖窂剑苊庀萑刖植孔顑?yōu)和提高了搜索效率；同年，丁鑄等[26]結(jié)合禁忌搜索和微粒群優(yōu)化算法，提出混合優(yōu)化策略用于解決目標火力分配問題，提高了原算法的性能。

2008 年，程杰等[27]結(jié)合粒子群算法和遺傳算法，將遺傳算法中的變異操作引入粒子群算法中，增強全局搜索能力，有助于跨出局部最優(yōu)。

2011年，曾松林等[28]基于動態(tài)博弈建立防空火力單元分配模型，利用雙矩陣博弈納什均衡建立納什均衡二次規(guī)劃，并利用混合粒子群算法進行求解，具有較高的應(yīng)用價值。

2012年，孫媛等[29]提出了一種改進的混合遺傳算法，將模擬退火算法與遺傳算法相結(jié)合，引入小生境技術(shù)解決早熟問題，然后利用模擬退火算法解決陷入局部最優(yōu)問題，使得問題得到較好的解決。

2013年，羅佳等[30]結(jié)合免疫遺傳算法和量子遺傳算法，利用免疫克隆、免疫記憶、免疫平衡算子改善優(yōu)化量子遺傳算法，引入先驗知識和局部最優(yōu)解來提高算法的收斂精度、收斂速度和穩(wěn)定性。

2016年，周興旺等[31]從博弈論的角度研究火力分配問題，建立基于貝葉斯混合博弈的火力分配模型。通過構(gòu)造貝葉斯混合博弈樹，利用混合粒子群算法求解，有效性好，有較高的理論應(yīng)用價值。

4 MOEA/D進化算法

實踐中大多數(shù)優(yōu)化問題是多目標優(yōu)化問題，需要在約束條件下同時考慮多個優(yōu)化目標，且大多數(shù)目標并不是獨立存在的，每個目標都有不同的意義和量綱，各個目標之間存在相互耦合、競爭的關(guān)系。傳統(tǒng)求解多目標優(yōu)化問題的方法是用權(quán)重系數(shù)將各個目標聚合為一個單目標，然后用單目標優(yōu)化方法來求解。主要問題有：一是由于這些子目標往往相互沖突或關(guān)系未知，不存在或很難確定是否存在單個最優(yōu)解使得多個目標同時獲得最優(yōu)，此時需要通過多次設(shè)置不同的權(quán)重來得到多個“最優(yōu)解”來進行比較，這給求解多目標優(yōu)化問題的求解帶來了巨大的計算量；二是單個優(yōu)化目標經(jīng)過數(shù)學(xué)建模，具有相應(yīng)的目標函數(shù)，而多目標函數(shù)往往高度非線性、不可微分和多極值，這給優(yōu)化問題帶來了極大的困難；三是各目標之間相互制約，對其中一目標優(yōu)化必須犧牲其他目標為代價。

創(chuàng)傷性顱內(nèi)損傷患者所用全身用抗感染藥各亞類中，金額排序前3位的分別是第三代頭孢菌素類藥物（1 622.98萬元）、碳青霉烯類藥物（1 023.96萬元）、第二代頭孢菌素類藥物（493.91萬元）；DDDs排序前3位的分別是第三代頭孢菌素類藥物（94 635.5）、第二代頭孢菌素類藥物（28 962.6）、氟喹諾酮類藥物（22 586.3），詳見表7。

2007年，Zhang等[32]提出了一種新的多目標優(yōu)化算法框架—MOEA/D。MOEA/D先將MOP分解為多個標量優(yōu)化子問題；每個子問題通過交換各自解的信息來加快搜索速度。為了避免算法早熟，解信息的交換一般發(fā)生在臨近子問題之間，而臨近子問題通常通過聚合系數(shù)的歐式距離決定的，這是因為我們假設(shè)較近的聚合系數(shù)產(chǎn)生的子問題的最優(yōu)解也較相近。每個子問題保留的解都是迄今為止對應(yīng)聚合系數(shù)最好的解。可見，MOEA/D的基礎(chǔ)是分解策略。

MOEA/D將MOP分解為多個標量優(yōu)化子問題指的是：MOEA/D沒有將MOP作為一個整體進行處理，而是將一個MOP分解為N個單目標優(yōu)化問題，其中分解是通過聚合方法實現(xiàn)的。常見的聚合方法有：加權(quán)和方法、切比雪夫方法為例說明。

加權(quán)和（weighted sum）方法：

標量優(yōu)化問題的最優(yōu)解是一個Pareto最優(yōu)解；而Pareto最優(yōu)解可能是某個聚合標量優(yōu)化問題的最優(yōu)解。因此，PF的逼近可以轉(zhuǎn)化為多個標量優(yōu)化子問題。這也是很多傳統(tǒng)數(shù)學(xué)規(guī)劃法逼近PF的基本思想。可見，將MOP分解為多個標量優(yōu)化問題是個很好的求解方法。

本文在借鑒國內(nèi)外相關(guān)領(lǐng)域研究成果的基礎(chǔ)上，嘗試將火力分配的優(yōu)化算法進行系統(tǒng)整合。從算法概念、模型理論和發(fā)展情況方面對火力分配的優(yōu)化算法進行了初步研究，希望能借此開拓思路，為進一步研究航母編隊反潛作戰(zhàn)火力分配的應(yīng)用打下理論基礎(chǔ)。

[1]Matlin S.A Review of the Literature on the Missile-Allocation Problem[M]. INFORMS,1970.

[2]Lloyd S P,Witsenhausen H S.Weapons allocation is NP-complete[C].IEEE Summer Conference on Simulation. 1986.

[3]Nash J M.Optimal allocation of tracking resources[C].Decision and Control Including the,Symposium on Adaptive Processes and A Special Symposium on Fuzzy Set Theory and Applications,1977 IEEE Conference on.IEEE,1977：1177-1180.

[4]Libby V.Information-based sensor management[J].Proc Spie,1993,1955(1955)：156-164.

[5]Dasarathy B V.Distributed resource allocation under communication constraints[J].Proc Spie,2001：213-224.

[6]楊建兵,李大鵬,王忠義,杜濤.線性規(guī)劃在最優(yōu)火力分配輔助決策中的應(yīng)用,2004(19)：550-560．

[7]紀兵,侯勝高,劉學(xué)銀.基于馬爾可夫決策過程的坦克連動態(tài)火力分配方法研究[J].火力與指揮控制,2008,31(07)：15-19.

[8]陳偉兵,蔡向陽,姜博軒.基于馬爾可夫決策過程的炮兵群動態(tài)火力分配方法[J].國防科技,2009,30(04)：56-58．

[9]黃力偉,許品剛,王勤.基于匈牙利算法求解的火力分配問題[J].火力與指揮控制,2007,32(06)：25-28.

[10]王凈,戰(zhàn)凱,晏峰.基于動態(tài)規(guī)劃算法的艦空導(dǎo)彈火力分配模型研究[J].艦船電子工程,2011,200(02)：24-26.

[11]丁紅巖,董曉明,寇祝.基于模糊AHP的水面艦艇編隊攻潛武器分配[J].指揮控制與仿真,2013,35(04)：138-142．

[12]梁波，段然基于可行方向法的火力分配模型[J].指揮信息系統(tǒng)與技術(shù),2013,4(02)：30-32．

[13]譚樂祖,張 崢,孫仲元.多型反艦導(dǎo)彈混合攻擊異型艦艇編隊多目標整數(shù)規(guī)劃火力分配模型[J].兵工自動化,2016,35(08)：47-49．

[14]孫清.基于影響網(wǎng)絡(luò)和分布估計算法的空襲火力分配方法研究[D].國防科學(xué)技術(shù)大學(xué),2011.

[15]L.M.Gambardella,E.Taillard,and G.Agazzi.MACS-VRPTW：A multiple ant colony system for vehicle routing problems with time windows.In D.Corne,M.Dorigo,F. Glover,D.Dasgupta,P.Moscato,R. Poli,and K.V.Price,editors,New Ideas in Optimization,McGraw-Hill,1999,pp.63-76.

[16]Kennedy J,Eberhart R.Particle swarm optimization[C].IEEE International Conference on Neural Networks,1995.Proceedings.IEEE Xplore,1995：1942-1948 vol.4.

[17]余有明,劉玉樹,劉昆.混沌偽并行遺傳算法及其在火力分配優(yōu)化中的應(yīng)用[J].北京理工大學(xué)學(xué)報,2005,25(12)：1047-1051．

[18]丁鑄,馬大為,張學(xué)鋒,徐志強.基于改進微粒群算法的火力分配[J].彈箭與制導(dǎo)學(xué)報,2006：578-580．

[19]李丹,王巨海,陳振雷.基于神經(jīng)網(wǎng)絡(luò)TSP算法的防空作戰(zhàn)火力分配[J].火力與指揮控制,2006,31(04)：42-45．

[20]陳華東,王樹宗,王航宇.基于混合粒子群算法的多平臺多武器火力分配研究[J].系統(tǒng)工程與電子技術(shù),2008,30(05)：880-883．

[21]傅調(diào)平,陳建華,李剛強.基于動態(tài)自適應(yīng)遺傳算法的艦艇防空火力分配[J].廣西師范大學(xué)學(xué)報：自然科學(xué)版,2010,28(03)：187-190．

[22]隋永華,郭雷,俞利新,王海晏.改進的微分進化算法求解空戰(zhàn)火力分配問題[J].火力與指揮控制,2012,37(12)：118-121．

[23]韓占朋,王玉惠,姜長生,吳慶憲.用混合蛙跳算法的智能防空火力分配[J].電光與控制,2012,19(12)：10-13．

[24]董朝陽,路遙,王青.改進的遺傳算法求解火力分配優(yōu)化問題[J].兵工學(xué)報,2016,37(01)：97-102．

[25]馬宏斌,王玉生.基于改進型遺傳和蟻群混合算法的防空兵群火力分配模型[J].武器裝備自動化,2007,26(07)：3-4.

[26]丁鑄,馬大為,于存貴,張學(xué)鋒.基于禁忌搜索與微粒群優(yōu)化算法的混合優(yōu)化策略算法在目標分配問題上的應(yīng)用[J].兵工學(xué)報,2007,28(09)：1127-1131．

[27]程杰,李勇,任偉.改進粒子群算法在防空火力分配中的應(yīng)用[J].武器裝備自動化,2008,27(04)：10-11．

[28]曾松林,王文惲,丁大春,張毅.基于動態(tài)博弈的目標分配方法研究[J].電光與控制,2011,18(02)：26-29．

[297]孫媛,王毅,李季穎.改進的混合遺傳算法在防空目標分配中的應(yīng)用[J].四川兵工學(xué)報,2012,33(09)：113-116．

[30]羅佳,薛青,王之騰,張宏軍.作戰(zhàn)仿真中火力分配優(yōu)化算法研究[J].計算機仿真,2013,30(10)：62-66．

[31]周興旺,從福仲,龐世春,侯滿義,辛騰達.基于貝葉斯混合博弈的空襲火力資源分配決策模型[J].火力與指揮控制,2016,41(07)：18-22．

[32]Zhang Q,Li H. 2007.MOEA/D：A multiobjective evolutionary algorithm based on decomposition[J].IEEE Trans Evol Comput,11(06)：712-731.

作者單位
1.國防大學(xué)研究生院 北京市 100091
2.國防大學(xué)公共平臺中心 北京市 100091

陳龍（1988-），男，福建省仙游縣人。碩士在讀，現(xiàn)為國防大學(xué)研究生。主要研究方向為作戰(zhàn)模擬系統(tǒng)工程。