基于Memetic算法的超視距協(xié)同空戰(zhàn)火力分配

顏 驥 李相民 劉立佳

(海軍航空工程學(xué)院 兵器科學(xué)與技術(shù)系，煙臺264001)

張鳳霞

(中航工業(yè)洛陽電光設(shè)備研究所 光電控制技術(shù)重點實驗室，洛陽471009)

多機編隊超視距協(xié)同作戰(zhàn)是現(xiàn)代空戰(zhàn)的主要形式，若不涉及作戰(zhàn)戰(zhàn)術(shù)，協(xié)同空戰(zhàn)決策的核心和熱點問題為交戰(zhàn)階段的協(xié)同多目標分配，目的是確定多戰(zhàn)機在一個決策時間片或一個時間序列中的任務(wù)集，使戰(zhàn)機間形成協(xié)同，以最小的代價達到最優(yōu)的作戰(zhàn)效能［1］.對這類具有約束條件的組合優(yōu)化問題，解決方法一般先構(gòu)建協(xié)同多目標分配模型，然后根據(jù)約束條件選擇適當?shù)姆椒▽δＰ瓦M行優(yōu)化求解，得出目標分配方案用于決策或輔助決策.超視距協(xié)同空戰(zhàn)中的目標分配一般指導(dǎo)彈目標分配，故本文稱其火力分配.

目前大部分火力分配模型都是基于單純的求毀傷概率越大越好或剩余威脅越小越好的最優(yōu)準則［1-10］，這種一次性分配的靜態(tài)模型在火力資源充足、目標數(shù)目相對較少的情況下，會導(dǎo)致武器火力資源的浪費，當有后續(xù)敵機目標到來時，無法繼續(xù)為其提供火力.文獻［11］提出帶毀傷概率門限的火力分配模型，在取得最大的對目標毀傷概率均值的同時，盡量少地消耗火力資源，更符合現(xiàn)代空戰(zhàn)多階段攻防對抗.

求解火力分配的算法有多種，從結(jié)構(gòu)上看可分為集中式算法和分布式算法.諸如粒子群算法、遺傳算法等［2-3］仿生算法，差分進化算法等［4-5］啟發(fā)式算法以及這些算法的改進與混合［1，6-7］的集中式算法，一般應(yīng)用于數(shù)據(jù)鏈組網(wǎng)/退網(wǎng)時間較長且戰(zhàn)機計算能力和智能性較差的場景，戰(zhàn)機之間信息共享很少，由長機集中負責(zé)編隊的協(xié)同多目標分配;分布式方法源自無人機和無人作戰(zhàn)系統(tǒng)的拍賣算法［8-10］和完全分布式的群集智能算法［1］，涉及目標分配的拍賣算法［8-10］一般應(yīng)用于有指揮中心的分布式協(xié)同場景，戰(zhàn)機間信息交互頻繁，且多針對一次性分配的靜態(tài)模型;無指揮中心協(xié)同模式下的拍賣算法在無人系統(tǒng)間通信拓撲時變及時延時可獲得較優(yōu)的無沖突的任務(wù)分配方案，但其屬于一對一［12］或一對多［13］的目標分配.文獻［8］提出的組合拍賣算法雖解決了戰(zhàn)機間不能共享投標而無法協(xié)同攻擊的問題(彈-目分配的多對一問題)，但戰(zhàn)機在僅能與部分其他武器平臺進行信息共享時分配結(jié)果不能保證.文獻［14］提出了一種魯棒的分布式任務(wù)分配方法，無人機群在通信網(wǎng)絡(luò)拓撲變化和態(tài)勢信息不完全情況下，通過信息一致和計劃生成兩階段可得出滿意的協(xié)同任務(wù)分配方案.類似文獻［12-13］，各無人系統(tǒng)對環(huán)境的態(tài)勢感知并非完全一致，不同之處在于，文獻［14］每架無人機都基于自身掌握的不完全態(tài)勢信息計算編隊的協(xié)同方案，最后通過沖突消除階段來獲得滿意解.

本文基于文獻［11］的火力分配模型，采用文獻［14］的任務(wù)協(xié)同分配框架，討論多戰(zhàn)機編隊協(xié)同火力分配問題.限于篇幅，本文僅對協(xié)同火力分配展開研究，采用Memetic算法來解決該問題，以提高算法對全局最優(yōu)解的搜索效率.信息一致性算法和沖突消除方法可參考文獻［12-14］，本文不再贅述.

1 協(xié)同空戰(zhàn)火力分配數(shù)學(xué)模型

假設(shè)在某次多機協(xié)同攻擊多目標的超視距空戰(zhàn)中，由 r架飛機組成的編隊 R={R1，R2，…，Rr}，掛載了不同類型的導(dǎo)彈，所有導(dǎo)彈的總數(shù)量為 m，每枚導(dǎo)彈的編號為 Mi(i=1，2，…，m)，需要攻擊的敵機目標有n個，每個目標的編號為Tj(j=1，2，…，n).記 Pj為所分配火力對第 j個目標的聯(lián)合毀傷概率，則

式中，pij為第i枚導(dǎo)彈對第j個目標的毀傷概率;xij為決策變量，若分配第i枚導(dǎo)彈攻擊第j個目標，則 xij=1，否則 xij=0.

一般基于求毀傷概率越大越好的一次性分配模型為

式中Wj為第j個目標的威脅權(quán)重.

為避免火力資源相對充足、目標數(shù)相對較少情況下應(yīng)用上述模型造成的火力資源浪費，本文采用帶毀傷概率門限的火力分配模型［11］為

式中，Pdj為第j個目標的預(yù)設(shè)毀傷概率門限，其值可根據(jù)目標戰(zhàn)場態(tài)勢由指揮員確定，或由指揮系統(tǒng)確定為Pj的均值;約束Pj≥Pdj表示對每個目標的毀傷概率應(yīng)大于其預(yù)設(shè)毀傷概率門限，若一個火力分配方案中，對某個目標的毀傷概率低于毀傷概率門限，則該分配方案無效;約束∑xij≤1表示一枚導(dǎo)彈最多只能攻擊一個目標.

在符合約束條件下，該模型將毀傷概率和資源消耗問題綜合考慮，在選擇盡量少的導(dǎo)彈數(shù)目前提下，選取對目標毀傷概率最大的導(dǎo)彈組合，達到既節(jié)省資源又使毀傷概率盡量大的效果.

上述模型為非線性0-1整數(shù)規(guī)劃問題，目標函數(shù)和約束條件均為決策變量的非線性函數(shù).為此，本文先將上述問題化為一個無約束問題，然后采用Memetic算法求解該火力分配問題.

無約束問題的轉(zhuǎn)化采用罰函數(shù)法，令

則原問題化為

式中M為罰因子，設(shè)M=100.

當火力分配方案某目標的毀傷概率低于預(yù)設(shè)門限時，式(5)的后半部分為負，以式(5)為適應(yīng)度函數(shù)的值劣于符合約束條件方案的值，在種群的進化中容易被淘汰.

2 解火力分配問題的Memetic算法

Memetic算法［15］屬于文化進化算法，是一種混合算法框架.其充分吸收全局搜索算法和局部搜索算法的優(yōu)點，不僅具有很強的全局尋優(yōu)能力，同時，對每次全局算法產(chǎn)生的新種群(部分或全部)進行局部搜索，通過優(yōu)化種群分布，及早剔除不良個體，進而減少迭代次數(shù)，加快算法的求解速度，這樣既保證了較高的收斂性能，又能獲得高質(zhì)量解，從而使Memetic算法的搜索效率在某些問題領(lǐng)域比傳統(tǒng)的進化算法要快幾個數(shù)量級.

2.1 Memetic算法流程

本文解決火力分配問題的Memetic算法是以離散粒子群算法為全局搜索策略，以貪婪算法為局部搜索策略的混合優(yōu)化算法.在一次迭代中，算法讓每個個體(粒子)執(zhí)行全局進化操作(速度、位置更新)后，再進行局部搜索，直至滿足優(yōu)化準則而終止.具體算法流程如圖1所示，將圖中粒子群操作替換為遺傳操作則為基于遺傳算法框架的Memetic算法.

2.2 全局搜索DPSO算法

針對非線性0-1整數(shù)規(guī)劃的火力分配問題，采用連續(xù)空間離散粒子群優(yōu)化(DPSO，Discrete Particle Swarm Optimization)算法作為Memetic算法的全局搜索策略，這樣保留了連續(xù)PSO算法的運算模式，從而可以充分利用其矢量計算簡單、消耗時間短的優(yōu)勢.

采用一種基于實數(shù)的編碼方式，用粒子位置代表一種導(dǎo)彈-目標分配的候選方案，粒子位置矢量維數(shù)分量(維數(shù)m與導(dǎo)彈數(shù)相同)代表導(dǎo)彈，維數(shù)分量對應(yīng)的整數(shù)代表該導(dǎo)彈分配的目標.設(shè)粒子的總數(shù)為R，則第r個粒子的位置矢量為Xr=［Xr1，Xr2，…，Xrm］，分量 Xri(i=1，2，…，m)為 0 ～n之間的整數(shù).粒子速度矢量為Vr=［vr1，vr2，…，vrm］，分量 vri(i=1，2，…，m)為 -(n-1)～ (n-1)之間的整數(shù).

圖1 Memetic算法程序流程Fig.1 Flow chart of Memetic algorithm

為將整數(shù)編碼轉(zhuǎn)化為適合適應(yīng)值計算的0-1整數(shù)規(guī)劃的決策變量形式 x=［xij］m×n(i=1，2，…，m;j=1，2，…，n)，采用轉(zhuǎn)化公式:

第r個粒子在i維子空間的飛行速度和位置更新公式及參數(shù)可以參見文獻［11］，此處不再贅述.

2.3 局部搜索貪婪算法

針對本文的火力分配問題，為取得個體鄰域內(nèi)目標函數(shù)的局部最優(yōu)解，結(jié)合目標函數(shù)(5)的結(jié)構(gòu)特點，提出“先刪后補”的串行兩階段貪婪策略.

1)分配冗余刪除階段.

這一階段對一種導(dǎo)彈-目標分配候選方案Xr，檢查所有符合殺傷概率門限約束的目標所分配的導(dǎo)彈數(shù)目，若分配給該目標的導(dǎo)彈數(shù)大于1，則嘗試刪除分配給該目標中對該目標單發(fā)毀傷概率小的導(dǎo)彈，若刪除該導(dǎo)彈分配后，剩余導(dǎo)彈對目標的聯(lián)合毀傷概率仍大于或等于對目標的毀傷概率門限，則確認刪除該導(dǎo)彈分配，否則保留該分配.此階段通過對冗余導(dǎo)彈分配的刪除，提高對目標整個毀傷概率的均值，并選擇Pj大的導(dǎo)彈組合，從而使目標函數(shù)(5)的前半部分盡可能大.

2)分配不足補充階段.

本階段對上一階段優(yōu)化后的分配方案，首先，分別檢查方案中未分配目標的導(dǎo)彈集M'i和聯(lián)合殺傷概率低于預(yù)設(shè)殺傷概率門限的目標集T'j;然后，對T'j中的目標按其Pfj值大小由低到高排序(若目標j未分配導(dǎo)彈，則Pfj=0-Pdj)，并將M'i中對目標j殺傷概率最大的導(dǎo)彈i按序依次分配給目標.此階段，有未分配目標導(dǎo)彈的前提下，聯(lián)合毀傷概率小于預(yù)設(shè)毀傷概率門限的目標可獲得一次補充分配的機會，Pfj值越小，其選擇剩余導(dǎo)彈的優(yōu)先級越高.過程中每個目標只能補充分配一枚導(dǎo)彈，分配L次后結(jié)束.

輸入:導(dǎo)彈-目標分配候選方案Xr

輸出:優(yōu)化的導(dǎo)彈-目標分配候選方案Xr

1)分配冗余刪除階段.

3 算例仿真驗證及分析

為驗證本文提出的Memetic算法求解該火力分配問題的可行性和有效性，進行了仿真實驗.

設(shè)我方戰(zhàn)機編隊在超視距條件下與敵機編隊進行空戰(zhàn).我方戰(zhàn)機架數(shù)為4架，每架戰(zhàn)機均掛載4枚導(dǎo)彈，協(xié)同攻擊區(qū)內(nèi)發(fā)現(xiàn)10個敵機目標.

仿真中，各目標預(yù)設(shè)毀傷概率門限Pdj均為0.90.各目標的威脅權(quán)重矩陣為

各導(dǎo)彈對各目標的毀傷概率矩陣［11］為

采用本文的Memetic算法，包括分別以離散粒子群算法和以遺傳算法為全局搜索策略，以本文設(shè)計的貪婪策略為局部搜索策略的兩種混合優(yōu)化算法(分別簡稱為MGA和MPA)、DPSO算法，模擬退火-離散粒子群(SA-DPSO)算法、遺傳算法和模擬退火-遺傳(SA-GA)算法對該火力分配問題進行優(yōu)化求解.其中，DPSO算法和SA-DPSO算法的參數(shù)設(shè)置同文獻［11］;本文DPSO算法中，設(shè)置慣性權(quán)重為w=0.8.

本文采用的GA中，使用單點交叉運算和基本位變異運算(文中隨機取3個基因位)，采用確定性的選擇策略，在父代和子代種群中選擇目標函數(shù)值按從大到小排序的前R個個體進化到下一代.交叉概率 pc=0.9，變異概率 pm=0.1.SA-GA的參數(shù)設(shè)置同文獻［6］.

導(dǎo)彈-目標的最優(yōu)分配方案見表1，表中“0”代表未攻擊.由表1可看出，火力分配模型僅用13枚導(dǎo)彈便達到指標要求，大大節(jié)省了火力資源，從而為打擊后續(xù)來襲目標做準備.

表1 最優(yōu)攻擊分配Table 1 Optimal attacks allocation

文獻［15］對Memetic算法的收斂性進行了理論上的證明，本文對上述6種算法分別進行100次仿真實驗，以證明Memetic算法解決該火力分配問題的有效性.種群規(guī)模均取為60個，迭代次數(shù)均為120代.為便于比較，分別將 GA，SA-GA和基于GA的Memetic算法分為一組，將DPSO，SA-DPSO和基于DPSO的Memetic算法分為一組分別比較，然后再將這兩組做比較，見圖2、圖3.

通過比較可知，Memetic算法能夠迅速收斂到全局最優(yōu)解，100次中，算法每次收斂到最優(yōu)解的概率MGA為50%，MPA為97%;SA-DPSO算法和SA-GA算法能夠收斂到全局最優(yōu)，但相對Memetic算法較慢，且收斂到最優(yōu)解的概率都低于20%;基本DPSO算法和GA不僅收斂速度慢，且在迭代過程中常常陷入局部最優(yōu).6種算法的綜合比較見表2.可見，本文提出的MPA算法能有效提高對全局最優(yōu)解的尋優(yōu)效率.

圖2 圍繞GA的3種算法最優(yōu)迭代過程比較Fig.2 Comparison of iterative process of three algorithms based on GA

圖3 圍繞DPSO的3種算法最優(yōu)迭代過程比較Fig.3 Comparison of iterative process of three algorithms based on DPSO

表2 6種算法綜合比較Table 2 Comprehensive comparison of six algorithms

4 結(jié)論

本文研究了火力資源相對充足條件下的多機編隊超視距協(xié)同空戰(zhàn)火力分配問題:

1)研究了一種滿足毀傷概率門限的火力分配模型，該模型保證火力分配方案使各目標達到預(yù)設(shè)毀傷概率門限的前提下，實現(xiàn)對目標的平均毀傷概率最大且所用武器火力單元盡可能少，從而保存火力，便于打擊后續(xù)目標;

2)提出求解該火力分配模型的Memetic算法，針對模型特點設(shè)計了基于離散粒子群算法的全局搜索策略和先刪后補的串行兩階段局部貪婪搜索策略;

3)仿真結(jié)果表明，火力分配模型可有效節(jié)約火力資源，本文的Memetic算法在解決該問題時是有效且快速的.

References)

［1］劉波，陳哨東，賀建良.基于概率群集的多戰(zhàn)機協(xié)同空戰(zhàn)決策算法［J］.上海交通大學(xué)學(xué)報，2011，45(2):257-261 Liu Bo，Chen Shaodong，He Jianliang.Air combat decision-making for multi-fighter coordinated attack based on probability collectives［J］.Journal of Shanghai Jiaotong University，2011，45(2):257-261(in Chinese)

［2］肖冰松，方洋旺，許蘊山，等.編隊內(nèi)協(xié)同超視距空戰(zhàn)目標分配模型研究［J］.系統(tǒng)工程與電子技術(shù)，2010，32(7):1476-1479 Xiao Bingsong，F(xiàn)ang Yangwang，Xu Yunshan，et al.Research on coordinated formation target assignment model for beyond visual range air combats［J］.Systems Engineering and Electronic，2010，32(7):1476-1479(in Chinese)

［3］ Lee Z J，Su S F，Lee C Y.Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics［J］.IEEE Transactions on Systems，Man，and Cybernetics—Part B:Cybernetics，2003，33(1):113-121

［4］ Song W D，Zhao C W，Huo J X.Improved differential evolution algorithm for solving WTA problem［J］.Energy Procedia，2011(11):1348-1353

［5］ Madni A M，Andrecut M.Efficient heuristic approach to the weapon-target assignment problem［J］.Journal of Aerospace Computing，Information，and Communication，2009，6(6):405-414

［6］羅德林，王彪，龔華軍，等.基于SAGA的協(xié)同多目標攻擊決策［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2007，39(7):1154-1159 Luo Delin，Wang Biao，Gong Huajun，et al.Air combat decision making for cooperative multiple target attack based on SAGA［J］.Journal of Harbin Institute of Technology，2007，39(7):1154-1159(in Chinese)

［7］楊飛，王青，侯硯澤.基于整數(shù)域改進粒子群優(yōu)化算法的多平臺武器目標分配［J］.兵工學(xué)報，2011，32(7):906-912 Yang Fei，Wang Qing，Hou Yanze.Weapon-target assignment in multi-launcher system based on improved integer field particle swarm optimization algorithm［J］.Acta Armamentarii，2011，32(7):906-912(in Chinese)

［8］劉波，張選平，王瑞，等.基于組合拍賣的協(xié)同多目標攻擊空戰(zhàn)決策算法［J］.航空學(xué)報，2010，31(7):1433-1444 Liu Bo，Zhang Xuanping，Wang Rui，et al.Air combat decision making for coordinated multiple target attack using combinatorial auction［J］.Acta Aeronautica et Astronautica Sinica，2010，31(7):1433-1444(in Chinese)

［9］張杰勇，姚佩陽，王欣，等.基于時間約束的多平臺協(xié)同目標分配方法［J］.系統(tǒng)工程與電子技術(shù)，2011，33(6):1287-1292 Zhang Jieyong，Yao Peiyang，Wang Xin，et al.Multiple platforms coordinated target assignment method based on time restraint［J］.Systems Engineering and Electronic，2011，33(6):1287-1292(in Chinese)

［10］萬路軍，姚佩陽，孫鵬.有人/無人作戰(zhàn)智能體分布式任務(wù)分配方法［J］.系統(tǒng)工程與電子技術(shù)，2013，35(2):310-316 Wan Lujun，Yao Peiyang，Sun Peng.Distributed task allocation method of manned/unmanned combat Agents［J］.Systems Engineering and Electronics，2013，35(2):310-316(in Chinese)

［11］李儼，董玉娜.基于SA-DPSO混合優(yōu)化算法的協(xié)同空戰(zhàn)火力分配［J］.航空學(xué)報，2010，31(3):626-631 Li Yan，Dong Yuna.Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat［J］.Acta Aeronautica et Astronautica Sinica，2010，31(3):626-631(in Chinese)

［12］ Zavlanos M M，Spesivtsev L，Pappas G J.A distributed auction algorithm for the assignment problem［C］//Proc of the 47th IEEE Conf on Decision and Control.Piscataway，NJ:IEEE，2008:1212-1217

［13］ Choi H L，Brunet L，Jonathan P H.Consensus-based decentralized auctions for robust task allocation ［J］.IEEE Transactions on Robotics，2009，25(4):912-926

［14］ Mehdi A，Jonathan P H.Robust decentralized task assignment for cooperative UAVs［R］.AIAA 2006-6454，2006

［15］段海濱，張祥銀，徐春芳.仿生智能計算［M］.北京:科學(xué)出版社，2011:130-149 Duan Haibin，Zhang Xiangyin，Xu Chunfang.Bio-inspired computing［M］.Beijing:Science Press，2011:130-149(in Chinese)