李亞雄，劉新學(xué)，徐 萌

(1 火箭軍工程大學(xué)，西安 710025； 2.中國人民解放軍31102部隊， 南京 210016)

?

基于分支定界和模擬退火算法的成爆彈型彈量計算模型

李亞雄1，劉新學(xué)1，徐 萌2

(1 火箭軍工程大學(xué)，西安 710025； 2.中國人民解放軍31102部隊， 南京 210016)

在多型導(dǎo)彈組合打擊模式下，對同一目標打擊存在多種混合火力彈型彈量組合方案；如何選出既滿足毀傷要求，耗彈量又盡可能少的組合方案是決策者關(guān)心的重大問題；針對該問題決策變量維數(shù)高的特點，基于分支定界算法和模擬退火算法，建立了兩種成爆彈型彈量計算模型，設(shè)計了兩種算法組合使用方法；算例分析表明：建立的模型具有較高的計算效率和全局尋優(yōu)能力，具有重要的工程應(yīng)用價值。

分支定界；模擬退火；彈型彈量

目前，對于導(dǎo)彈成爆彈量計算的研究主要基于單彈型打擊的前提，并沒有區(qū)分彈型的差異。比如，文獻[1]基于導(dǎo)彈對目標的命中彈數(shù)指標要求和單發(fā)命中概率，給出了單目標成爆彈量的計算模型。文獻[2]分析研究了目標網(wǎng)格分割粒度、仿真次數(shù)對成爆彈量計算精度的影響。文獻[3]基于對機場內(nèi)部子系統(tǒng)的串、并聯(lián)結(jié)構(gòu)與機場保障能力的關(guān)系，給出了摧毀機場目標最大保障能力的耗彈量計算模型。在上述研究中，目標毀傷效果f與成爆彈量N之間的函數(shù)關(guān)系f(N)屬于單調(diào)遞增關(guān)系，決策變量為一維變量，滿足打擊要求的最小彈量即為所需要的成爆彈量，計算結(jié)果是唯一的。在混合火力打擊條件下，由于彈型選擇的多樣性，在總耗彈量相同的情況下，滿足打擊要求的彈型彈量組合通常有多種方案。除了導(dǎo)彈數(shù)量，彈型也是重要的決策變量，變量維數(shù)的增加極大地提高了計算的復(fù)雜度。另外，在混合火力打擊模式下，“基于物理”的武器毀傷效果評估與單彈型打擊相比有著結(jié)構(gòu)性的差異，涉及目標易損性，系統(tǒng)結(jié)構(gòu)、功能評價等問題。本文重點對獲得毀傷效能評估基礎(chǔ)上彈型彈量的優(yōu)化計算問題進行研究。

1 成爆彈型彈量計算問題數(shù)學(xué)模型

1.1 成爆彈型彈量計算問題數(shù)學(xué)模型構(gòu)建

混合火力打擊成爆彈型彈量計算問題可用式(1)所示的數(shù)學(xué)規(guī)劃模型表示：

式中：FN為總耗彈量；NWi為第i種彈型的成爆彈量，為該問題的決策變量，i=1,2,…,m；DXCSi為第i種彈型的戰(zhàn)技參數(shù)，i=1,2,…,m；MBXX為計算毀傷效果需要的目標參數(shù)；HL為混合火力子目標和瞄準點分配方案；f(*)為混合火力打擊獲得的毀傷效果。

1.2 成爆彈型彈量計算問題數(shù)學(xué)模型特點

1.3 成爆彈型彈量計算問題的求解思路

2 基于分支定界算法的成爆彈型彈量計算模型

2.1 分支定界法簡介

2.2 基于分支定界算法的成爆彈型彈量計算步驟

基于分支定界算法的成爆彈型彈量計算步驟如下：

步驟2：進行增加彈數(shù)分支，分別將每種彈型的彈數(shù)增加1枚，得到m個成爆彈數(shù)相同的彈型彈量組合方案，每個方案稱為一個分支。計算這m個方案對目標打擊的毀傷效果，對滿足毀傷要求的方案停止增加彈數(shù)分支，轉(zhuǎn)入步驟3。如果所有分支均不滿足毀傷要求，則選擇毀傷效果指標值最好的分支，減去其余分支，重復(fù)步驟2，繼續(xù)進行增加彈數(shù)分支。

步驟3：進行減少彈數(shù)分支，分別將每種彈型的彈數(shù)減去1枚，得到m個成爆彈數(shù)相同的彈型彈量組合方案，每個方案稱為一個分支。計算這m個方案對目標打擊的毀傷效果，減去不滿足毀傷要求的分支，若所有分支均被減去，則分支前的彈型彈量組合為即為滿足打擊要求的耗彈量最小的方案；對沒有減去的分支，重復(fù)上述過程，直到所有分支都被減去為止。

需要指出的是，分支定界法用于解決線性整數(shù)規(guī)劃問題時能夠得到完備的整數(shù)解集，而成爆彈型彈量計算問題屬于非線性NP完全問題，運用分支定界的思想求解得到的解屬于準優(yōu)解，不能保證全局最優(yōu)。

3 基于模擬退火算法的彈型彈量計算模型

3.1 模型的基本概念

在模擬退火算法中，自然界的金屬物體涉及狀態(tài)、能量最低的狀態(tài)和能量等概念；組合優(yōu)化算法中涉及解、最優(yōu)解、目標函數(shù)等概念；在求解成爆彈型彈量時，涉及組合方案、滿足要求的方案、總耗彈量等概念。其相互關(guān)系如表1所示。

表1 成爆彈型彈量計算模型相關(guān)概念

3.2 初始解集的構(gòu)造和領(lǐng)域結(jié)構(gòu)

根據(jù)模擬退火算法的基本原理，結(jié)合成爆彈型彈量計算模型的特點，給出兩種構(gòu)造初始解集的方法。

方法1：為了得到滿足打擊要求的混合火力打擊彈型彈量方案集，在利用模擬退火算法求解時，采用多起點策略，若有彈型m種，則初始解的規(guī)模設(shè)為m。不失一般性，可以從分別設(shè)每種彈型為1枚彈作為初始解集，如表2所示。

表2 模擬退火算法的初始解集

方法2：為提高計算效率，可以先由基于分支定界算法的計算模型得到L個滿足打擊要求的可行解，當L=m時，直接將其作為初始解集；當L>m時，隨機選取其中m個作為初始解集；當L

3.3 溫度參數(shù)的控制

模擬退火算法中包含內(nèi)外兩重循環(huán)，其中外層循環(huán)靠溫度的下降進行控制，內(nèi)層循環(huán)靠每一溫度迭代長度控制。溫度參數(shù)是模擬退火算法的關(guān)鍵參數(shù)之一，主要包括起始溫度的選取、溫度的下降方法、停止溫度和每一溫度的迭代長度。

1) 起始溫度。起始溫度t0應(yīng)保證平穩(wěn)分布中每一狀態(tài)的概率相等，即滿足下式：

(2)

式中：ΔFNij為第j次迭代和第i次迭代的目標函數(shù)差，ΔFNij=FN(j)-FN(i)。

很容易得到t0的估計值為

t0=KΔ0

(3)

式中：K為充分大的數(shù)，實際計算中，可以選K=10,20,100,…的試驗值。

Δ0按下式計算：

(4)

對于具體的成爆彈型彈量計算問題，可以按照上式對Δ0進行估計。

2) 溫度下降方法。溫度下降采用最常用的相同比率下降法，即溫度tk+1=αtk，其中0<α<1，α越接近1，溫度下降越慢。

3) 終止溫度及算法的終止原則。模擬退火的最終溫度為0，最簡單的原則是給定一個比較小的正數(shù)tmin，當溫度t≤tmin時，算法停止。

4) 每一溫度的迭代長度。根據(jù)成爆彈型彈量計算問題的特點，采用固定長度的方法確定每一溫度的迭代步數(shù)。根據(jù)與鄰域大小相關(guān)的規(guī)則，迭代長度可設(shè)為彈型數(shù)量m。

3.4 解的接受機制

區(qū)分兩種初始解集的生成方法，建立不同接受機制。

3.5 算法計算流程設(shè)計

基于模擬退火算法的成爆彈型彈量計算，如果按照方法1生成初始解集，計算流程如圖1所示；如果按照方法2生成初始解集，計算流程如圖2所示。

圖1 成爆彈型彈量計算流程(方法1)

4 仿真算例及結(jié)果分析

4.1 問題背景

問題背景：用甲型侵徹子母彈、乙型侵徹子母彈和丙型延時子母彈等3種彈型對機場跑道進行混合火力打擊(目標和武器參數(shù)略)。打擊要求為跑道0～60 min內(nèi)起飛飛機數(shù)平均下降率不小于0.6。求能夠完成上述任務(wù)的混合火力成爆彈型彈量。

4.2 分支定界算法及結(jié)果分析

運用分支定界算法對問題進行求解，計算步驟如圖3所示。

圖2 成爆彈型彈量計算流程(方法2)

由于沒有對所有方案進行遍歷，而且打擊效果與彈型彈量的關(guān)系并不是線性關(guān)系，因此基于分支定界算法得到的彈型彈量組合方案只是“準優(yōu)解”不一定是耗彈量最少的方案。例如，在耗彈量為7枚的36種彈型彈量組合方案中，共有5種方案對目標的毀傷效果能夠滿足要求，在耗彈量為6枚的28種彈型彈量組合方案中，共有2種方案對目標的毀傷效果能夠滿足要求。實際通常在對計算時間快速性要求很高的條件下應(yīng)用該方法，或者將其計算結(jié)果作為智能優(yōu)化計算方法的初始解，以加快收斂速度。

圖3 基于分支定界算法的成爆彈型彈量計算

4.3 模擬退火算法及結(jié)果分析

設(shè)定起始計算參數(shù)，t0=100，tmin=0.1，α=0.7。為便于比較兩種成爆彈型彈量計算問題的計算效率，運用枚舉法、基于分支定界算法的計算模型、基于模擬退火算法的計算模型3種方法的計算結(jié)果和計算效率對比如表3所示。

表3 成爆彈型彈量計算結(jié)果對比

如表3所示，對于該計算實例，基于分支定界算法的計算模型求解結(jié)果不是全局最優(yōu)解，而是“準優(yōu)解”，基于模擬退火算法的計算模型能夠得到全局最優(yōu)解，采用普通方法生成初始解的模擬退火算法比枚舉法能夠提高2.4倍的計算效率，如果采用分支定界法得到的解為初始解，能夠提高9.1倍的計算效率，表明該方法綜合了分支定界計算的快速性和模擬退火算法全局尋優(yōu)能力，是解決打擊要求給定的混合火力成爆彈型彈量計算問題的有效方法。

5 結(jié)束語

分析了混合火力打擊彈型彈量計算問題與傳統(tǒng)成爆彈量計算問題的差異，建立了數(shù)學(xué)模型，分析了模型特點，分別基于分支定界算法和模擬退火算法，構(gòu)建了成爆彈型彈量計算模型，兩種方法各有優(yōu)點，將兩種模型組合使用較好地解決了具有高維變量的混合火力成爆彈型彈量計算問題。在工程應(yīng)用實際中，由于決策變量的多維性，在總耗彈量相同或相近的前提下，滿足毀傷要求的彈型彈量通常有多種組合方案。對這些組合方案優(yōu)選時，不能僅僅考慮總彈量一個指標，需要從工程應(yīng)用實際出發(fā)，綜合考慮多種因素。比如，作戰(zhàn)部隊、作戰(zhàn)地域的協(xié)同使用問題，以及各型導(dǎo)彈武器的庫存量、補充周期等因素。對于彈量組合方案的綜合優(yōu)選將是下一步需要研究解決的問題。

[1] 肖旭青，周奕，黃偉,等.成爆彈量預(yù)測模型研究[J].兵工自動化，2010，29(4)：12-14.

[2] 史宏亮，齊少軍，劉忠仕，等.基于數(shù)值仿真的面殺傷戰(zhàn)斗部對面目標成爆彈量計算方法[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2010(3)：53-56.

[3] 張紅文，陳智江，畢義明.基于遺傳算法的機場目標耗彈量優(yōu)化方法[J].火力指揮與控制，2007，32(8)：84-86.

[4] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計算方法[M].北京：清華大學(xué)出版社，2005.

[5] 曾劍新，周焰，張斌.基于模擬退火和共同進化算法的協(xié)同航路規(guī)劃[J].火力指揮與控制，2011，36(12)：34-39.

[6] 《運籌學(xué)》教材編寫組.運籌學(xué)[M].北京：清華大學(xué)出版社，2005.

(責任編輯 周江川)

Model for Calculating the Quantity of the Bomb Based on the Branch-Bound and Simulated Annealing Algorithm

LI Yaxiong1， LIU Xinxue1， XU Meng2

(1.Rocket Force University of Engineering, Xi’an 710025, China; 2.The No. 31102ndTroop of PLA, Nanjing 210016, China)

In the multi mode missile combined attack mode, there are many kinds of combination scheme for the same target attack. How to choose the combination scheme that meets the requirements of the damage, and the quantity of the quantity of ammunition as few as possible is a major concern of the decision maker. To solve the problem of high dimension of decision variables, and based on the branch and bound algorithm and the simulated annealing algorithm, two kinds of calculation models for the amount of kinds of bomb are established, and the combination of the two algorithms is designed. Example analysis shows that the model has high computational efficiency and global optimization ability, and it has important engineering application value.

branch and bound; simulated annealing; bomb quantity

10.11809/scbgxb2017.07.005

2017-03-13；

2017-04-10

李亞雄(1979—)，男，博士，副教授，主要從事軍事運籌學(xué)研究。

format:LI Yaxiong，LIU Xinxue，XU Meng.Model for Calculating the Quantity of the Bomb Based on the Branch-Bound and Simulated Annealing Algorithm[J].Journal of Ordnance Equipment Engineering,2017(7):20-24.

TJ765

A

2096-2304(2017)07-0020-05

本文引用格式：李亞雄，劉新學(xué)，徐萌.基于分支定界和模擬退火算法的成爆彈型彈量計算模型[J].兵器裝備工程學(xué)報，2017(7):20-24.