劉雙雙， 許瑞明， 潘俊杰(. 軍事科學院 軍事運籌分析研究所， 北京 0009； 2. 6569部隊)

基于小生境蝙蝠算法的聯(lián)合遠程打擊武器目標分配問題建模與求解

劉雙雙1,2， 許瑞明1， 潘俊杰1
(1. 軍事科學院 軍事運籌分析研究所， 北京 100091； 2. 61569部隊)

針對聯(lián)合遠程打擊作戰(zhàn)籌劃中武器目標分配問題，使用數(shù)學建模與仿真分析相結(jié)合的方法，研究了聯(lián)合遠程精確打擊武器目標分配基本原則，構(gòu)建了武器目標分配問題的多目標優(yōu)化數(shù)學模型；對目標函數(shù)和約束條件進行處理，將該模型轉(zhuǎn)化為單目標優(yōu)化問題；提出了一種結(jié)合小生境淘汰思想的改進蝙蝠算法，用來求解武器目標分配的近似最優(yōu)解。實驗分析表明：該算法能夠有效改善蝙蝠算法的收斂特性，適用于聯(lián)合遠程打擊作戰(zhàn)武器目標分配問題的求解。

武器目標分配；聯(lián)合遠程打擊；蝙蝠算法；小生境

聯(lián)合遠程打擊作戰(zhàn)，是現(xiàn)階段我軍擔負的重要使命任務(wù)，只有足夠重視和強化 “以遠制遠”的作戰(zhàn)能力，才能有效懾止和擊潰潛在敵人。在聯(lián)合遠程打擊作戰(zhàn)籌劃中，各軍兵種需通過精確規(guī)劃武器目標分配，確保在有效完成作戰(zhàn)任務(wù)的前提下，提高武器系統(tǒng)的整體作戰(zhàn)效益。武器目標分配(Weapon-target Assignment，WTA)問題的核心，是根據(jù)作戰(zhàn)目的、作戰(zhàn)態(tài)勢、目標特性和武器性能等因素，把具有不同殺傷力和使用代價的武器，用于打擊不同的目標，形成整體優(yōu)化的分配方案。武器目標分配問題屬于NP(Non-deterministic Polynomial，多項式復(fù)雜程度的非確定性問題)完全問題[1]，該問題的研究主要集中在建模和模型求解算法的設(shè)計上。當前，建模研究多是以對目標的毀傷概率最大為目標函數(shù)；模型求解主要使用人工免疫算法[2]、粒子群算法[3]、遺傳算法[4]98、蟻群算法[5]、模擬退火算法[6]、禁忌搜索算法[7]、NSGA-II[8]等。

蝙蝠算法(Bat Algorithm，BA)由劍橋大學Yang[9]于2010年提出，是一種模擬蝙蝠回聲定位捕食原理的啟發(fā)式群智能搜索算法。蝙蝠算法能以較高概率收斂問題的全局最優(yōu)解，具有收斂速度快、魯棒性好的優(yōu)點[10]。本文將小生境概念引入蝙蝠算法中，研究了小生境蝙蝠算法在武器目標分配中的應(yīng)用，并通過實例驗證了該算法的有效性。

1 聯(lián)合遠程打擊武器目標分配建模

1.1 問題描述

文獻[11-13]在多種武器攻擊多目標的火力分配中，把對目標毀傷概率最大作為優(yōu)化的目標函數(shù)。追求目標毀傷概率最大，可能會導致對某些目標“過度”毀傷，而對另外一些目標打擊出現(xiàn)“不足”的情況，從而造成不合理的資源配置?，F(xiàn)代戰(zhàn)爭對于精確火力的運用，更強調(diào)使用適當?shù)奈淦髻Y源達成理想的作戰(zhàn)效果，追求整體作戰(zhàn)效益最大?？梢姡撃Ｐ鸵巡荒芎芎梅从超F(xiàn)代戰(zhàn)爭的制勝機理，與實際作戰(zhàn)籌劃也不適應(yīng)。文獻[4]98通過設(shè)置毀傷閾值，確保對目標的毀傷程度達到預(yù)期效果，解決可能出現(xiàn)打擊“不足”的問題，但沒能解決可能“過度”的問題。

聯(lián)合遠程打擊作戰(zhàn)中，并非對目標的毀傷越大越好?！度諆?nèi)瓦四公約關(guān)于保護非國際性武裝沖突受難者的附加協(xié)議書》要求控制附帶民事?lián)p傷，附帶損傷可能會使政府陷入政治和輿論上的被動。遠程打擊作戰(zhàn)行動的附帶損傷，主要受目標特性、武器精度和火力運用方式等因素影響。在作戰(zhàn)籌劃階段，目標特性和武器精度均已確定，但仍可通過合理籌劃火力運用以減小附帶損傷。文獻[14]中的模型通過設(shè)置效費比最大準則，雖能使附帶損傷受到限制，但仍不能有效控制過度損傷。因此，本文提出附帶損傷最小原則，確保在實現(xiàn)打擊意圖的前提下通過控制火力運用來減少附帶損傷。

1.2 武器目標分配原則

武器目標分配問題，要遵循系統(tǒng)的、整體的思想才可能求解出全局最優(yōu)解。因此，要建立一個適應(yīng)聯(lián)合遠程打擊作戰(zhàn)的數(shù)學模型，首先要對武器目標分配的基本原則進行分析。一般地，只有對目標的毀傷達到預(yù)期效果，才能實現(xiàn)期望的軍事效益，如若沒有達到預(yù)期毀傷效果，作戰(zhàn)效能將大打折扣。然而，如果造成附帶損傷也會影響作戰(zhàn)效益。在以上分析的基礎(chǔ)上，建立武器目標分配三原則：

原則1：必要毀傷原則，要求對目標的打擊能夠滿足期望的毀傷概率，確保能夠?qū)崿F(xiàn)指揮員的作戰(zhàn)意圖。

原則2：附帶損傷最小原則，盡量避免出現(xiàn)過度打擊，以減小附帶損傷帶來的政治和輿論影響。

原則3：效費比最大原則，對武器資源進行優(yōu)化配置，追求武器效能和作戰(zhàn)效益的最大化。

1.3 武器目標分配數(shù)學建模

(1)

圖1 作戰(zhàn)效能函數(shù)μj曲線示意圖

根據(jù)“必要毀傷原則”，確保對目標的毀傷達到期望毀傷概率，確定約束條件為

(2)

根據(jù)“附帶損傷最小原則”，確保盡可能地減小對目標的過度毀傷，構(gòu)建目標函數(shù)為

(3)

聯(lián)合遠程打擊作戰(zhàn)行動消耗武器資源的總代價為

(4)

聯(lián)合遠程打擊毀傷目標帶來的總效益為

(5)

根據(jù)“效費比最大原則”，確定目標函數(shù)為

(6)

多種武器打擊多個目標問題的優(yōu)化，要求在確保目標有效毀傷的前提下，使得作戰(zhàn)效益最大。該模型求解的輸出，是一個或一組能夠?qū)崿F(xiàn)最大效益的分配方案，明確將每一個目標與具體的武器單元建立對應(yīng)關(guān)系。

在既定的戰(zhàn)場環(huán)境中，相同型號的武器在不同平臺上的使用成本和突防概率不同，即便是武器和平臺都相同，但配置在不同位置，其突防概率也可能不同。比如，配置在不同海域的同一型號驅(qū)逐艦，受戰(zhàn)場環(huán)境影響，在打擊相同目標時的突防概率不同。因此，本文在確定武器種類和數(shù)量的時候，與以往僅按型號進行分類不同，即使將型號相同的武器配置在不同的平臺或位置也按不同類型武器處理。

2 武器目標分配的小生境蝙蝠算法

2.1 蝙蝠算法

蝙蝠算法中，優(yōu)化問題的每個解都對應(yīng)于搜索空間中蝙蝠的位置向量，每個蝙蝠的位置都對應(yīng)一個由優(yōu)化問題決定的適應(yīng)度值。每個蝙蝠通過調(diào)整頻率、響度、脈沖發(fā)射率，追隨當前最優(yōu)蝙蝠在解空間中搜索最優(yōu)位置[15]。蝙蝠個體是蝙蝠算法的基本單元，蝙蝠群體的運動對應(yīng)于解空間中的一組解從無序到有序的演化過程。

(7)

(8)

(9)

式中：β∈[0,1]為服從標準正態(tài)分布的隨機變量；x*為d維空間中當前全局最優(yōu)位置向量；fl為超聲波頻率。

局部搜索過程中，從當前最優(yōu)蝙蝠個體中任選一個位置向量xold，那么新的位置向量xnew就在xold附近隨機產(chǎn)生，即

xnew=xold+εAt

(10)

式中：ε為一個d維隨機向量，向量中所有元素均為[-1,1]上的隨機數(shù)；At為t時刻蝙蝠群的平均響度。用xnew代替當前位置向量，返回全局搜索繼續(xù)搜索獵物，避免陷入局部最優(yōu)。

搜索獵物過程中，最初為了在更廣范圍搜索，超聲波響度A大而脈沖頻率r??；發(fā)現(xiàn)獵物后，為了進一步精確定位，減小響度A、增大脈沖頻率r。響度A和脈沖頻率r的更新公式可描述為

(11)

(12)

蝙蝠算法的搜索過程分為全局尋優(yōu)過程和局部尋優(yōu)過程。其中，公式(7)～(9)用來搜索全局最優(yōu)位置向量；公式(10)～(12)用來搜索局部最優(yōu)位置向量。利用蝙蝠算法特有的回波定位特性來避免搜索過程陷入局部最優(yōu)，是其他智能算法不具有的，使得蝙蝠算法具有其他智能算法不可比擬的優(yōu)勢[16]。

2.2 小生境淘汰機制

生物學中，小生境是指特定的生存環(huán)境。生物進化過程中，一般總是與自己相同的物種生活在一起，這就是小生境自然現(xiàn)象。小生境遺傳算法(NicheGeneticAlgorithm)是在經(jīng)典遺傳算法的基礎(chǔ)上引入小生境技術(shù)，基本思想是在經(jīng)典遺傳算法每產(chǎn)生新一代種群時，通過排擠、預(yù)選擇、適應(yīng)度共享或者淘汰相似結(jié)構(gòu)等機制使個體能夠在解空間中分散開來，更好地維持種群的多樣性，從而有效改善經(jīng)典遺傳算法易陷入局部最優(yōu)解的問題[17]。

基于淘汰相似結(jié)構(gòu)機制的小生境，是通過引入懲罰函數(shù)調(diào)整個體的適應(yīng)度值來實現(xiàn)的。淘汰結(jié)構(gòu)相似的個體，使得個體之間存在一定的距離，從而就造成一種小生境的進化環(huán)境，維護了種群的多樣性，提高了全局搜索能力[18]。本文借鑒了小生境淘汰思想，并將該淘汰機制應(yīng)用到蝙蝠算法中，以提高蝙蝠算法的全局搜索能力。

2.3 小生境蝙蝠算法設(shè)計

為求解聯(lián)合遠程打擊作戰(zhàn)中武器目標分配問題，設(shè)計了小生境蝙蝠算法。以下對該算法的主要操作步驟進行闡述，并給出算法流程。

2.3.1 編 碼

編碼方式直接影響算法的搜索效率。武器的類型、數(shù)目以及目標數(shù)均為整數(shù)，本文選用整數(shù)編碼表示武器與目標的對應(yīng)關(guān)系。整數(shù)編碼方式，能夠描述武器總數(shù)m與打擊目標總數(shù)n的不同情況(m>n，m

編碼可以表示為x=[y1,y2,…,yh,…,ym]，式中，yh為0～n之間的整數(shù)，稱為元素。yh=j表示分配第h件武器單元打擊第j個目標；yh=0表示第h件武器單元沒有參加聯(lián)合遠程打擊作戰(zhàn)任務(wù)。這樣就可以將武器目標分配表示為一個整數(shù)編碼的解向量，也就是蝙蝠算法中蝙蝠個體的位置向量，并且這種對應(yīng)關(guān)系是唯一的。

2.3.2 構(gòu)造適應(yīng)度函數(shù)

適應(yīng)度函數(shù)，是度量個體適應(yīng)度的函數(shù)，個體適應(yīng)度表示種群中個體在優(yōu)化計算中有可能達到或接近最優(yōu)解的優(yōu)良程度。

1) 目標函數(shù)。公式(3)和公式(6)作為武器目標分配問題優(yōu)化的2個目標函數(shù)，屬于多目標優(yōu)化問題。在實際求解過程中，對附帶損傷最小原則進行處理，將問題簡化為單目標求解問題。實際上，若目標附帶損傷程度越小，則需要消耗的武器資源就越少，相應(yīng)地也能夠提高作戰(zhàn)行動的效費比。因此,可以通過限制附帶損傷，將附帶損傷目標函數(shù)轉(zhuǎn)化為求解效費比函數(shù)的約束條件,即令

(13)

式中，ω為打擊所有目標帶來的附帶損傷之和，求解過程中設(shè)置成常數(shù)，以控制附帶損傷在可以接受的范圍內(nèi)。

(14)

2) 懲罰函數(shù)。根據(jù)以上分析，公式(2)和公式(13)作為優(yōu)化求解的約束條件，計算蝙蝠個體適應(yīng)度值時，可以通過構(gòu)造懲罰函數(shù)來實現(xiàn)。公式(15)就是對不滿足約束條件的解進行懲罰，使其對應(yīng)的適應(yīng)度值為負。

(15)

(15)

2.3.3 小生境蝙蝠算法流程

設(shè)計小生境蝙蝠算法(NicheBatAlgorithm，NBA)的實現(xiàn)流程：

1) 初始化t時刻蝙蝠群的位置(也就是問題的解向量xl(i=1,2,…,n))和速度vl；初始化頻率fl、脈沖頻率rl和響度Al；

2) 計算種群中所有個體的適應(yīng)度值，并按照適應(yīng)度值從大到小對個體排序，記錄前N個蝙蝠個體；

3) 根據(jù)公式(7)～(9)，更新t+1時刻蝙蝠的速度和位置；

4) 產(chǎn)生隨機變量rand1，若rand1大于rl，選擇最佳位置并在該位置附近隨機產(chǎn)生一個位置；

5) 通過隨機飛行產(chǎn)生一個新的位置；

6) 產(chǎn)生隨機變量rand2，若rand2f(x*)，接受新的位置，按照公式(11)和公式(12)更新rl和Al；

7) 小生境淘汰操作，計算每2個蝙蝠之間的歐氏距離，當距離小于預(yù)設(shè)值時，對其中適應(yīng)度較小的個體予以懲罰[19]。對popsize+N個蝙蝠按適應(yīng)度值進行降序排列，保留前popsize個蝙蝠作為下次迭代的初始群；

8)判斷是否達到設(shè)置的迭代次數(shù)，“是”則結(jié)束計算，“否”則返回2)。

具體算法操作流程如圖2所示。

圖2 小生境蝙蝠算法流程

3 實例分析

3.1 實驗案例

為驗證小生境蝙蝠算法求解武器目標分配問題的有效性，設(shè)計了一個聯(lián)合遠程打擊案例。此案中，使用5種類型的武器打擊7個獨立目標，武器和目標的相關(guān)參數(shù)如表1和表2所示。每種類型的武器對目標的毀傷概率和突防概率數(shù)據(jù)如表3和表4所示。

表1 目標參數(shù)

表2 武器參數(shù)

表3 武器—目標毀傷概率

表4 武器—目標突防概率

3.2 仿真分析

3.2.1 參數(shù)設(shè)置

種群popsize=50，保留優(yōu)秀個體數(shù)N=3，迭代次數(shù)N_iter=100，初始速度、頻率用rand()函數(shù)隨機產(chǎn)生，響度衰減系數(shù)α=0.9，脈沖頻率增加系數(shù)γ=0.05，頻率下限fmin=0，頻率上限fmax=2，附帶損傷控制量ω=1，作戰(zhàn)效能函數(shù)的底數(shù)a=10。

3.2.2 仿真實驗

使用Matlab軟件對以上案例進行仿真分析，得出適應(yīng)度值演化過程如圖3所示，在第37次迭代過程搜索出最優(yōu)解，最大效費比為1.694。

圖3 小生境蝙蝠算法迭代100次適應(yīng)度值演化情況

進行多次獨立重復(fù)實驗，求解的最大適應(yīng)度值穩(wěn)定在1.694，認為該適應(yīng)度值為近似最優(yōu)解。實驗中獲得2組滿足近似最優(yōu)解的可行分配方案，其武器目標對應(yīng)關(guān)系如表5所示。

表5 分配方案

為驗證本文改進算法的性能，使用傳統(tǒng)蝙蝠算法和本文算法分別對上述案例進行100次求解實驗，得到近似最優(yōu)解的次數(shù)分別是21次和86次。這表明引入小生境思想的蝙蝠算法，通過控制蝙蝠個體的分布距離，有效改善了算法的全局搜索能力。

4 結(jié) 論

針對聯(lián)合遠程打擊作戰(zhàn)籌劃中武器目標分配問題，提出了武器分配的基本原則并構(gòu)建了數(shù)學模型，在模型求解中提出了一種改進蝙蝠算法，通過實例驗證得到以下結(jié)論：

1) 本文構(gòu)建的聯(lián)合遠程打擊WTA數(shù)學模型，更好地反映了現(xiàn)代戰(zhàn)爭的制勝機理。

2) 引入小生境淘汰思想的改進蝙蝠算法，通過控制蝙蝠個體的分布距離，有效改善了蝙蝠算法的全局搜索能力。

References)

[1]LLOYD S P，WITSENHAUSEN H S.Weapon allocation is NP-complete [C]//Proc.1986 Summer Compute Simulation Conference.Reno：[s.n.],1986：1054-1058.

[2] 阮晏智，李慶民，劉天華.編隊防空火力分配建模及其優(yōu)化方法研究[J].兵工學報，2010,31(11)：1525-1529.

[3] 劉曉，劉忠，侯文姝，等.火力分配多目標規(guī)劃模型的改進MOPSO算法[J].系統(tǒng)工程與電子技術(shù)，2013,35(2)：326-331.

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

[5] 崔莉莉.基于蟻群算法的武器—目標分配問題研究[D].上海交通大學，2011：56-59.

[6] 吳平，梁青.武器—目標分配問題的模擬退火算法[J].計算機工程與應(yīng)用，2006(4)：87-90.

[7] 徐加強，畢義明，汪民樂，等.基于時空約束的常規(guī)導彈火力分配建模與實現(xiàn)[J].系統(tǒng)工程與電子技術(shù)，2011，33(9)：2025-2029.

[8] 吳家明，喬氏東，黃金才.基于NSGA-II的防空部署優(yōu)化方法[J].火力與指揮控制，2011，36(3)：57-61.

[9] YANG X S.A new metaheuristic bat-inspired a1gorithm[M]//Nature inspired cooperative strategies for optimization (NICSO 2010).Ber1in Heidelberg：Springer，2010：65-74.

[10] YANG X S，GANDOMI A H.Bat algorithm： a novel approach for global engineering optimization[J].Engineering Computations，2012，29(5)：464-483.

[11] 張最良，李長生，趙文志，等.軍事運籌學[M].北京：軍事科學出版社，1993：408-410.

[12] 劉振林，唐蘇妍，葛偉.創(chuàng)造性思維粒子群優(yōu)化的武器目標分配[J].火力與指揮控制，2012，37(3)：4-9.

[13] 毛藝帆，張多林.改進的人工蜂群算法求解武器目標分配問題[J].軍事運籌與系統(tǒng)工程，2015，29(1)：30-34.

[14] 李平，李長文．武器目標協(xié)同火力分配建模及算法[J].指揮控制與仿真，2015，37(2)：36-40.

[15] YANG X S.Nature-inspired metaheuristic algorithms[M].United Kingdom：Luniver Press，2010：97-104.

[16] 郭業(yè)才，吳華鵬，王惠.基于DNA遺傳蝙蝠算法的分數(shù)間隔多模盲均衡算法[J].兵工學報，2015，36(8)：1052-1057.

[17] 韓維，史瑋韋，司維超．多交叉混沌選擇反向小生境遺傳算法[J].計算機工程，2014，40(6)：154-156.

[18] 汪民樂.遺傳算法的收斂性研究[J].計算技術(shù)與自動化，2015，34(1)：58-62.

[19] 陸文博，劉春生，周青松，等.基于小生境遺傳算法的干擾資源優(yōu)化分配技術(shù)[J].電子信息對抗技術(shù)，2014，29(3)：33-37.

(編輯：李江濤)

Research on the Modeling and Solving of the Joint Long-range Strike Weapon Target Assignment Problem Based on the Niche Bat Algorithm

LIU Shuangshuang1,2， XU Ruiming1， PAN Junjie1

(1. Institute of Military Operational Research and Analysis， Academy of the Military Science， Beijing 100091, China; 2. 61569 Troops, China)

Based on the combination of mathematical modeling and simulation analysis, this paper studies the basic principle of weapon target assignment of joint long-range precision strike weapon target assignment and constructs a multi-objective optimization mathematical model to solve the weapon target assignment problem in the operational planning of joint long-range precision strike. This paper processes the objective functions and constraint conditions and transforms the model into a single objective optimization problem. An improved bat algorithm is proposed to solve the approximate optimal solution of weapon target assignment. The experimental results show that the proposed algorithm can effectively improve the convergence characteristics of the bat algorithm and is suitable for solving the problem concerning weapon target assignment of joint long-range strike.

weapon target assignment; joint long-range strike; bat algorithm; niche

2016-10-24

部委級資助課題(2015JY546)

劉雙雙(1985—)，男，工程師，博士研究生，主要研究方向為聯(lián)合作戰(zhàn)方案生成與評估。