與單目標打擊方案和發射地域相關的快速大規模火力任務分配

黃紅兵 李賢玉 張連偉 鄒輝

火力任務分配是作戰任務規劃的一項重要內容.因面臨的問題不同,實際作戰任務規劃中的火力任務分配問題有很大的差別(如諸多工作所展示的[1?7]).實際工作中存在這樣一類問題：給定一大批打擊目標,每個目標都有若干單目標打擊方案,每個單目標打擊方案涉及的武器可能分屬不同作戰單位,而每個作戰單位只能在有限的幾個作戰區域進行發射活動；在此前提下,需要在給定的武器、兵力、發射地域等諸多約束條件下,針對若干優化目標,給出單目標打擊方案選擇及發射地域分配.特別是在指揮決策層次上,需要考慮錯綜復雜的約束關系和決策因素,大大加大了這類大規模火力任務分配的難度.

針對這一類問題,本文將諸多決策因素作為約束條件或優化目標引入問題,給出了詳細的問題模型,設計了問題求解的遺傳算法,并通過實驗驗證了大規模火力分配算法的快速性.

1 問題描述

設需要打擊的目標有n個,分別為T1、T2、···、Tn;對每個目標Ti有ui個不同的單目標打擊方案Pi1、Pi2、···、Piui;每個單目標打擊方案包括使用的武器類型和需要的數量,如表1所示.

設共有m個可用發射地域Z1、Z2、···、Zm,分屬o個作戰單位Dw1、Dw2、···、Dwo,發射地域與作戰單位對應關系矩陣如表2所示,其中dij為0或1,表示發射地域Zj不屬于或屬于作戰單位Dwj;對于發射地域Zi有vi個可用陣地ZDi1、ZDi2、···、ZDivi稱vi為該發射地域的容量.

表1 單目標打擊方案

表2 發射地域與作戰單位對應關系矩陣

設共有l種武器M1、M2、···、Ml,數量分別為xd1、xd2、···、xdl;對于作戰單位Dwi,設其各類武器的保有量為xdi1、xdi2、···、xdil.

整個火力任務分配問題就是,按照給定的約束條件和優化目標(具體見第2節),為每個打擊目標選擇單目標打擊方案,并分配到具體的發射地域,如表3所示.其中,biuij為0或1,1表示對于Ti方案Piui被選中,并且分配到發射地域Zj.只要給出這一分配矩陣,就可以通過相關條件,統計得到各作戰單位的任務分配,因而表3中的biuij可以作為火力分配規劃問題的決策變量.

表3 火力任務分配及其決策變量

2 數學模型

針對以上問題,將復雜的相關關系和決策因素作為約束條件或優化目標引入問題,建立數學模型.

2.1 約束條件

根據問題和實際情況,這些約束如下.

1)單目標打擊方案被選唯一性及發射區域分配唯一性約束

這一約束下,對于每個目標Ti,表3中對應的火力任務分配決策變量biuij只有一個取1,即：

2)武器數量總量約束

指的是根據實際武器保有量或指揮員決策要求,對分配規劃中武器類型使用的總量進行約束.

以矩陣的形式表示確定毀傷等級的單目標打擊方案的武器使用,如表4所示.

表4 單目標打擊方案武器使用數量矩陣

那么,這一約束可以表示為：

3)作戰單位武器數量約束

指的是根據實際各作戰單位保有的武器數量或指揮員決策要求,對分配規劃中各作戰單位武器使用的數量進行約束.

以矩陣的形式表示各作戰單位擁有或允許使用的武器數量,如表5所示.

表5 各作戰單位擁有或允許使用的武器數量矩陣

那么,這一約束可以表示為:

4)武器射程約束

設武器Mk的射程為Sck,發射地域Zj與目標Ti之間的距離為Lij.如果火力分配決策矩陣中(表3)的biuij為1,并且假設單目標打擊方案武器使用數量矩陣中(表4),方案Piui對應的數量不為0的武器為Mk,那么,武器射程約束可表示為:

5)發射地域容量約束

實際作戰中,每個發射地域安排發射的武器數量小于等于發射地域的容量v.結合表3、表4,這一約束可以表示為:

6)作戰單位作戰單元數量約束

實際作戰中,每個作戰單位發射的彈量,應小于作戰單位作戰單元數量乘以發射波次.設波次數為c,每個作戰單位Dwi的作戰單元數為Gi,結合表2、表3和表4,這一約束可以表示為:

2.2 優化目標

根據實際情況和指揮員的意圖,這類問題的大規模火力任務分配可能有多個目標.

1)最小彈量

在滿足相關約束的條件下,使用的彈量最少.將決策變量集{biuij}記為B,則目標函數可以表示為

2)最少(或最多)建制單位

在滿足相關約束的條件下,使用的建制單位最少(或最多).將表3中火力分配(決策變量)矩陣的行向量記為Bi,將表2中發射地域與作戰單位對應關系矩陣記為Rz,則最少(或最多)建制單位目標函數可以表示為

或

3)彈道平面交叉最少

假設目標Ti與發射地域Zj的平面彈道為Sij,彈道之間的交叉關系用如表6所示的矩陣表示,其中表示Sij和Sxy是否交叉(值的計算可以按照諸如文獻[8]的給出方法進行).

表6 彈道之間的交叉關系矩陣

則彈道平面交叉最少的優化目標函數可以表示為

4)值班發射地域優先使用

假設有值班發射地域Zi1、Zi2、···、Zir,則值班發射地域優先使用的優化目標函數可以表達為

5)值班武器優先使用

假設作戰單位Dwi的值班武器Mj的數量為Zdij.將表4中火力分配(決策變量)矩陣記為B,將表2中發射地域與作戰單位對應關系矩陣記為Rz,將表4中單目標打擊方案武器使用數量矩陣記為X,列向量記為Xj,定義函數

則值班武器優先使用的優化目標函數可以表達為

3 分配算法

從算法設計理論上看,任務分配最優化是NP難問題,實際工作中一般是通過近似算法,給出次優解.本節根據上述火力任務分配多目標優化模型和相關研究[9?10],給出火力任務快速分配的遺傳算法.

3.1 算法描述

火力任務快速分配遺傳算法的總體過程如圖1所示.

圖1 火力任務快速分配遺傳算法的總體過程

具體問題處理如下：

1)個體編碼

火力任務快速分配遺傳算法中的每個個體,都設計成一個任務分配方案,即表3所示的矩陣,在這個矩陣中包括了單目標打擊方案的選取和目標打擊發射地域的分配.因此,對個體適應度的計算也就是對一個任務分配方案的評價(適應度的計算,具體見后文).

2)初始化種群

考慮到個體編碼中的每個基因也是一個決策變量,為保證種群的多樣性,初始化種群時,種群規模選取為.

并且,種群個體產生時遵守“單目標被選打擊方案唯一性及發射地域分配唯一性約束”,以保證每個個體的有效性.

3)交叉變異規則

在種群交叉過程中,父親個體的選取根據個體的適應度進行,適應度大的個體被選取的概率大,同時為避免種群收斂過快,保證每個個體都有可能被選取,每個個體選為父親的概率為

其中,0

在種群交叉過程中母親個體的選取,則隨機進行,每個個體的選取概率為

種群個體變異過程設計成兩種:a)發射地域分配方案變異;b)單目標打擊方案選擇變異.發射地域分配方案變異,只是改變分配方案(個體)中被選擇打擊目標的發射地域;單目標打擊方案選擇變異,則對被選變異目標的單目標打擊方案選取和發射地域分配,都作出改變.

和初始化種群一樣,為保證每個個體的有效性,在種群交叉變異過程中,遵守“單目標被選打擊方案唯一性及發射地域分配唯一性約束”.也就是說,在交叉過程中,父親個體和母親個體交換的是關于某個打擊目標的整個方案,包括其單目標打擊方案選取和發射地域分配;變異也是針對某個目標的單目標選取和發射區域分配的整個方案.

4)適應度計算

算法設計中,將個體適應度分為兩個大的部分:a)對約束條件的適應度;b)對優化目標的適應度.

由于火力任務分配首先要滿足約束條件,所以,對于有不滿足約束條件的分配方案(即個體),計算時賦予它極小的適應度.

優化目標適應度的計算按照2.1給出的目標函數進行.對多個優化目標的滿足可以采取兩種策略:a)為優化目標排序,按順序滿足,即在上一目標優化的前提下,優化下一目標;b)為優化目標賦予權值,化作單目標進行優化.

5)代際更新與算法終止規則

種群交叉和個體變異后產生新一代的種群,為保證算法能夠終止,給更新代數設定一個最大值.

同時,為保證算法效率,當種群適應度達到一定的要求時,終止算法.這一要求為

其中,δ為一個極小值.

3.2 算法效率

以Matlab實現算法,在表7所示的運行環境下,進行算法效率的實驗,結果如圖2.

表7 實驗運行環境

實驗主要參數:發射地域數目為20,每個目標的單目標打擊方案平均個數分別為n=3、4、5,目標個數分別為20、30、40、50、60.

實驗所得數據:如圖2,其中縱軸數據單位為“秒(s)”.

圖2 火力任務快速分配算法效率

4 結論

本文針對這樣的現實問題進行單目標打擊方案選擇及發射地域分配:給定大批打擊目標,每個目標都有若干單目標打擊方案,每個單目標打擊方案涉及的武器分屬不同作戰單位,而每個作戰單位只能在有限的幾個作戰區域進行發射活動.在詳細描述問題的基礎上,將諸多決策因素作為約束條件或優化目標引入問題,給出了問題的數學模型,并基于問題的特征設計了問題求解的遺傳算法,實驗顯示針對此類多約束、多目標大規模火力分配問題,能夠很快得出分配方案,針對實際碰到的問題,能在1min內給出結果,大大提高作戰任務規劃效率.