顏 驥 李相民 劉立佳

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

張鳳霞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

則原問(wèn)題化為

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

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

2 解火力分配問(wèn)題的Memetic算法

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

2.1 Memetic算法流程

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

2.2 全局搜索DPSO算法

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

采用一種基于實(shí)數(shù)的編碼方式，用粒子位置代表一種導(dǎo)彈-目標(biāo)分配的候選方案，粒子位置矢量維數(shù)分量(維數(shù)m與導(dǎo)彈數(shù)相同)代表導(dǎo)彈，維數(shù)分量對(duì)應(yīng)的整數(shù)代表該導(dǎo)彈分配的目標(biāo).設(shè)粒子的總數(shù)為R，則第r個(gè)粒子的位置矢量為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)值計(jì)算的0-1整數(shù)規(guī)劃的決策變量形式 x=［xij］m×n(i=1，2，…，m;j=1，2，…，n)，采用轉(zhuǎn)化公式:

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

2.3 局部搜索貪婪算法

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

1)分配冗余刪除階段.

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

2)分配不足補(bǔ)充階段.

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

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

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

1)分配冗余刪除階段.

3 算例仿真驗(yàn)證及分析

為驗(yàn)證本文提出的Memetic算法求解該火力分配問(wèn)題的可行性和有效性，進(jìn)行了仿真實(shí)驗(yàn).

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

References)

［1］劉波，陳哨東，賀建良.基于概率群集的多戰(zhàn)機(jī)協(xié)同空戰(zhàn)決策算法［J］.上海交通大學(xué)學(xué)報(bào)，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］肖冰松，方洋旺，許蘊(yùn)山，等.編隊(duì)內(nèi)協(xié)同超視距空戰(zhàn)目標(biāo)分配模型研究［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é)同多目標(biāo)攻擊決策［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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ù)域改進(jìn)粒子群優(yōu)化算法的多平臺(tái)武器目標(biāo)分配［J］.兵工學(xué)報(bào)，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é)同多目標(biāo)攻擊空戰(zhàn)決策算法［J］.航空學(xué)報(bào)，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］張杰勇，姚佩陽(yáng)，王欣，等.基于時(shí)間約束的多平臺(tái)協(xié)同目標(biāo)分配方法［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］萬(wàn)路軍，姚佩陽(yáng)，孫鵬.有人/無(wú)人作戰(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é)報(bào)，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］段海濱，張祥銀，徐春芳.仿生智能計(jì)算［M］.北京:科學(xué)出版社，2011:130-149 Duan Haibin，Zhang Xiangyin，Xu Chunfang.Bio-inspired computing［M］.Beijing:Science Press，2011:130-149(in Chinese)