基于遺傳算法的虛兵火力協同任務規劃

黃義松　趙德勇　李明雨

摘要：從虛擬兵力智能化角度出發，針對虛擬兵力火力協同任務規劃問題，提出了一種對重要目標優先打擊，同時彈藥消耗最低的任務規劃模型，并采用遺傳算法對不同火力單元打擊多個任務目標的規劃問題進行求解優化。最后通過仿真試驗對構建的算法進行驗證，結果表明構建的模型算法能夠很好地對火力協同任務規劃問題進行求解，提高火力打擊效益，實現虛擬兵力的智能決策。

關鍵詞：虛擬兵力；遺傳算法；任務規劃；火力協同

一、前言

火力協同任務規劃作為虛擬兵力智能行為的重要組成部分，是一種NP完全問題[1]，也是實現虛擬兵力智能決策行為的關鍵環節。在對多個目標進行火力協同任務規劃的活動過程中，火力任務分配的結果直接影響著火力打擊的效果，同時也是虛擬兵力智能決策的重難點。劉鈺等[2]提出了融合禁忌搜索概念的遺傳算法，對艦載機的保障調度優化展開了研究。王海峰等[3]將蛙跳算法和遺傳算法相結合，對聯合火力打擊目標動態分配問題進行了研究。王書勤等[4]采用遺傳算法對武警捕殲任務的兵力派遣問題進行了研究。李天龍等[5]在空地多目標火力分配優化問題上，引入遺傳算法構建數學模型并進行了驗證。對于任務規劃這種NP完全問題的優化，遺傳算法作為較早提出的智能化算法，其結果優化顯著，并且具有較好的魯棒性，能夠較好地實現對任務規劃問題進行求解和優化[6]。

二、問題描述

在指揮訓練活動中，虛擬兵力按照指揮信息對多個目標實施火力打擊的過程中，火力協同任務規劃問題是虛擬兵力智能決策需要重點考慮的問題。不同虛擬兵力對多個目標進行火力打擊所涉及的兵力選擇、火力運用、目標選定等問題以及動態調整分配是一種NP完全問題。火力協同必須在完成火力打擊任務的情況下，考慮打擊目標的重要程度、威脅程度、毀傷程度、目標類型和選定兵力位置、射程、命中概率、毀傷能力、彈藥消耗等因素，對火力運用、彈藥損耗等問題進行優化。

三、算法構建

遺傳算法在本質上是對NP完全問題進行智能優化的一種算法。在組織火力協同任務規劃采用遺傳算法進行智能決策時，其算法步驟可大致劃分為數據錄入階段、數據向量轉換階段、評估階段以及優化處理階段。其中，數據錄入階段主要是將火力協同任務中的參與協同的單位、打擊目標等具體戰場態勢信息數據輸入計算系統中；數據轉換階段主要是將輸入的戰場態勢信息數據轉化為多維度的數據向量，實質上是將火力協同任務規劃問題轉變為在多維度幾何空間中求得整體性最優解的問題；評估階段主要通過火力協同任務規劃的評估模型，對轉化后的數據進行計算，評估當前的火力規劃下所得的評分；優化處理階段以評估階段所得的評分為依據，在多維空間中隨機選取個體，利用智能優化算法對選取的個體進行交叉變異得到新的個體，并對其進行評估，同時對評分最優的個體進行標記。在經過多次迭代循環后輸出最優個體。

傳統的遺傳算法能夠以靈活的方式對大部分優化問題求解，能夠有效地避免局部極小值的發生。但其在個體選擇方面上的隨機性，有時會導致需要進行較長次數的迭代，無法快速地對問題求解。同時對于較為復雜的問題，往往還需要占用極大地內存用來計算。為解決上述問題，可以這里引入螞蟻算法中的信息素的概念，利用信息素濃度來影響個體的交叉變異，提高進化效率，減少迭代的次數。具體的算法如圖1所示。

1.種族初始化。針對火力協同任務分配問題，可以這里采用二進制的方法進行編碼，用基因位來表示打擊目標所對應的火力單位，既每個基因組表示目標由第幾個火力單位負責打擊，基因組可視為種族中的一個個體。例如基因組100010中的基因位數表示有6個火力單元，1表示相應基因位的火力單元對該目標進行打擊，0表示不打擊，則該基因組代表的打擊方案為該目標由第1和第5火力單元負責打擊。若有n個目標，基因長度就為6n，代表每個目標的基因之間用“：”進行分隔，“：”不參與實際運算。種族初始化就是盡可能多的隨機生成個體，構成第一代種族群體，既表示著不同火力分配方案的集合。同時生成個體的信息素初始濃度以及火力單元禁忌表。

2.適應度函數。經過對火力協同任務規劃進行問題描述，根據梳理出的約束條件，我們主要將打擊目標的威脅程度、目標類型和火力單元的位置、射程、命中概率、彈藥留存比作為評估的影響因素來構建適應度函數（見表1）。

3.種族滅絕。“種族滅絕”并不是將所有的個體信息進行刪除，而是按照一定的比例減少個體的數量，并令存活下的個體壽命加1。“種族滅絕”是為了能夠更快的從種群中選擇優秀的個體，作為父體以產生后代，選擇的方法對生成的后代個體具有較大的影響。這里采用輪盤法的方式來確定要保留的個體，使得評分高的個體能有較大的概率得以保留，同時也確保評分低的個體有概率得以生存，其選擇公式如下所示：

4.交叉變異（更新信息素濃度）。交叉變異是對生物染色體交換基因和基因突變的仿真。其中交叉是從種族滅絕后留存的個體中選擇兩個作為雙親，并在它們的基因組中選擇截斷點，將被截斷的基因相互交換，產生新的個體，根據截斷點的不同，交叉類型可劃分有：一點交叉、二點交叉以及均勻交叉，其基因交換過程如圖2所示。變異環節根據火力單元禁忌表選擇基因變異的方向，并且更新個體的信息素濃度，提高發生變異個體的信息素濃度，相應地降低未發生變異個體的信息素濃度。設μij為火力單元i對目標j進行火力打擊的信息素濃度，α為μij的重要度參數；fij為火力單元i對目標j進行火力打擊的適應度，β為個體適應度的影響系數；H表示火力單元禁忌表，既不可選擇的火力單元的集合。發生變異概率δij的公式如下：

5.判斷退出。判斷遺傳算法是否達到設置的退出條件，若未達到則重復上述環節，若已經達到退出條件，則輸出最優的個體并退出。

四、案例分析

五、結語

本文針對虛擬兵力火力協同任務規劃的智能決策問題，提出了一種信息素遺傳算法對NP完全問題進行智能優化的方法。通過對決策問題進行梳理分析，得到軟硬2類約束條件，建立了基本問題模型，并采用遺傳算法對問題求解，并通過仿真實例對算法進行驗證。結果表明該算法能夠在綜合考慮打擊目標的重要程度、威脅程度、毀傷程度、目標類型和選定兵力的位置、射程、命中概率、毀傷能力、彈藥消耗等因素的情況下，對火力協同任務規劃進行求解和優化，有效地提高了火力打擊效益。

參考文獻

[1]邢巖，劉昊，吳世杰.基于信息素遺傳算法的聯合火力打擊任務規劃[J].兵器裝備工程學報，2020，41（8）：169-175，192.

[2]劉鈺，王能建，羅旭，等.采用改進遺傳算法的艦載機保障調度方法[J].國防科技大學學報，2020，42（2）：194-205.

[3]王海峰，高小軍，劉昊.基于競爭蛙跳算法的聯合火力打擊任務規劃方法[J].指揮控制與仿真，2019，41（4）：65-71.

[4]王書勤，黃茜.基于遺傳算法的武警捕殲戰斗兵力優化指派建模與仿真[J].數學的實踐與認識，2020，50（15）：164-169.

[5]李天龍，張軍超.基于融合算法的空—地多目標攻擊火力分配[J].電光與控制，2019，26（11）：56-59.

[6]李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

作者單位：黃義松、趙德勇，陸軍工程大學石家莊校區；李明雨，陸軍步兵學院石家莊校區