與單目標(biāo)打擊方案和發(fā)射地域相關(guān)的快速大規(guī)?；鹆θ蝿?wù)分配

黃紅兵 李賢玉 張連偉 鄒輝

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

針對(duì)這一類問題,本文將諸多決策因素作為約束條件或優(yōu)化目標(biāo)引入問題,給出了詳細(xì)的問題模型,設(shè)計(jì)了問題求解的遺傳算法,并通過實(shí)驗(yàn)驗(yàn)證了大規(guī)?；鹆Ψ峙渌惴ǖ目焖傩?

1 問題描述

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

設(shè)共有m個(gè)可用發(fā)射地域Z1、Z2、···、Zm,分屬o個(gè)作戰(zhàn)單位Dw1、Dw2、···、Dwo,發(fā)射地域與作戰(zhàn)單位對(duì)應(yīng)關(guān)系矩陣如表2所示,其中dij為0或1,表示發(fā)射地域Zj不屬于或?qū)儆谧鲬?zhàn)單位Dwj;對(duì)于發(fā)射地域Zi有vi個(gè)可用陣地ZDi1、ZDi2、···、ZDivi稱vi為該發(fā)射地域的容量.

表1 單目標(biāo)打擊方案

表2 發(fā)射地域與作戰(zhàn)單位對(duì)應(yīng)關(guān)系矩陣

設(shè)共有l(wèi)種武器M1、M2、···、Ml,數(shù)量分別為xd1、xd2、···、xdl;對(duì)于作戰(zhàn)單位Dwi,設(shè)其各類武器的保有量為xdi1、xdi2、···、xdil.

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

表3 火力任務(wù)分配及其決策變量

2 數(shù)學(xué)模型

針對(duì)以上問題,將復(fù)雜的相關(guān)關(guān)系和決策因素作為約束條件或優(yōu)化目標(biāo)引入問題,建立數(shù)學(xué)模型.

2.1 約束條件

根據(jù)問題和實(shí)際情況,這些約束如下.

1)單目標(biāo)打擊方案被選唯一性及發(fā)射區(qū)域分配唯一性約束

這一約束下,對(duì)于每個(gè)目標(biāo)Ti,表3中對(duì)應(yīng)的火力任務(wù)分配決策變量biuij只有一個(gè)取1,即：

2)武器數(shù)量總量約束

指的是根據(jù)實(shí)際武器保有量或指揮員決策要求,對(duì)分配規(guī)劃中武器類型使用的總量進(jìn)行約束.

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

表4 單目標(biāo)打擊方案武器使用數(shù)量矩陣

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

3)作戰(zhàn)單位武器數(shù)量約束

指的是根據(jù)實(shí)際各作戰(zhàn)單位保有的武器數(shù)量或指揮員決策要求,對(duì)分配規(guī)劃中各作戰(zhàn)單位武器使用的數(shù)量進(jìn)行約束.

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

表5 各作戰(zhàn)單位擁有或允許使用的武器數(shù)量矩陣

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

4)武器射程約束

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

5)發(fā)射地域容量約束

實(shí)際作戰(zhàn)中,每個(gè)發(fā)射地域安排發(fā)射的武器數(shù)量小于等于發(fā)射地域的容量v.結(jié)合表3、表4,這一約束可以表示為:

6)作戰(zhàn)單位作戰(zhàn)單元數(shù)量約束

實(shí)際作戰(zhàn)中,每個(gè)作戰(zhàn)單位發(fā)射的彈量,應(yīng)小于作戰(zhàn)單位作戰(zhàn)單元數(shù)量乘以發(fā)射波次.設(shè)波次數(shù)為c,每個(gè)作戰(zhàn)單位Dwi的作戰(zhàn)單元數(shù)為Gi,結(jié)合表2、表3和表4,這一約束可以表示為:

2.2 優(yōu)化目標(biāo)

根據(jù)實(shí)際情況和指揮員的意圖,這類問題的大規(guī)模火力任務(wù)分配可能有多個(gè)目標(biāo).

1)最小彈量

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

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

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

或

3)彈道平面交叉最少

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

表6 彈道之間的交叉關(guān)系矩陣

則彈道平面交叉最少的優(yōu)化目標(biāo)函數(shù)可以表示為

4)值班發(fā)射地域優(yōu)先使用

假設(shè)有值班發(fā)射地域Zi1、Zi2、···、Zir,則值班發(fā)射地域優(yōu)先使用的優(yōu)化目標(biāo)函數(shù)可以表達(dá)為

5)值班武器優(yōu)先使用

假設(shè)作戰(zhàn)單位Dwi的值班武器Mj的數(shù)量為Zdij.將表4中火力分配(決策變量)矩陣記為B,將表2中發(fā)射地域與作戰(zhàn)單位對(duì)應(yīng)關(guān)系矩陣記為Rz,將表4中單目標(biāo)打擊方案武器使用數(shù)量矩陣記為X,列向量記為Xj,定義函數(shù)

則值班武器優(yōu)先使用的優(yōu)化目標(biāo)函數(shù)可以表達(dá)為

3 分配算法

從算法設(shè)計(jì)理論上看,任務(wù)分配最優(yōu)化是NP難問題,實(shí)際工作中一般是通過近似算法,給出次優(yōu)解.本節(jié)根據(jù)上述火力任務(wù)分配多目標(biāo)優(yōu)化模型和相關(guān)研究[9?10],給出火力任務(wù)快速分配的遺傳算法.

3.1 算法描述

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

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

具體問題處理如下：

1)個(gè)體編碼

火力任務(wù)快速分配遺傳算法中的每個(gè)個(gè)體,都設(shè)計(jì)成一個(gè)任務(wù)分配方案,即表3所示的矩陣,在這個(gè)矩陣中包括了單目標(biāo)打擊方案的選取和目標(biāo)打擊發(fā)射地域的分配.因此,對(duì)個(gè)體適應(yīng)度的計(jì)算也就是對(duì)一個(gè)任務(wù)分配方案的評(píng)價(jià)(適應(yīng)度的計(jì)算,具體見后文).

2)初始化種群

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

并且,種群個(gè)體產(chǎn)生時(shí)遵守“單目標(biāo)被選打擊方案唯一性及發(fā)射地域分配唯一性約束”,以保證每個(gè)個(gè)體的有效性.

3)交叉變異規(guī)則

在種群交叉過程中,父親個(gè)體的選取根據(jù)個(gè)體的適應(yīng)度進(jìn)行,適應(yīng)度大的個(gè)體被選取的概率大,同時(shí)為避免種群收斂過快,保證每個(gè)個(gè)體都有可能被選取,每個(gè)個(gè)體選為父親的概率為

其中,0

在種群交叉過程中母親個(gè)體的選取,則隨機(jī)進(jìn)行,每個(gè)個(gè)體的選取概率為

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

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

4)適應(yīng)度計(jì)算

算法設(shè)計(jì)中,將個(gè)體適應(yīng)度分為兩個(gè)大的部分:a)對(duì)約束條件的適應(yīng)度;b)對(duì)優(yōu)化目標(biāo)的適應(yīng)度.

由于火力任務(wù)分配首先要滿足約束條件,所以,對(duì)于有不滿足約束條件的分配方案(即個(gè)體),計(jì)算時(shí)賦予它極小的適應(yīng)度.

優(yōu)化目標(biāo)適應(yīng)度的計(jì)算按照2.1給出的目標(biāo)函數(shù)進(jìn)行.對(duì)多個(gè)優(yōu)化目標(biāo)的滿足可以采取兩種策略:a)為優(yōu)化目標(biāo)排序,按順序滿足,即在上一目標(biāo)優(yōu)化的前提下,優(yōu)化下一目標(biāo);b)為優(yōu)化目標(biāo)賦予權(quán)值,化作單目標(biāo)進(jìn)行優(yōu)化.

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

種群交叉和個(gè)體變異后產(chǎn)生新一代的種群,為保證算法能夠終止,給更新代數(shù)設(shè)定一個(gè)最大值.

同時(shí),為保證算法效率,當(dāng)種群適應(yīng)度達(dá)到一定的要求時(shí),終止算法.這一要求為

其中,δ為一個(gè)極小值.

3.2 算法效率

以Matlab實(shí)現(xiàn)算法,在表7所示的運(yùn)行環(huán)境下,進(jìn)行算法效率的實(shí)驗(yàn),結(jié)果如圖2.

表7 實(shí)驗(yàn)運(yùn)行環(huán)境

實(shí)驗(yàn)主要參數(shù):發(fā)射地域數(shù)目為20,每個(gè)目標(biāo)的單目標(biāo)打擊方案平均個(gè)數(shù)分別為n=3、4、5,目標(biāo)個(gè)數(shù)分別為20、30、40、50、60.

實(shí)驗(yàn)所得數(shù)據(jù):如圖2,其中縱軸數(shù)據(jù)單位為“秒(s)”.

圖2 火力任務(wù)快速分配算法效率

4 結(jié)論

本文針對(duì)這樣的現(xiàn)實(shí)問題進(jìn)行單目標(biāo)打擊方案選擇及發(fā)射地域分配:給定大批打擊目標(biāo),每個(gè)目標(biāo)都有若干單目標(biāo)打擊方案,每個(gè)單目標(biāo)打擊方案涉及的武器分屬不同作戰(zhàn)單位,而每個(gè)作戰(zhàn)單位只能在有限的幾個(gè)作戰(zhàn)區(qū)域進(jìn)行發(fā)射活動(dòng).在詳細(xì)描述問題的基礎(chǔ)上,將諸多決策因素作為約束條件或優(yōu)化目標(biāo)引入問題,給出了問題的數(shù)學(xué)模型,并基于問題的特征設(shè)計(jì)了問題求解的遺傳算法,實(shí)驗(yàn)顯示針對(duì)此類多約束、多目標(biāo)大規(guī)模火力分配問題,能夠很快得出分配方案,針對(duì)實(shí)際碰到的問題,能在1min內(nèi)給出結(jié)果,大大提高作戰(zhàn)任務(wù)規(guī)劃效率.