基于競爭蛙跳算法的聯(lián)合火力打擊任務(wù)規(guī)劃方法

王海峰,高小軍,劉 昊

(1.中國人民解放軍31696部隊,遼寧 錦州 121000;2.鄭州聯(lián)勤保障中心,河南 鄭州 450000)

聯(lián)合火力打擊是未來聯(lián)合作戰(zhàn)的重要環(huán)節(jié),對聯(lián)合火力打擊任務(wù)規(guī)劃的綜合效果評估和優(yōu)化是聯(lián)合作戰(zhàn)籌劃中的工作重點和難點[1]?？紤]到聯(lián)合火力打擊任務(wù)規(guī)劃中涉及的火力打擊兵器種類、彈藥類型和目標(biāo)數(shù)量繁多,問題復(fù)雜度遠(yuǎn)高于過往戰(zhàn)爭形態(tài)中以單一兵種的動態(tài)火力分配問題,手工作業(yè)手段難以應(yīng)對,必須考慮引入智能優(yōu)化算法求解聯(lián)合火力打擊任務(wù)規(guī)劃問題。聯(lián)合火力打擊任務(wù)規(guī)劃中的兵力、火力、目標(biāo)分配問題在軍事運籌領(lǐng)域?qū)儆趧討B(tài)火力分配問題,以被證明屬于NP完全問題[2]。針對此類問題,國內(nèi)外的學(xué)者已經(jīng)進行了充分的研究和論證,隨著計算機運算能力的大幅提升和人工智能研究的逐步深入,運用智能優(yōu)化算法通過多代迭代找到NP問題最優(yōu)解成為解決此類問題的有效解法。

智能優(yōu)化算法是20世紀(jì)70年代隨人工智能而興起的一類仿生算法,代表算法包括以模擬生物群落行為規(guī)律的蜂群算法[3]、蟻群算法[4]、蛙跳算法[5]、魚群算法[6]、螢火蟲算法[7]、布谷鳥算法[8]、粒子群算法[9]、細(xì)菌覓食算法[10]等;以模擬自然界規(guī)律的細(xì)胞膜優(yōu)化算法[11]、模擬退火算法[12]、量子進化算法[13]等;以及模擬生物種群內(nèi)部演化規(guī)律的遺傳算法[14]、貪心算法[15]等。上述智能優(yōu)化算法各自的理論出發(fā)點均不相同,但算法設(shè)計存在共同點:一是設(shè)計可動態(tài)調(diào)整的智能體框架,結(jié)合具體問題的可行解建立一一對應(yīng)的映射關(guān)系,將問題求解轉(zhuǎn)化為向量空間中找最佳位置向量;二是通過引入偽隨機數(shù)使智能體在向量空間中隨機游走或多代變異演化,使可行解無限逼近周邊最優(yōu);三是通過設(shè)定退出條件限制迭代次數(shù),并輸出優(yōu)化后的最優(yōu)解作為時限內(nèi)的可行解。相比于基于數(shù)學(xué)函數(shù)的線性規(guī)劃算法,智能優(yōu)化算法具有非線性不連續(xù)、約束條件調(diào)整方便、最優(yōu)解輸出可控等優(yōu)點,然而算法也存在易陷入局部最優(yōu)陷阱,以及收斂代數(shù)和優(yōu)化效果不可控的風(fēng)險?；诖?本文以蛙跳算法為標(biāo)準(zhǔn),借鑒并引入遺傳算法中的壽終正寢和優(yōu)勝劣汰機制,設(shè)計了競爭蛙跳算法,并將該算法引入聯(lián)合火力打擊任務(wù)規(guī)劃問題求解中,實現(xiàn)了動態(tài)火力分配的自動生成和智能優(yōu)化,取得了良好的工程應(yīng)用效果。

1 問題描述

聯(lián)合火力打擊任務(wù)規(guī)劃問題是在限定的兵力、火力和目標(biāo)條件下,確保以完成火力打擊任務(wù)份額為前提,使我方兵力和火力損耗最小的動態(tài)兵力、火力、目標(biāo)分配問題。設(shè)我方參與聯(lián)合火力打擊的兵力為B={b1,b2…bn},其中bk表示第k個火力打擊部隊的編號、兵力種類、打擊參數(shù)、執(zhí)行任務(wù)次數(shù)、執(zhí)行任務(wù)時長、任務(wù)間隔時長等變量集合;敵方目標(biāo)為D={d1,d2…dm},其中dl表示第l個目標(biāo)的編號、種類、應(yīng)毀傷程度、對應(yīng)彈藥需求量等變量集合;H(dl,bk)、D(dl,bk)、S(dl,bk)、T(dl,bk)分別表示使用第k個火力打擊部隊打擊第l個目標(biāo)時,對目標(biāo)造成的毀傷程度,彈藥消耗量,我方兵力預(yù)計損耗量,火力打擊總體時長等變量。聯(lián)合火力打擊任務(wù)規(guī)劃問題的硬約束條件如下:

1)保證完成上級賦予的火力打擊任務(wù)份額。設(shè)任務(wù)規(guī)劃共包含p個子任務(wù),規(guī)定的火力打擊任務(wù)份額為G;則約束條件的數(shù)學(xué)模型表述如下

(1)

2)保證我方各參戰(zhàn)部隊有足夠彈藥應(yīng)對突發(fā)任務(wù)。設(shè)任務(wù)規(guī)劃中第k個部隊執(zhí)行p次任務(wù),每次彈藥消耗量為l,彈藥總量為Lk;則約束條件的數(shù)學(xué)模型表述如下

(2)

3)保證在規(guī)定時限內(nèi)完成火力打擊任務(wù)。設(shè)任務(wù)規(guī)劃共包含p個子任務(wù),發(fā)起火力打擊時刻為Ts,規(guī)定火力打擊截止時刻為Tz,第k個部隊的火力打擊總時長為Tk;則約束條件的數(shù)學(xué)模型表述如下:

(3)

max{T1,T2,…,Tk}≤Tz-Ts

(4)

在達(dá)成硬約束條件的前提下,設(shè)定軟約束條件如下:

1)盡可能在最短時間內(nèi)對目標(biāo)實施火力打擊(防止目標(biāo)逃離)；

2)盡可能節(jié)約我方彈藥量,以備不時之需；

3)盡可能減少我各參戰(zhàn)部隊的兵力損耗；

4)盡可能平均分配各部隊的火力打擊任務(wù)量；

5)盡可能壓縮總體火力打擊時長；

6)盡可能對同一目標(biāo)實現(xiàn)多兵器、多彈種聯(lián)合火力打擊。

問題的難點:1)各約束條件相互為制約,須通過智能算法建立數(shù)學(xué)模型找到最佳平衡點;2)目標(biāo)清單處于動態(tài)更新中,隨時會出現(xiàn)新的目標(biāo)打擊任務(wù),因此聯(lián)合火力打擊任務(wù)規(guī)劃要保證預(yù)留部隊和彈藥量應(yīng)對臨機任務(wù)。

2 算法構(gòu)建

智能優(yōu)化算法應(yīng)用于聯(lián)合火力打擊任務(wù)規(guī)劃問題求解,主要由數(shù)據(jù)錄入、向量空間建立、綜合評估、競爭蛙跳4個部分構(gòu)成。數(shù)據(jù)錄入部分將當(dāng)前態(tài)勢下獲取的實時目標(biāo)情報信息、我方火力打擊部隊的實時信息錄入,結(jié)合前期已知的各兵器、彈種對各目標(biāo)的毀傷能力信息,為后續(xù)的智能優(yōu)化提供數(shù)據(jù)支撐;向量空間建立部分以打擊部隊，消耗彈藥，打擊目標(biāo)建立多維空間,將動態(tài)兵力、火力、目標(biāo)分配問題轉(zhuǎn)化為多維向量空間中尋找最優(yōu)解向量問題;綜合評估部分以數(shù)據(jù)錄入為基礎(chǔ),將固定輸入條件下的聯(lián)合火力打擊任務(wù)規(guī)劃通過數(shù)學(xué)模型的量化評估指標(biāo)計算綜合評分;競爭蛙跳部分以向量空間和綜合評估為基礎(chǔ),通過競爭蛙跳,經(jīng)過多代迭代,獲取聯(lián)合火力打擊任務(wù)規(guī)劃在向量空間中對應(yīng)的最佳位置,并將解向量轉(zhuǎn)化為唯一對應(yīng)的任務(wù)規(guī)劃結(jié)果輸出。智能優(yōu)化算法的流程如圖1所示。

圖1 智能優(yōu)化算法流程圖

2.1 競爭蛙跳模型

標(biāo)準(zhǔn)蛙跳算法以自然界中蛙群為參考對象,設(shè)蛙群分散在多個獨立的子群落中,各子群中的最差評分個體可通過有限次數(shù)蛙跳向周邊的高分位置轉(zhuǎn)移,若轉(zhuǎn)移失敗則引入新個體替代最差評分個體;定期將子群落中的個體打亂重組,防止子群落中的個體陷入局部最優(yōu)。標(biāo)準(zhǔn)蛙跳算法流程如圖2所示。

圖2 標(biāo)準(zhǔn)蛙跳算法流程圖

通過對標(biāo)準(zhǔn)蛙跳算法分析可知,其算法核心包含兩部分:一是通過最差評分個體向周邊移動的蛙跳操作探索高分位置;二是定期打亂重組防止算法陷入局部最優(yōu)。然而算法也存在如下缺陷:一是對偶然產(chǎn)生的局部最高評分個體無法規(guī)避,該個體會繁殖眾多類似的后代個體替代低分個體,使種群多樣性受到破壞,導(dǎo)致算法陷入局部最優(yōu);二是蛙跳冗余問題,最差評分個體若處于低分區(qū)域,但未達(dá)到刪除的程度時,算法會頻繁對其實施無意義的重復(fù)蛙跳動作,導(dǎo)致系統(tǒng)資源消耗?；诖?本文借鑒遺傳算法中的壽終正寢和優(yōu)勝劣汰機制,引入壽命和淘汰系數(shù)對蛙跳算法進行改造。算法思想是，為了防止局部高分個體的大量繁殖,為所有個體添加壽命系數(shù),設(shè)每次打亂重組后為所有個體壽命+1,若有個體壽命達(dá)到上限,不論其綜合評分結(jié)果如何,均刪除該個體,以模擬自然界的壽終正寢生命歷程;為了防止無意義蛙跳問題,為所有個體添加淘汰系數(shù),設(shè)個體的每次蛙跳動作后且評分未提升,則淘汰系數(shù)+1,若有個體蛙跳次數(shù)達(dá)到上限,不論其綜合評分結(jié)果如何,均刪除該個體,以模擬自然界的優(yōu)勝劣汰自然選擇規(guī)律。競爭蛙跳算法流程如圖3所示。

圖3 競爭蛙跳算法流程圖

個體數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 個體數(shù)據(jù)結(jié)構(gòu)

具體算法步驟如下:

Step1:創(chuàng)建初始種群,每個個體對應(yīng)向量空間中的唯一點位。

Step2:計算種群內(nèi)所有個體的綜合評分,記錄最高評分個體Xq。

Step3:將種群內(nèi)所有個體按評分排序,并按序號平均分配到m個子群中,保證各子群內(nèi)個體總評分相差不大。

Step4:所有個體壽命+1。

Step5:對各子群的最低評分個體Xw實施蛙跳操作,蛙跳后的新位置個體為X′w。

Step6:若X′w的綜合評分高于Xw,則用X′w替代Xw。

Step7:否則重復(fù)5-6,若k次蛙跳后的X′w綜合評分低于Xw,則用該子群最高分個體繁殖新個體代替Xw。

Step8:更新所有個體淘汰系數(shù)。

Step9:將所有子群打亂重組,記錄最高評分個體Xq。

Step10:重復(fù)Step3-8,直至達(dá)成退出條件,輸出最高評分個體。

2.2 評估指標(biāo)模型

本文中針對聯(lián)合火力打擊任務(wù)規(guī)劃的各約束條件,共設(shè)計了3類、11項評估指標(biāo)。具體評估指標(biāo)如圖4所示。

圖4 聯(lián)合火力打擊任務(wù)規(guī)劃評估指標(biāo)

設(shè)共有m支部隊,第i支部隊打擊半徑為oi,可執(zhí)行打擊任務(wù)次數(shù)為ci,任務(wù)執(zhí)行時長di,任務(wù)間隔時長ei,部隊所在地坐標(biāo)為(xmi,ymi);目標(biāo)打擊表中共有n個目標(biāo),第j個目標(biāo)的標(biāo)準(zhǔn)毀傷程度為hj,目標(biāo)所在地坐標(biāo)為(xnj,ynj);毀傷能力表中第i支部隊對第j個目標(biāo)火力打擊,毀傷40%對應(yīng)出動次數(shù)為g40ij,毀傷60%對應(yīng)出動次數(shù)為g60ij;火力打擊任務(wù)規(guī)劃中共有子任務(wù)r個,第k個子任務(wù)的執(zhí)行任務(wù)次數(shù)為lk,打擊開始時刻為pk,打擊結(jié)束時刻為qk;u為部隊每次執(zhí)行任務(wù)后的兵力損耗百分比。首先要對任務(wù)規(guī)劃進行可行性判斷。

1)剔除超過部隊射程的子任務(wù),計算公式為

(5)

2)剔除超出最大出動能力的子任務(wù),計算公式為

(6)

然后計算各評估指標(biāo)。

1)單目標(biāo)打擊時長(Aj)。用以表示對第j個目標(biāo)實施聯(lián)合火力打擊的總用時,計算公式為:

Aj=max{qj}-min{pj}

(7)

2)單部隊打擊次數(shù)(Bi)。用以表示第i個部隊已實施火力打擊的次數(shù),計算公式

(8)

3)整體打擊時長(C)。用以表示該任務(wù)規(guī)劃的聯(lián)合火力打擊總用時,計算公式為

C=max{qk}-min{pk}

(9)

4)單目標(biāo)冗余彈藥比例(Ej)。用以表示對第j個目標(biāo)實施聯(lián)合火力打擊的彈藥用量,超過規(guī)定毀傷彈藥用量的比例。設(shè)投入彈藥比例為Dj,s表示目標(biāo)等級,d表示出動次數(shù);計算公式為

(10)

Ej=max{0,Dj-100}

(11)

5)單目標(biāo)完成任務(wù)比例(Fj)。用以表示任務(wù)規(guī)劃中對第j個目標(biāo)實施聯(lián)合火力打擊的任務(wù)完成度,計算公式

Fj=min{100,Dj}

(12)

6)體系破擊能力(Gr)。用以表示完成第r個子任務(wù)時,對敵體系作戰(zhàn)能力的破壞程度,計算公式為

(13)

7)防空削弱能力(Hr)。用以表示完成第r個子任務(wù)時,對敵防空能力的破壞程度,計算公式為

(14)

8)地面打擊削弱能力(Ir)。用以表示完成第r個子任務(wù)時,對敵地面打擊能力的破壞程度,計算公式為

(15)

9)彈藥剩余比例(Ji)。用以表示第i個部隊執(zhí)行完火力打擊任務(wù)后的彈藥剩余比例,計算公式為

(16)

10)兵力剩余比例(Ki)。用以表示第i個部隊執(zhí)行完火力打擊任務(wù)后,按照敵方的體系破擊能力、防空削弱能力、地面打擊削弱能力情況,預(yù)測剩余的兵力占原有兵力的比例,計算公式為

(17)

11)聯(lián)合打擊次數(shù)(L)。用以表示對各目標(biāo)實施聯(lián)合火力打擊過程中,實現(xiàn)了多種兵器、多種彈藥在同一時刻對同一目標(biāo)實施復(fù)合火力打擊的次數(shù),計算公式為

(18)

(19)

2.3 綜合評分模型

本文使用熵權(quán)法[16]將單目標(biāo)指標(biāo)和單部隊指標(biāo)進行融合處理,生成唯一對應(yīng)的評估指標(biāo),而后使用理想點法[17]將11項評估指標(biāo)綜合計算評分。以單目標(biāo)指標(biāo)的融合計算過程為例,設(shè)共有m個火力打擊目標(biāo),有n個任務(wù)規(guī)劃參與評估,建立初始矩陣X;熵權(quán)法的計算流程如下:

Step1:歸一化處理。生成歸一化矩陣P,計算公式為

(20)

Step2:熵值計算。生成m個目標(biāo)的對應(yīng)熵值ej,計算公式為

(21)

Step3:熵權(quán)重計算。生成第m個目標(biāo)的對應(yīng)熵權(quán)重tj,計算公式為

(22)

Step4:融合評估指標(biāo)計算。生成n個任務(wù)規(guī)劃的融合評估指標(biāo)值zi,計算公式為

(23)

當(dāng)獲取n個任務(wù)規(guī)劃的11項評估指標(biāo)后,使用理想點法的計算流程如下。

Step1:計算正負(fù)理想點A+和A-,計算公式為

(24)

(25)

Step2:計算第i個任務(wù)規(guī)劃與正負(fù)理想點之間的距離di+和di-,計算公式為

(26)

(27)

Step3:計算第i個任務(wù)規(guī)劃的綜合評分Mi,計算公式為

(28)

3 仿真分析

為了驗證競爭蛙跳算法在聯(lián)合火力打擊任務(wù)規(guī)劃中的優(yōu)化效果,本文采用文獻[5]提供的標(biāo)準(zhǔn)蛙跳算法作為對比算法。仿真實驗計算機配置為Intel酷睿雙核處理器T7300 2.0 GHz，3G內(nèi)存，Window 7 32位操作系統(tǒng)，vc6.0編程平臺。

3.1 參數(shù)有效性分析

為了驗證最優(yōu)搭配組合的參數(shù)設(shè)置,設(shè)計實驗如下:選取變異概率、種群規(guī)模、蛙跳步長、蛙跳嘗試次數(shù)、壽命上限、淘汰系數(shù)上限、退出條件代數(shù)為待調(diào)節(jié)參數(shù),每次調(diào)整其中一個參數(shù)的取值范圍,并通過競爭蛙跳算法的多代迭代最優(yōu)評分為參考條件,將參數(shù)調(diào)整為最佳位置,如此反復(fù),直至所有參數(shù)均達(dá)成最優(yōu)值,輸出最優(yōu)評分個體。所有參數(shù)的最優(yōu)值如表2所示。

3.2 效果對比分析

為了檢驗算法的優(yōu)化效果,以標(biāo)準(zhǔn)蛙跳算法和標(biāo)準(zhǔn)遺傳算法作為對比實驗,計算經(jīng)過500代迭代進化的最優(yōu)個體綜合評分結(jié)果。算法最高評分對比變化情況和各代最高評分對比變化情況如圖5和圖6所示。

表2 參數(shù)優(yōu)化統(tǒng)計

圖5 最優(yōu)個體綜合評分對比

圖6 各代最高評分對比

實驗結(jié)果表明,競爭蛙跳算法相比于標(biāo)準(zhǔn)蛙跳算法和標(biāo)準(zhǔn)遺傳算法,收斂速度更快,能夠在較少代數(shù)內(nèi)達(dá)成全局最優(yōu)。圖6中,標(biāo)準(zhǔn)蛙跳算法的各代最優(yōu)個體評分抖動不大,表明高分的超級個體影響了算法的尋優(yōu)能力,限制了種群的多樣化發(fā)展方向;相比而言,競爭蛙跳算法的各代最優(yōu)個體評分抖動明顯,表明種群正在向多樣化發(fā)展,試圖突破當(dāng)前位置局限,尋找全局最優(yōu)解。

3.3 規(guī)劃結(jié)果分析

為了檢查算法在聯(lián)合火力打擊任務(wù)規(guī)劃具體問題中的應(yīng)用效果,將三種算法得到的最優(yōu)個體進行對比分析。三種算法的時間消耗對比情況如圖7所示,收斂代數(shù)對比情況如圖8所示。

圖7 算法時間消耗對比

圖8 算法收斂代數(shù)對比

實驗結(jié)果表明,競爭蛙跳算法由于引入了淘汰系數(shù),蛙跳更具方向性,同時避免了無意義的重復(fù)蛙跳動作,因此收斂代數(shù)更短,時間消耗更少。對標(biāo)準(zhǔn)蛙跳算法和競爭蛙跳算法得到的任務(wù)規(guī)劃11項評估指標(biāo)進行對比分析,兩種算法的評估指標(biāo)對比情況如圖9所示。

圖9 算法評估指標(biāo)分值對比

實驗結(jié)果表明,除了單部隊打擊次數(shù)(No.4)和體系破擊能力(No.8)評估指標(biāo)外,競爭蛙跳算法的各項評估指標(biāo)均優(yōu)于標(biāo)準(zhǔn)蛙跳算法,由此可知,標(biāo)準(zhǔn)蛙跳算法獲取的最優(yōu)個體并不是全局最優(yōu)個體,競爭蛙跳算法相比較而言具備更優(yōu)異的全局尋優(yōu)能力。

競爭蛙跳算法對應(yīng)的聯(lián)合火力打擊任務(wù)規(guī)劃示例如表3所示。

表3 聯(lián)合火力打擊任務(wù)規(guī)劃輸出示例

4 結(jié)束語

本文在前人對智能優(yōu)化算法研究的基礎(chǔ)上,創(chuàng)造性地將遺傳算法中的壽終正寢和優(yōu)勝劣汰機制引入到蛙跳算法中,設(shè)計了綜合效果更優(yōu)異的競爭蛙跳算法,并以此為基礎(chǔ)實施聯(lián)合火力打擊任務(wù)規(guī)劃,通過競爭蛙跳算法的多代迭代獲取最優(yōu)的規(guī)劃計劃,使任務(wù)規(guī)劃綜合評分達(dá)成全局最優(yōu)。創(chuàng)新點有，一是梳理了聯(lián)合火力打擊任務(wù)規(guī)劃的硬性和軟性約束條件,并提出了量化評分算法,實現(xiàn)了對聯(lián)合火力打擊任務(wù)規(guī)劃的量化評估;二是設(shè)計了新的智能優(yōu)化算法——競爭蛙跳算法,經(jīng)仿真實驗驗證,優(yōu)化分值和收斂效率均高于標(biāo)準(zhǔn)算法;三是將智能優(yōu)化算法引入聯(lián)合火力打擊任務(wù)規(guī)劃問題中,實現(xiàn)了基于計算機的自動優(yōu)化評估。仿真實驗結(jié)果表明,該方法可引入到聯(lián)合火力打擊任務(wù)規(guī)劃問題優(yōu)化中,能夠動態(tài)生成最優(yōu)的任務(wù)規(guī)劃,并以此為基礎(chǔ)擬制火力打擊方案和計劃,并提出量化的輔助決策建議,為聯(lián)合作戰(zhàn)指揮員定下火力打擊決心提供參考標(biāo)準(zhǔn)。