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

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

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

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

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

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

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

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

1 聯合遠程打擊武器目標分配建模

1.1 問題描述

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

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

1.2 武器目標分配原則

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

原則1：必要毀傷原則，要求對目標的打擊能夠滿足期望的毀傷概率，確保能夠實現指揮員的作戰意圖。

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

原則3：效費比最大原則，對武器資源進行優化配置，追求武器效能和作戰效益的最大化。

1.3 武器目標分配數學建模

(1)

圖1 作戰效能函數μj曲線示意圖

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

(2)

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

(3)

聯合遠程打擊作戰行動消耗武器資源的總代價為

(4)

聯合遠程打擊毀傷目標帶來的總效益為

(5)

根據“效費比最大原則”，確定目標函數為

(6)

多種武器打擊多個目標問題的優化，要求在確保目標有效毀傷的前提下，使得作戰效益最大。該模型求解的輸出，是一個或一組能夠實現最大效益的分配方案，明確將每一個目標與具體的武器單元建立對應關系。

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

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

2.1 蝙蝠算法

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

(7)

(8)

(9)

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

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

xnew=xold+εAt

(10)

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

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

(11)

(12)

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

2.2 小生境淘汰機制

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

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

2.3 小生境蝙蝠算法設計

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

2.3.1 編 碼

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

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

2.3.2 構造適應度函數

適應度函數，是度量個體適應度的函數，個體適應度表示種群中個體在優化計算中有可能達到或接近最優解的優良程度。

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

(13)

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

(14)

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

(15)

(15)

2.3.3 小生境蝙蝠算法流程

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

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

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

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

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

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

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

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

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

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

圖2 小生境蝙蝠算法流程

3 實例分析

3.1 實驗案例

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

表1 目標參數

表2 武器參數

表3 武器—目標毀傷概率

表4 武器—目標突防概率

3.2 仿真分析

3.2.1 參數設置

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

3.2.2 仿真實驗

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

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

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

表5 分配方案

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

4 結 論

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

1) 本文構建的聯合遠程打擊WTA數學模型，更好地反映了現代戰爭的制勝機理。

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

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

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

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

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

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

[8] 吳家明，喬氏東，黃金才.基于NSGA-II的防空部署優化方法[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] 劉振林，唐蘇妍，葛偉.創造性思維粒子群優化的武器目標分配[J].火力與指揮控制，2012，37(3)：4-9.

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

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

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

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

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

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

[19] 陸文博，劉春生，周青松，等.基于小生境遺傳算法的干擾資源優化分配技術[J].電子信息對抗技術，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—)，男，工程師，博士研究生，主要研究方向為聯合作戰方案生成與評估。