基于進(jìn)化粒子群算法的聯(lián)合火力打擊任務(wù)規(guī)劃方法?

劉 昊 宋敬峰 陳 超

（1.國防大學(xué)聯(lián)合作戰(zhàn)學(xué)院 石家莊 050000）（2.31696部隊參謀部 錦州 121000）（3.93123部隊參謀部 遼陽 111000）

1 引言

聯(lián)合火力打擊任務(wù)規(guī)劃是聯(lián)合作戰(zhàn)火力打擊過程中對諸軍兵種火力打擊部隊執(zhí)行火力打擊任務(wù)的動態(tài)規(guī)劃任務(wù)集合，是確定火力打擊中目標(biāo)、部隊、彈種、用量的格式化命令表述形式，是指揮員用以指揮聯(lián)合火力打擊的最終輸出指令樣式[1]。在軍事運(yùn)籌領(lǐng)域，聯(lián)合火力打擊任務(wù)規(guī)劃屬于動態(tài)火力分配問題，是典型的NP完全問題，在諸軍兵種聯(lián)合作戰(zhàn)的背景下，火力分配又融入多兵種、多彈種的多維變量，使優(yōu)化計算復(fù)雜度和算法工作量進(jìn)一步提升，傳統(tǒng)機(jī)械化戰(zhàn)爭中依靠人工分配火力打擊任務(wù)的規(guī)劃方式難以應(yīng)對，必須考慮采用計算機(jī)輔助規(guī)劃的手段予以解決[2]。隨著計算機(jī)性能的提升和人工智能技術(shù)的發(fā)展成熟，智能優(yōu)化算法逐步替代原有以線性規(guī)劃為代表的數(shù)學(xué)規(guī)劃方法，成為任務(wù)規(guī)劃領(lǐng)域的主流算法。相較于數(shù)學(xué)規(guī)劃方法，智能優(yōu)化算法具備指標(biāo)離散性、約束條件可調(diào)、輸出結(jié)果可控等優(yōu)點，廣泛應(yīng)用于工程實踐領(lǐng)域。

智能優(yōu)化算法按照優(yōu)化原理可分為模擬生物種群特征的遺傳算法[3]、量子進(jìn)化算法[4]；模擬自然界物理規(guī)律的細(xì)胞膜滲透算法[5]、模擬退火算法[6]；以及模擬生物群體行為特征的蜂群算法[7]、蟻群算法[8]、粒子群算法[9]、蛙跳算法[10]等。上述智能優(yōu)化算法中，遺傳算法提出相對較早，算法設(shè)計較為簡單，對后代各類智能優(yōu)化算法影響較大；粒子群算法是1995年由Kennedy和Eberhart提出，其模擬自然界中鳥群覓食的行為特征，通過設(shè)計智能體向空間中的“食物豐沛區(qū)”移動尋找最優(yōu)解，具備較高的迭代效率。然而粒子群算法也存在易陷入局部最優(yōu)和迭代次數(shù)不可控的問題，無法保證在有限時間內(nèi)找到符合要求的全局最優(yōu)解。本文通過借鑒遺傳算法和粒子群算法的內(nèi)在原理，在粒子群算法中引入遺傳算法中遺傳變異和優(yōu)勝劣汰的生物競爭機(jī)制，構(gòu)造進(jìn)化粒子群算法，以此提升迭代效率和全局尋優(yōu)能力，并將算法引入聯(lián)合火力打擊任務(wù)規(guī)劃中，解決任務(wù)規(guī)劃的優(yōu)化問題。

2 問題描述

聯(lián)合火力打擊任務(wù)規(guī)劃問題的核心是在有效時限內(nèi)對我方兵器、彈種和敵方目標(biāo)之間的最優(yōu)化匹配，以實現(xiàn)體系破擊毀傷效果，并以完成上級賦予的目標(biāo)火力毀傷任務(wù)份額為前提，減少我方兵力和彈藥損耗。根據(jù)問題需求，可對聯(lián)合火力打擊任務(wù)規(guī)劃設(shè)定硬約束條件如下。

一是必須保證完成上級賦予的火力毀傷任務(wù)份額；二是必須保證我方火力打擊部隊能夠隨時執(zhí)行臨機(jī)火力打擊任務(wù)；三是必須保證所有火力打擊任務(wù)在規(guī)定時限內(nèi)完成。設(shè)聯(lián)合火力打擊的部隊模型用B=｛b1，b2，……，bn｝表示，其中 bk代表火力打擊部隊的屬性集合；聯(lián)合火力打擊目標(biāo)模型用D=｛d1，d2，……，dm｝表示，其中dl代表火力打擊目標(biāo)的屬性集合；H（dl，bk）表示第k支部隊對第l個目標(biāo)實施火力打擊產(chǎn)生的毀傷程度；G（dl，bk）表示第 k支部隊擔(dān)負(fù)對第l個目標(biāo)的火力打擊任務(wù)份額；p表示任務(wù)規(guī)劃的子任務(wù)數(shù)量，l表示彈藥消耗量，Lk表示第k支部隊的彈藥總量，Ts表示火力打擊起始時刻，Tz表示火力打擊結(jié)束時刻，Tk表示第k支部隊的火力打擊總時長。則根據(jù)聯(lián)合火力打擊任務(wù)規(guī)劃的硬約束條件，建立數(shù)學(xué)模型如下：

此外，為了使聯(lián)合火力打擊任務(wù)規(guī)劃可量化比較優(yōu)劣，在滿足硬約束條件的前提下，設(shè)置軟約束條件如下。

一是我方參加火力打擊的部隊兵力損耗越小越好；二是我方執(zhí)行火力打擊的彈藥消耗越少越好；三是各軍兵種部隊的執(zhí)行任務(wù)壓力盡量平均；四是完成聯(lián)合火力打擊的總體時長越少越好；五是保持隨時有空余部隊執(zhí)行臨機(jī)火力打擊任務(wù)；六是對同一目標(biāo)同一時刻的復(fù)合打擊次數(shù)越多越好。

通過對聯(lián)合火力打擊任務(wù)規(guī)劃的軟硬約束條件分析和建?？芍?，問題的難點在于各約束條件縱橫交叉、相互制約，難以在評分算法中取得統(tǒng)一的綜合評估結(jié)果；此外，參與聯(lián)合火力打擊的諸軍兵種部隊的兵器、彈種、作戰(zhàn)使用條件各不相同，使聯(lián)合火力打擊任務(wù)規(guī)劃的可行性評估難度大幅提升，手工規(guī)劃難以解決，必須依靠智能算法通過多代迭代求解。

3 算法構(gòu)建

智能優(yōu)化算法應(yīng)用于聯(lián)合火力打擊任務(wù)規(guī)劃，可采取問題視角切換、隨機(jī)變量迭代、批量評估選優(yōu)的方法設(shè)計算法構(gòu)架，選擇合適的智能優(yōu)化算法種類，完成任務(wù)規(guī)劃的優(yōu)選和輸出?；诖?，智能優(yōu)化算法由數(shù)據(jù)錄入、向量空間建立、綜合評估、粒子群優(yōu)化四個部分構(gòu)成。數(shù)據(jù)錄入模塊采集聯(lián)合火力打擊任務(wù)規(guī)劃所需的基礎(chǔ)數(shù)據(jù)，以格式化形式存儲分發(fā)；向量空間建立模塊將聯(lián)合火力打擊任務(wù)規(guī)劃的兵力、火力、目標(biāo)轉(zhuǎn)換為多維空間中的維度，從而將優(yōu)化問題視角切換為多維向量空間尋優(yōu)問題；綜合評估模塊按照粒子群個體的空間位置向量結(jié)構(gòu)計算綜合評分并輸出，作為評估個體優(yōu)劣的依據(jù)；粒子群優(yōu)化模塊構(gòu)造能夠隨機(jī)覓食的種群個體，通過多代迭代尋優(yōu)并輸出最優(yōu)解向量。智能優(yōu)化算法的流程如圖1所示。

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

3.1 進(jìn)化粒子群算法

粒子群算法是借鑒鳥群覓食行為設(shè)計的智能優(yōu)化算法，算法在多維向量空間中隨機(jī)產(chǎn)生眾多個體，將空間位置的綜合評分看做食物，則個體可根據(jù)所在位置周邊的食物豐沛情況自主游走，經(jīng)過多代迭代使最優(yōu)個體綜合評分收斂于全局最優(yōu)解。粒子群算法流程如圖2所示。

圖2 粒子群化算法流程圖

進(jìn)化粒子群算法在標(biāo)準(zhǔn)粒子群算法基礎(chǔ)上，借鑒遺傳算法中的優(yōu)勝劣汰進(jìn)化機(jī)制，在個體結(jié)構(gòu)中引入壽命和淘汰系數(shù)，當(dāng)個體處于食物貧瘠區(qū)，隨著多次游走導(dǎo)致淘汰系數(shù)上升，當(dāng)超過淘汰閾值即判斷當(dāng)前空間位置附近沒有最優(yōu)解，刪除該個體；由高分個體繁殖后代個體代替刪除個體，繁殖個體壽命+1；當(dāng)有個體壽命達(dá)到上限，判定個體死亡，刪除超齡個體以防算法陷入局部最優(yōu)。進(jìn)化粒子群算法的流程如圖3所示。

圖3 進(jìn)化粒子群化算法流程圖

具體算法如下：

Step1：建立向量空間。

Step2：設(shè)置初始種群。個體結(jié)構(gòu)如表1所示。

表1 進(jìn)化粒子群算法個體結(jié)構(gòu)

Step3：計算個體下一游走位置。設(shè)個體當(dāng)前的位置為Xi，Pi為個體當(dāng)前為止游走到的最優(yōu)位置，Qi為種群當(dāng)前游走到的最優(yōu)位置，Vi為個體當(dāng)前游走步長；r1和r2為隨機(jī)實數(shù)。則個體下一游走步長Vi+1計算公式為

設(shè)種群個數(shù)為n，Pij為第j個個體當(dāng)前為止游走到的最優(yōu)位置，遷移系數(shù)Mi計算公式為

設(shè)u為0～1之間的隨機(jī)實數(shù)，個體下一游走位置Xi+1計算公式為

Step4：計算所有個體綜合評分。

Step5：種群淘汰。刪除淘汰系數(shù)超過閾值的個體，刪除超過壽命上限的個體，而后對所有個體比較歷史最優(yōu)評分，刪除低評分個體。

Step6：種群繁殖。使用輪盤法選中父代個體，按照變異概率對個體中的火力分配任務(wù)進(jìn)行調(diào)整，產(chǎn)生新個體，使種群規(guī)模達(dá)到上限。

Step7：重復(fù)Step3～6，直至算法滿足退出條件：在達(dá)到收斂代數(shù)閾值時，最優(yōu)個體綜合評分未更新。算法退出并輸出全局最優(yōu)個體歷史綜合評分。

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

對于聯(lián)合火力打擊任務(wù)規(guī)劃的軟硬約束條件，本文采取層次分析法，對任務(wù)規(guī)劃的評估指標(biāo)進(jìn)行量化分析，將其分為單目標(biāo)指標(biāo)類、單部隊指標(biāo)類、體系指標(biāo)類，并將其細(xì)化為11項具體評估指標(biāo)。評估指標(biāo)明細(xì)如圖4所示。

圖4 評估指標(biāo)明細(xì)

設(shè)參加聯(lián)合火力打擊的部隊數(shù)為m，其中第i支部隊打擊半徑為oi，火力打擊次數(shù)上限為ci，執(zhí)行任務(wù)耗時為di，火力打擊任務(wù)間隔轉(zhuǎn)換耗時為ei，部隊坐標(biāo)位置為xmi和ymi；火力打擊目標(biāo)的數(shù)量為n，其中第j個目標(biāo)的規(guī)定毀傷程度為hj，目標(biāo)坐標(biāo)位置為xnj和ynj；若第i支部隊對第j個目標(biāo)實施火力打擊，設(shè)壓制火力毀傷對應(yīng)的火力打擊次數(shù)為g40ij，殲滅火力毀傷對應(yīng)的火力打擊次數(shù)為g60ij；聯(lián)合火力打擊任務(wù)規(guī)劃中，設(shè)共包含子任務(wù)數(shù)為r個，其中第k個子任務(wù)的執(zhí)行火力打擊次數(shù)為lk，起始時刻為pk，結(jié)束時刻為qk；部隊執(zhí)行任務(wù)對應(yīng)的兵力損耗系數(shù)為u。對任務(wù)規(guī)劃的可行性判斷主要包括：

1）保證目標(biāo)距離不能超過部隊射程。計算公式為

2）保證部隊執(zhí)行任務(wù)數(shù)不能超過任務(wù)上限數(shù)。計算公式為

對各類評估指標(biāo)的量化分析如下：

1）單目標(biāo)打擊時長（Aj）。表示第j個目標(biāo)在任務(wù)規(guī)劃火力打擊過程中，遭火力打擊的起止時長。計算公式為

2）單部隊打擊次數(shù)（Bi）。表示第i支部隊在任務(wù)規(guī)劃火力打擊過程中，實際完成火力打擊的次數(shù)。計算公式為

3）整體打擊時長（C）。表示任務(wù)規(guī)劃中各火力打擊子任務(wù)的總體起止時長。計算公式為

4）單目標(biāo)冗余彈藥比例（Ej）。表示第j個目標(biāo)在任務(wù)規(guī)劃火力打擊過程中，被分配到的彈藥用量超過其規(guī)定毀傷程度對應(yīng)彈藥量的比例。設(shè)投入彈藥比例為Dj，目標(biāo)等級為s，火力打擊次數(shù)為d。計算公式為

5）單目標(biāo)完成任務(wù)比例（Fj）。表示第j個目標(biāo)在任務(wù)規(guī)劃火力打擊過程中，被分配到的彈藥用量與規(guī)定毀傷程度對應(yīng)彈藥量的比例。計算公式為

6）體系破擊能力（Gr1）。表示當(dāng)執(zhí)行完第r1個子任務(wù)時，對敵目標(biāo)體系的破壞程度。計算公式為

7）防空削弱能力（Hr1）。表示當(dāng)執(zhí)行完第r1個子任務(wù)時，對敵防空預(yù)警能力的破壞程度。計算公式為

8）地面打擊削弱能力（Ir1）。表示當(dāng)執(zhí)行完第r1個子任務(wù)時，對敵地面打擊能力的破壞程度。計算公式為

9）彈藥剩余比例（Ji）。表示第i支部隊在任務(wù)規(guī)劃火力打擊后，剩余彈藥量占攜帶彈藥總量的比例。計算公式為

10）兵力剩余比例（K）i。表示第i支部隊在任務(wù)規(guī)劃火力打擊后，通過綜合衡量敵方的體系破擊情況、防空削弱情況、地面打擊削弱情況，綜合預(yù)測兵力剩余數(shù)量占原有兵力數(shù)量的比例。計算公式為

11）復(fù)合打擊次數(shù)（L）。表示任務(wù)規(guī)劃中對目標(biāo)實現(xiàn)多彈種、多兵種立體交叉火力打擊的總次數(shù)。計算公式為

3.3 綜合評分模型

在評估指標(biāo)模型中，單目標(biāo)指標(biāo)類和單部隊指標(biāo)類是針對每個目標(biāo)和每支部隊計算的評估分值，因此需將各子評分融合為對應(yīng)的評估指標(biāo)分值，本文采用熵權(quán)法[11]進(jìn)行子評分的融合計算。以單部隊指標(biāo)類的單部隊打擊次數(shù)評估指標(biāo)為例，設(shè)目標(biāo)數(shù)為m，聯(lián)合火力打擊任務(wù)規(guī)劃的參評數(shù)為n，建立矩陣X。熵權(quán)法計算指標(biāo)類的計算流程如下：

Step1：歸一化處理。通過歸一化變換將矩陣X轉(zhuǎn)換為矩陣P，計算公式為

Step2：熵值計算。通過熵值公式將矩陣P中的m列轉(zhuǎn)換為ej，計算公式為

Step3：熵權(quán)重計算。通過熵權(quán)重公式將熵值ej轉(zhuǎn)換為熵權(quán)重tj，計算公式為

Step4：融合評估指標(biāo)類計算。通過矩陣X和熵權(quán)重tj生成評估指標(biāo)值zi，計算公式為

通過熵權(quán)法獲取n個聯(lián)合火力打擊任務(wù)規(guī)劃的11類評估指標(biāo)后，使用理想點法[12]獲取各任務(wù)規(guī)劃的綜合評分，實現(xiàn)聯(lián)合火力打擊任務(wù)規(guī)劃的量化對比評估。計算流程如下：

Step1：理想點計算。獲取正負(fù)理想點的空間位置A+和A-，計算公式為

Step2：理想距離計算。獲取第i個任務(wù)規(guī)劃和正負(fù)理想點位置的空間距離di+和di-，計算公式為

Step3：綜合評分計算。獲取第i個任務(wù)規(guī)劃的綜合評分Mi，計算公式為

4 仿真分析

為了驗證粒子群算法在聯(lián)合火力打擊任務(wù)規(guī)劃問題求解中的具體優(yōu)化性能，設(shè)計仿真實驗如下：采用文獻(xiàn)[3]提供的標(biāo)準(zhǔn)遺傳算法和文獻(xiàn)[9]提供的標(biāo)準(zhǔn)粒子群算法作為參照對象，通過同類同源對比效果的方法分析算法的優(yōu)缺點和有效性。仿真實驗建模環(huán)境為Intel酷睿雙核處理器T7300 2.0GHz；3G運(yùn)行內(nèi)存；Windows 7 32位操作系統(tǒng)；vc6.0仿真編程環(huán)境。

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

鑒于進(jìn)化粒子群算法優(yōu)化過程中的調(diào)試參數(shù)眾多，難以有效衡量算法的綜合優(yōu)化效果，采取蒙特卡羅仿真的方法對各參數(shù)在取值范圍內(nèi)的優(yōu)化迭代，找到最佳參數(shù)取值組合。根據(jù)算法的內(nèi)部結(jié)構(gòu)，選取的參數(shù)包括：個體壽命上限、個體變異概率、個體淘汰系數(shù)上限、覓食步長、允許覓食次數(shù)、判定收斂代數(shù)，r1，r2。各參數(shù)的優(yōu)化結(jié)果如表2所示。

表2 參數(shù)優(yōu)化結(jié)果

4.2 優(yōu)化效果分析

為了檢驗進(jìn)化粒子群算法應(yīng)用于聯(lián)合火力打擊任務(wù)規(guī)劃的有效性，并分析算法性能，以標(biāo)準(zhǔn)粒子群算法和遺傳算法作為對比算法，統(tǒng)一設(shè)定迭代次數(shù)為500代，并標(biāo)記各代最優(yōu)個體的綜合評分，以及全局最優(yōu)個體的綜合評分。三種算法各代最優(yōu)個體綜合評分情況如圖5所示。

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

三種算法全局最優(yōu)個體綜合評分情況如圖6所示。

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

實驗結(jié)果表明，進(jìn)化粒子群算法相比于標(biāo)準(zhǔn)粒子群算法和遺傳算法的收斂效率和收斂綜合評分均較高，側(cè)面證明了標(biāo)準(zhǔn)粒子群算法和遺傳算法通過有限代數(shù)的迭代獲取的最優(yōu)個體并非全局最優(yōu)個體，相比之下進(jìn)化粒子群算法能夠在有限代數(shù)內(nèi)獲取更高性能的可行解，算法的應(yīng)用性和尋優(yōu)能力更強(qiáng)。通過對圖5的分析可知，由于進(jìn)化粒子群算法引入了遺傳算法中的個體優(yōu)勝劣汰機(jī)制，并且加入了壽命限制系數(shù)，使得算法的全局尋優(yōu)能力更強(qiáng)，圖5中進(jìn)化粒子群算法各代最優(yōu)個體綜合評分抖動的更頻繁劇烈，算法通過多代嘗試尋找全局范圍內(nèi)的最優(yōu)解，標(biāo)準(zhǔn)粒子群算法和遺傳算法在此方面的表現(xiàn)相對較弱。

4.3 最優(yōu)結(jié)果對比分析

將三種算法獲取的全局最優(yōu)個體對比分析，圖7為最優(yōu)個體內(nèi)各評估指標(biāo)的對比分析情況。

圖7 全局最優(yōu)個體各評估指標(biāo)對比

實驗結(jié)果表明，進(jìn)化例子群算法最優(yōu)個體的彈藥剩余比例（No.6）評估指標(biāo)明顯優(yōu)于標(biāo)準(zhǔn)粒子群算法和遺傳算法，側(cè)面證明了進(jìn)化粒子群算法在應(yīng)對臨機(jī)火力打擊任務(wù)時具備更好的優(yōu)化效果。綜合評分的比較上，進(jìn)化粒子群算法最優(yōu)個體綜合評分明顯高于另外兩種算法。圖8為三種算法完成收斂的迭代次數(shù)對比分析情況。

圖8 算法迭代次數(shù)對比

圖9為三種算法獲取最優(yōu)個體的時間消耗對比分析情況。

圖9 算法時間消耗對比

實驗結(jié)果表明，進(jìn)化粒子群算法的迭代次數(shù)和時間消耗都要低于標(biāo)準(zhǔn)粒子群算法，基本和遺傳算法持平，遺傳算法的效率最高，但綜合考慮最優(yōu)個體的性能表現(xiàn)，進(jìn)化粒子群仍然具備較強(qiáng)的競爭能力。進(jìn)化粒子群算法獲取的最優(yōu)聯(lián)合火力打擊任務(wù)規(guī)劃示例如表3所示。

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

5 結(jié)語

本文在借鑒標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上，將遺傳算法中的優(yōu)勝劣汰和壽終正寢機(jī)制引入到粒子群算法，使算法的收斂效率和全局尋優(yōu)能力進(jìn)一步增強(qiáng)，并將其引入到聯(lián)合火力打擊任務(wù)規(guī)劃具體問題求解中。創(chuàng)新點有：一是設(shè)計了基于標(biāo)準(zhǔn)粒子群算法的進(jìn)化粒子群算法，經(jīng)仿真實驗檢驗，算法的各方面性能指標(biāo)均優(yōu)于原算法。二是通過對聯(lián)合火力打擊任務(wù)規(guī)劃的約束條件分析，構(gòu)建了能夠?qū)崿F(xiàn)任務(wù)規(guī)劃綜合評分的數(shù)學(xué)模型及相應(yīng)評估算法。三是將智能優(yōu)化算法引入聯(lián)合火力打擊任務(wù)規(guī)劃中，實現(xiàn)了自動優(yōu)化，為指揮員指揮決策提供了量化的輔助決策參考。