基于信息素遺傳算法的聯合火力打擊任務規劃

邢 巖，劉 昊，吳世杰

(1.沈陽航空航天大學 電子信息工程學院， 沈陽 110000； 2.國防大學聯合作戰學院， 石家莊 050000；3.遼寧省軍區， 沈陽 110000)

聯合火力打擊作為聯合作戰的重要組成部分，是形成和發揮諸軍兵種火力打擊部隊綜合作戰效能的實踐環節，對聯合火力打擊的任務規劃優劣直接影響諸軍兵種火力打擊部隊作戰能力的發揮，也是聯合作戰籌劃中的重點和難點[1]。軍事運籌學已經對火力打擊任務規劃中的動態火力分配問題進行深入系統的研究，并證明其屬于NP完全問題，聯合火力打擊任務規劃在原有動態火力分配基礎上，引入了多兵器、多彈種維度變量，各約束條件相互牽制，使問題復雜度進一步提升[2]。對于NP完全問題的求解，通常使用智能優化算法通過多代演化獲取具體問題的可行解，并通過對算法的改進試圖在有限代數內使可行解逼近全局最優，然而對智能優化算法的設計和改進方案仍處于探索階段。

自1972年遺傳算法被提出并應用于NP問題求解后，眾多原理不同、功能和設計理念各異的智能優化算法相繼被提出，代表算法包括以模擬生物群體行為特征的蟻群算法[3]、蛙跳算法[4]、蜂群算法[5]、粒子群算法[6]、布谷鳥算法[7]、螢火蟲算法[8]、魚群算法[9]等；以模擬自然現象的模擬退火算法[10]、量子進化算法[11]、細胞膜優化算法[12]等；以模擬生命演化規律的遺傳算法[13]、人口遷移算法[14]等。各種智能優化算法的設計原理和依據各異，在解決具體問題方面各具優勢，特別是遺傳算法作為最早提出的智能優化算法，因其構造簡單，優化效果明顯，成為應用最廣泛的智能優化算法。然而遺傳算法也存在如下問題：一是易陷入局部最優陷阱。當進化到一定代數時，受限于最優個體的自身結構，導致算法無法尋找到全局最優。二是進化代數不可控。不論算法的結束條件如何限定，都難以保證評分收斂和代數可控之間的平衡，使算法實效性有所降低。基于此，本文借鑒了蟻群算法中的信息素濃度概念，將其引入到遺傳算法的變異環節，實現可控性變異，以此提升算法收斂效率，并通過壽命條件和輪盤法的綜合運用，提升算法全局尋優能力，將信息素遺傳算法應用于聯合火力打擊任務規劃具體問題中，取得了良好的優化效果。

1 問題描述

聯合火力打擊任務規劃中的兵力、火力和目標之間的動態分配問題是典型的NP完全問題，包含了使目標火力毀傷份額達成情況下，必須滿足兵力、彈藥損耗最優化等約束條件。設我方參與聯合火力打擊的部隊為B={b1,b2,…,bn}，其中bk表示第k支部隊的數據輸入變量集合；敵方目標打擊清單中的目標為D={d1,d2,…,dm}，其中dl表示第l個目標的數據輸入變量集合；設聯合火力打擊任務規劃中，第k支部隊對第l個目標實施火力打擊時，H表示毀傷程度，G表示火力打擊任務份額，L表示消耗彈藥總量，Ts和Tz分別表示火力打擊起始和結束時刻，Tk表示第k支部隊的火力打擊總時長。設計聯合火力打擊任務規劃的硬約束條件如下：

1) 任務規劃必須完成上級分配的各目標火力打擊任務份額。設任務規劃中的子任務數為p個，則約束條件數學模型如下：

(1)

2) 任務規劃必須確保各火力打擊部隊留存彈藥完成臨機任務。設每次火力打擊的彈藥消耗量為li，則約束條件數學模型如下：

(2)

3) 任務規劃必須確保各火力打擊任務在上級規定時限內完成。約束條件數學模型如下：

(3)

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

(4)

在滿足硬約束條件基礎上，聯合火力打擊任務規劃還應滿足如下軟約束條件：

1) 突然性原則。火力打擊的持續時間盡可能短，保證火力打擊發起的突然性。

2) 損耗性原則。火力打擊部隊的兵力和彈藥損耗盡可能低，保證留存足夠兵力和彈藥完成臨機任務。

3) 平均性原則。火力打擊部隊擔負的任務量盡可能平均，保證各子任務平行展開，分擔壓力。

4) 一致性原則。任務規劃的總體火力打擊時長盡可能和上級規定的火力打擊開始、結束時限保持一致，保持持續的火力威懾效能。

5) 復合毀傷原則。由于對同一目標的多彈種打擊會造成高于單一彈種打擊造成的毀傷，任務規劃盡可能保證同一時刻多彈種對同一目標達成毀傷。

經過上述分析，歸納聯合火力打擊任務規劃的難點為：一是聯合火力打擊的參戰軍兵種多、彈種多、精確制導彈藥和范圍毀傷彈藥并存、各火力打擊子任務互相牽制，使綜合評分計算難度大幅提升；二是任務規劃必須留足兵力和火力應對臨機火力打擊任務，規劃任務和臨機任務的分配比例難以確定；三是任務規劃的優化只適用于當前敵我態勢，如何隨敵我態勢動態變化而修訂調整任務規劃也是聯合指揮員面臨的工作難點。

2 算法構建

信息素遺傳算法的內核仍然是智能優化算法，將智能優化算法應用于聯合火力打擊任務規劃等NP完全問題的算法設計步驟可分為數據錄入階段、向量空間轉換階段、綜合評分階段、智能優化階段。其中，數據錄入階段用于將聯合火力打擊任務規劃的具體數據指標錄入計算平臺；向量空間轉換階段用于將聯合火力打擊任務規劃中的兵力、火力、目標規劃問題轉換為多維向量空間中尋找全局最優位置問題，將代數問題轉換為幾何問題；綜合評分階段用于構建聯合火力打擊任務規劃的綜合評分模型，通過錄入的數據計算當前任務規劃下的綜合評分；智能優化階段以綜合評分模型為基礎，通過智能優化算法在多維空間中構建眾多隨機個體，通過個體的隨機游走或變異尋找周邊最優綜合評分，并在多代進化后輸出最優個體綜合評分。智能優化算法的流程如圖1所示。

圖1 智能優化算法流程框圖

2.1 信息素遺傳算法

遺傳算法是借鑒自然界的生物進化過程，模擬優勝劣汰和適者生存的競爭淘汰機制設計的智能優化算法，以偽隨機數模擬個體的變異過程，通過多代進化使最優個體綜合評分向全局最優評分收斂。標準遺傳算法的流程如圖2所示。

圖2 標準遺傳算法流程框圖

蟻群算法是M Dorigo等在1991年提出的智能優化算法，算法原理為：蟻群在覓食過程中會隨機遍歷所有路徑，并沿途釋放隨時間遞減的信息素，蟻群后續跟進的螞蟻個體則根據信息素濃度判斷哪條路徑經過的螞蟻多，并釋放信息素強化已遍歷路徑，經過多次迭代，越短的路徑信息素濃度就越高，濃度上升又會使后續蟻群選擇該路徑的幾率增大，最終使蟻群按照最優路徑找到食物。在蟻群算法中，信息素濃度能夠強化變異的正反饋循環，提升變異效率，縮短進化的迭代次數，因此考慮將信息素濃度引入到遺傳算法中，設計信息素遺傳算法。具體算法為：

步驟1：初始化種群。生成信息素濃度數組和禁忌表數組。

步驟2：創建個體。定義個體的數據結構如表1所示。

表1 個體數據結構

步驟3：計算種群綜合評分。將種群中的個體對應的任務規劃代入綜合評分算法中計算個體的綜合評分。

步驟4：種群滅絕。按照種群淘汰比例將種群規模壓縮，使用輪盤法選擇應保留的個體，保證高評分個體留存概率較大，低評分個體也有留存機會；所有留存個體的壽命+1。

步驟5：種群繁殖變異。使用輪盤法選擇繁殖的父代個體，按照禁忌表的選擇方向產生變異，同時根據禁忌表更新信息素數組中的濃度系數，沒變異的禁忌方向濃度遞減，產生變異的禁忌方向濃度遞增，使種群規模達到上限。設任務規劃子任務的目標序號為i，部隊序號為j，τij表示第j支部隊打擊第i個目標子任務的信息素濃度，ηij表示子任務綜合評分，α和β為重要程度參數，K表示禁忌表數組集合，則變異方向概率pij計算公式為：

(5)

步驟6：重復步驟3～5，并記錄每次進化的最優個體綜合評分。

步驟7：判斷退出。若達成退出條件，則退出算法并輸出最優個體及綜合評分。算法流程如圖3所示。

2.2 評估指標算法

根據聯合火力打擊任務規劃問題軟硬約束條件的分析，可將任務規劃的綜合指標區分為單目標類評估指標、單部隊類評估指標和體系評估指標3類。單目標類評估指標的數量和目標數等同，單部隊類評估指標的數量和部隊數等同，體系評估指標和任務規劃數等同。并基于3類評估指標設計11項具體指標，評估指標明細如圖4所示。

圖3 信息素遺傳算法流程框圖

圖4 聯合火力打擊任務規劃評估指標框圖

設聯合火力打擊部隊數為n，其中第i支部隊的火力打擊半徑為oi，在任務規劃中能夠執行打擊任務上限為ci，單次火力打擊時長為di，火力打擊之間的轉換周期為ei，部隊位置坐標為xmi和ymi；目標打擊清單中的目標數為m，其中第j個目標的規定毀傷程度為hj，目標位置坐標為xnj和ynj，對目標造成壓制毀傷對應的火力打擊次數為g40j，對目標造成殲滅毀傷對應的火力打擊次數為g60j；聯合火力打擊任務規劃中共包含子任務數為r，其中第k個子任務的對應火力打擊次數為lk，火力打擊起始時刻為pk，結束時刻為qk；執行該火力打擊后的部隊兵力損耗比例為u。計算評估指標前要對子任務進行可行性判斷：

1) 去除超程子任務，計算公式為：

(6)

2) 去除超過部隊火力打擊次數上限的子任務，計算公式為：

(7)

而后依次計算各項評估指標：

1) 單目標火力打擊時長(Aj)。代表對第j個目標實施火力打擊的總用時，計算公式為：

Aj=max{qj}-min{pj}

(8)

2) 單部隊火力打擊次數(Bi)。代表第i支部隊在任務規劃下執行火力打擊的總次數，計算公式為：

(9)

3) 火力打擊整體時長(C)。代表執行任務規劃各火力打擊任務的總用時，計算公式為：

C=max{qk}-min{pk}

(10)

4) 單目標冗余彈藥比例(Ej)。代表對第j個目標實施火力打擊分配的彈藥超過標準投放彈藥的比例。設投放彈藥比例為Dj，s表示目標等級，d表示部隊的火力打擊次數，計算公式為：

(11)

Ej=max{0,Dj-100}

(12)

5) 單目標完成任務比例(Fj)。代表對第j個目標實施火力打擊后，造成的毀傷份額占規定毀傷份額的比例，計算公式為：

Fj=min{100,Dj}

(13)

(14)

7) 防空預警削弱能力(Hr1)。代表在完成任務規劃中第r1個子任務時，對敵防空預警能力的削弱程度，計算公式為：

(15)

8) 地面打擊削弱能力(Ir1)。代表在完成任務規劃中第r1個子任務時，對敵地面遠程打擊能力的削弱程度，計算公式為：

(16)

9) 彈藥剩余比例(Ji)。代表第i支部隊完成所有火力打擊任務后剩余的彈藥占原有彈藥的比例，計算公式為：

(17)

10) 兵力剩余比例(Ki)。代表第i支部隊完成所有火力打擊任務后剩余的兵力占原有兵力的比例，計算公式為：

(18)

11) 復合打擊次數(L)。代表對同一目標的多彈種立體交叉火力打擊的發生次數，計算公式為：

(19)

(20)

2.3 綜合評分算法

針對聯合火力打擊任務規劃問題中的評估指標眾多、評估分值差異較大的情況，本研究借鑒了標準熵權法與理想點法，設計使用熵權理想點法對11類聯合火力打擊任務規劃的評估指標進行降維，并融合輸出為可量化比較的綜合評分。熵權理想點法的設計思路為：首先使用熵權法將各目標和各部隊的子類評估指標按照目標和部隊的分類計算熵權，并加權求和計算出單目標類中的3項評估指標和單部隊類中的3項評估指標；而后計算5項體系評估指標；最后使用理想點法對11項已經量化梳理好的評估指標進行理想點位空間距離計算，形成量化可比的綜合評分。熵權理想點法規避了復雜系統建模中評估指標過細、層次過多等問題，將復雜系統中的各類評估指標區分層次加以實施分步融合，使得綜合評分更加客觀可信，特別適用于解決復雜系統建模中的多指標量化評估問題。

使用熵權法[15]將單目標類評估指標和單部隊類評估指標融合為單一分值。設聯合火力打擊任務規劃中，共有m個火力打擊目標，n個任務規劃參與綜合評分，則構建矩陣X，熵權法融合的計算流程如下：

步驟1：歸一化計算。將矩陣X轉換為歸一化矩陣P，計算公式為：

(21)

步驟2：熵值計算。通過歸一化矩陣P計算m個目標的對應熵值ej，計算公式為：

柑桔紅蜘蛛的防治是贛南臍橙病蟲害防治中一項很重要的工作。柑桔紅蜘蛛一年代數很多，為害大。為提高臍橙的產量與質量，柑桔紅蜘蛛防治工作必須持之以恒。

(22)

步驟3：熵權計算。通過熵值ej計算m個目標對應的熵權重tj，計算公式為：

(23)

步驟4：融合分值計算。通過熵權重tj和矩陣X計算各任務規劃的融合分值zi，計算公式為：

(24)

獲取11項評估指標后，建立n個任務規劃的評估指標矩陣Z，使用理想點法[16]將各評估指標融合為單一的綜合評分，理想點法的計算流程如下：

步驟1：理想點計算。通過矩陣Z獲取正負理想點A+和A-，計算公式為：

(25)

(26)

(27)

(28)

步驟3：綜合評分計算。通過理想距離計算綜合評分，計算公式為：

(29)

3 仿真分析

為了驗證信息素遺傳算法應用于聯合火力打擊任務規劃的適用性，采用文獻[13]中提供的標準遺傳算法作為參考算法，設計綜合評分算法。仿真實驗平臺配置為：Intel酷睿雙核處理器T7300 2.0GHz；3G內存；Window 7 32位操作系統；VC6.0編程環境。為了檢驗算法應用于聯合火力打擊任務規劃的合理性，設置我方火力打擊部隊的兵力配置如表2所示。

敵方目標的屬性及打擊毀傷情況如表3所示。

表3 目標屬性及打擊毀傷情況(簡略)

3.1 參數有效性分析

首先通過仿真實驗修正信息素遺傳算法的各項輸入參數，確保算法達到最優效果。通過算法分析，引入參數如下：種群規模、變異概率、信息素更新系數、淘汰比例、壽命上限、進化退出代數。參數有效性實驗步驟為：

步驟1：為所有參數輸入初始值；

步驟2：以某一參數為調整對象，在取值范圍內微調；

步驟3：計算參數設置條件下的算法綜合評分；

步驟4：重復步驟2～3，直至找到某一參數的最佳參數值；

步驟5：重復步驟2～4，直至找到所有參數的最佳參數值。

需要注意的是，調整參數初始值后，需要重新微調各參數值，否則綜合評分不準確。通過仿真實驗，確定信息素遺傳算法的參數有效性指標如表4所示。

表4 參數有效性指標

3.2 綜合評分對比

為了驗證信息素遺傳算法的優化性能，以標準遺傳算法為參考算法設計仿真實驗如下：

步驟1：初始化算法環境，設置進化次數均為300代；

步驟2：將算法代入聯合火力打擊任務規劃問題，計算各代個體綜合評分；

步驟3：標記算法全局最優個體和各代最優個體的綜合評分；

步驟4：輸出結果。

算法全局最優個體綜合評分和各代最優個體綜合評分情況如圖5和圖6所示。

圖5 全局最優個體綜合評分曲線

圖6 各代最優個體綜合評分曲線

實驗結果表明：信息素遺傳算法的收斂效率明顯高于標準遺傳算法，這主要是由于引入信息素濃度對變異方向進行了自動控制，算法會自動向高分變異方向傾斜。此外，信息素遺傳算法的綜合評分高于標準遺傳算法，這主要是由于信息素遺傳算法引入了壽終正寢和輪盤法選取下一代繁殖個體，使種群的多樣性相較于標準遺傳算法更高，全局尋優能力更強。

3.3 最優個體對比

為了驗證信息素遺傳算法獲取的全局最優個體性能，以標準遺傳算法獲取的全局最優個體作為參考對象，分析比較兩種個體的獲取時間、進化代數以及個體內各評估指標的情況。兩種算法最優個體的獲取時間如圖7所示，完成算法的進化代數如圖8所示。

圖7 最優個體獲取時間圖

圖8 進化代數圖

實驗結果表明，信息素遺傳算法最優個體具有更短的收斂時間和更低的收斂代數，算法效率明顯高于標準遺傳算法，具有更好的工程應用前景。對兩種算法最優個體各項評估指標如圖9所示。

圖9 最優個體各項評估指標分值圖

實驗結果表明，信息素遺傳算法的各項評估指標與標準遺傳算法最優個體相差不大，其中單目標完成任務比例(No.3)和復合打擊次數(No.11)評估指標要明顯高于標準遺傳算法最優個體，綜合評分則略有提升，由此可以判斷，標準遺傳算法獲取的最優個體并非全局最優。最優個體對應的聯合火力打擊任務規劃示例的突擊時間如表3所示。

表5 聯合火力打擊任務規劃示例的突擊時間

續表(表5)

4 結論

1) 構建了能夠量化比較的聯合火力打擊任務規劃評分計算模型，初步實現了任務規劃之間的多角度對比分析。

2) 在標準遺傳算法的基礎上，參考蟻群算法構造，設計了信息素遺傳算法，實現了可控性變異，縮短進化收斂代數。

3) 設計了聯合火力打擊任務規劃智能優化的整體流程，通過使用信息素遺傳算法實現了任務規劃的自動優化，在時間和優化效果上均滿足工程實踐要求。

4) 信息素遺傳算法能夠有效解決聯合火力打擊任務規劃問題，具有良好的工程應用效果。