基于改進(jìn)煙花算法的多導(dǎo)彈目標(biāo)分配方法*

安炳合，寇佳禹，王永驥，劉 磊

(1 華中科技大學(xué)人工智能與自動(dòng)化學(xué)院， 武漢 430074；2 多譜信息處理技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室， 武漢 430074)

0 引言

隨著現(xiàn)代戰(zhàn)爭(zhēng)需求的提升，單一導(dǎo)彈對(duì)目標(biāo)進(jìn)行攔截已經(jīng)難以滿足作戰(zhàn)要求。在多個(gè)目標(biāo)需要被攔截的情況下，需要多個(gè)導(dǎo)彈協(xié)同作戰(zhàn)。因此，在多導(dǎo)彈情況下的目標(biāo)分配問題是作戰(zhàn)過程中需要被解決的重要問題。在分配過程中需要考慮不同導(dǎo)彈對(duì)目標(biāo)攔截的優(yōu)勢(shì)度，同時(shí)保證所有目標(biāo)都被攔截，且不出現(xiàn)浪費(fèi)火力的現(xiàn)象。已有不少學(xué)者對(duì)該問題進(jìn)行了研究。

YANG F根據(jù)飽和攻擊戰(zhàn)術(shù)的思想，建立了武器-目標(biāo)分配優(yōu)化模型[1]，將火力分配決策與路徑規(guī)劃過程相結(jié)合，提出了一種在多火力和多約束條件下實(shí)現(xiàn)飽和攻擊的方法。DOU J基于單艦空導(dǎo)彈射擊區(qū)定義方法[2]，提出了編隊(duì)艦空導(dǎo)彈系統(tǒng)的目標(biāo)分配方法。王曉紅基于目標(biāo)的威脅度建立了一種目標(biāo)分配模型[3]，采用匈牙利算法求解了分配問題。群體智能算法作為一種求解函數(shù)最優(yōu)值的有效方法，也被廣泛應(yīng)用在目標(biāo)分配問題中。針對(duì)火力分配問題，李平建立了一種層次分配結(jié)構(gòu)[4]，把武器的作戰(zhàn)效費(fèi)比作為總的性能指標(biāo)，利用遺傳算法對(duì)性能指標(biāo)進(jìn)行了優(yōu)化。周凌超在導(dǎo)彈與目標(biāo)戰(zhàn)術(shù)關(guān)系的基礎(chǔ)上[5]，建立了多目標(biāo)分配的數(shù)學(xué)模型，并提出一種改進(jìn)的模擬退火算法對(duì)目標(biāo)分配問題進(jìn)行求解。黃峰首先改進(jìn)了蟻群算法的搜索機(jī)制[6]，提出一種半約束隨機(jī)蟻群算法，之后根據(jù)動(dòng)態(tài)威脅因素，建立了防御過程的目標(biāo)函數(shù)，利用改進(jìn)的蟻群算法對(duì)多波次目標(biāo)下的最優(yōu)分配問題進(jìn)行了求解。

在已有成果的基礎(chǔ)上，針對(duì)多導(dǎo)彈攔截多目標(biāo)情形下的目標(biāo)分配問題，文中提出一種基于改進(jìn)煙花算法的分配方法。首先綜合考慮導(dǎo)彈的速度傾角，彈-目相對(duì)距離，彈-目速度關(guān)系對(duì)攔截效果的影響，建立了綜合優(yōu)勢(shì)函數(shù)。之后將差分進(jìn)化算法的交叉變異操作引入到煙花算法中，提出一種改進(jìn)的煙花算法。對(duì)同一個(gè)標(biāo)準(zhǔn)函數(shù)，使用改進(jìn)的煙花算法以及其他智能優(yōu)化算法進(jìn)行優(yōu)化，仿真結(jié)果證明了改進(jìn)后的算法具有更快的收斂速度。最后將提出的改進(jìn)煙花算法用于求解目標(biāo)分配問題，試驗(yàn)結(jié)果證明使用改進(jìn)的煙花算法可以在較短的時(shí)間內(nèi)完成目標(biāo)分配任務(wù)。

1 多導(dǎo)彈目標(biāo)分配建模

導(dǎo)彈與目標(biāo)在平面內(nèi)的相對(duì)運(yùn)動(dòng)模型如圖1所示：其中M代表導(dǎo)彈，T代表目標(biāo)，R代表導(dǎo)彈與目標(biāo)的相對(duì)距離，VM為導(dǎo)彈的速度，VT為目標(biāo)的速度，λ為視線角(LOS)，即導(dǎo)彈與目標(biāo)的連線與基準(zhǔn)線之間的夾角。導(dǎo)彈的導(dǎo)彈偏角為θM,目標(biāo)的彈道偏角為θT，γ為導(dǎo)彈的速度前置角，即導(dǎo)彈速度方向與視線之間的夾角。

圖1 導(dǎo)彈-目標(biāo)相對(duì)運(yùn)動(dòng)示意圖

根據(jù)幾何關(guān)系可以得到：

γ=θM-λ

(1)

在多導(dǎo)彈進(jìn)行目標(biāo)攔截的過程中，需要進(jìn)行合理的目標(biāo)分配，獲得最大的作戰(zhàn)效能。同時(shí)在分配的過程中應(yīng)保證所有目標(biāo)都被攔截，且不存在過多導(dǎo)彈攔截同一目標(biāo)的火力浪費(fèi)現(xiàn)象。因此需要根據(jù)導(dǎo)彈的物理狀態(tài)設(shè)計(jì)綜合優(yōu)勢(shì)函數(shù)，保證分配的結(jié)果能使綜合優(yōu)勢(shì)函數(shù)達(dá)到最大值,達(dá)到最優(yōu)的攔截效能。在綜合優(yōu)勢(shì)函數(shù)中主要需要考慮導(dǎo)彈的角度優(yōu)勢(shì)，導(dǎo)彈的距離優(yōu)勢(shì)以及導(dǎo)彈的速度優(yōu)勢(shì)對(duì)攔截過程的影響[7-8]。首先假設(shè)目標(biāo)全部在導(dǎo)彈導(dǎo)引頭的檢測(cè)范圍內(nèi)，且多彈之間可以通過通訊網(wǎng)絡(luò)相互通訊。

下面對(duì)各優(yōu)勢(shì)函數(shù)做具體分析：

1)導(dǎo)彈的角度優(yōu)勢(shì)

導(dǎo)彈速度方向沿視線方向的分量為VMcosγ，導(dǎo)彈速度沿視線方向的分量越大，越有利于導(dǎo)彈對(duì)目標(biāo)的攔截，速度前置角γ的取值范圍為[-π,π]，因此γ的絕對(duì)值越小，VMcosγ的值越大，當(dāng)γ=0時(shí)，導(dǎo)彈可以獲得最大的角度優(yōu)勢(shì)。根據(jù)以上分析定義如下的角度優(yōu)勢(shì)函數(shù)：

(2)

隨著|γ|的增大，角度優(yōu)勢(shì)Sγ逐漸減小，符合實(shí)際物理意義。

2)導(dǎo)彈的距離優(yōu)勢(shì)

當(dāng)目標(biāo)進(jìn)入導(dǎo)彈的導(dǎo)引頭檢測(cè)范圍時(shí)，相對(duì)距離越小，越有利于攔截。因此定義距離優(yōu)勢(shì)函數(shù)：

(3)

其中：a為當(dāng)前狀態(tài)下所有導(dǎo)彈與不同目標(biāo)間距離的最大值。 設(shè)計(jì)的距離優(yōu)勢(shì)函數(shù)隨著距離的增大而減小。

3)導(dǎo)彈的速度優(yōu)勢(shì)

在一般情況下，提高導(dǎo)彈的速度更有利于對(duì)目標(biāo)的攔截，因此定義速度優(yōu)勢(shì)函數(shù)：

(4)

在實(shí)際交戰(zhàn)過程中，當(dāng)導(dǎo)彈的距離優(yōu)勢(shì)與速度優(yōu)勢(shì)較大，但角度優(yōu)勢(shì)較小，即導(dǎo)彈的速度沿視線分量較小時(shí)，綜合優(yōu)勢(shì)函數(shù)也不會(huì)很大[7]?？紤]以上特性，采用綜合優(yōu)勢(shì)函數(shù)：

s=M(c1sγsR+c2sγsV)

(5)

綜合優(yōu)勢(shì)函數(shù)由兩部分組成，角度優(yōu)勢(shì)與距離優(yōu)勢(shì)的乘積項(xiàng)以及角度優(yōu)勢(shì)與速度優(yōu)勢(shì)的乘積項(xiàng)。其中：M>0為正常數(shù)，c1、c2為兩部分的權(quán)重因子，滿足條件c1>0,c2>0, 且c1+c2=1 。

設(shè)在交戰(zhàn)過程中，有i個(gè)導(dǎo)彈執(zhí)行攔截任務(wù)，有j個(gè)目標(biāo)需要被攔截，根據(jù)定義的綜合優(yōu)勢(shì)函數(shù)可以計(jì)算出綜合優(yōu)勢(shì)函數(shù)矩陣S為：

式中：si,j表示第i個(gè)導(dǎo)彈對(duì)第j個(gè)目標(biāo)的綜合優(yōu)勢(shì)函數(shù)值。

定義攔截矩陣D為：

式中：di,j的取值范圍為{0,1}，當(dāng)di,j=1 時(shí)代表第i個(gè)導(dǎo)彈對(duì)第j個(gè)目標(biāo)進(jìn)行攔截，當(dāng)di,j=0時(shí)代表第i個(gè)導(dǎo)彈不對(duì)第j個(gè)目標(biāo)進(jìn)行攔截。為保證每一個(gè)導(dǎo)彈對(duì)應(yīng)一個(gè)目標(biāo)，且每一個(gè)目標(biāo)都被攔截到，應(yīng)滿足條件：

(6)

(7)

為了避免出現(xiàn)過多導(dǎo)彈攔截同一目標(biāo)造成火力浪費(fèi)的現(xiàn)象，加入限制條件：

(8)

式中：G為針對(duì)同一目標(biāo)的最大攔截彈數(shù)。

根據(jù)以上分析，可以將目標(biāo)分配問題轉(zhuǎn)化成含有約束的非線性整數(shù)規(guī)劃問題：

(9)

約束條件為:

(10)

(11)

群體智能算法是求解非線性規(guī)劃問題的有效手段，相較于傳統(tǒng)的求解方法，在求解空間較大時(shí)具有較大的優(yōu)勢(shì)，同時(shí)不需要函數(shù)的梯度信息，更有利于實(shí)際應(yīng)用。因此提出一種改進(jìn)的煙花算法并應(yīng)用改進(jìn)的煙花算法求解目標(biāo)分配問題。

2 改進(jìn)的煙花算法設(shè)計(jì)

煙花算法是學(xué)者TAN Y提出的一種新型群體智能優(yōu)化算法，它啟發(fā)于煙花的爆炸過程[9]，在搜索最優(yōu)解的過程中，以煙花的火花作為問題的可行解，模擬煙花爆炸產(chǎn)生新的火花的方式在舊的可行解的基礎(chǔ)上產(chǎn)生新的可行解，并根據(jù)可行解的適應(yīng)度函數(shù)(即待優(yōu)化函數(shù))進(jìn)行選擇，直到找到問題的最優(yōu)解。但是，傳統(tǒng)的煙花算法中種群內(nèi)部的煙花粒子之間無法進(jìn)行有效的信息交流：為了充分利用煙花粒子中所包含的可行解信息，文中在傳統(tǒng)煙花算法的基礎(chǔ)上引入差分進(jìn)化算法中的交叉、變異操作，加強(qiáng)了粒子間的信息交流，提高算法的全局搜索能力。改進(jìn)后的算法的流程如下：

步驟2：爆炸。以第i個(gè)煙花粒子xi為例進(jìn)行說明：根據(jù)其適應(yīng)度函數(shù)值f(xi)分別按照式(12)、式(13)計(jì)算該煙花爆炸產(chǎn)生的火花數(shù)量Ni以及爆炸半徑Ri。

(12)

(13)

式中：fmax和fmin分別代表所有煙花粒子中適應(yīng)度函數(shù)值的最大值和最小值，ε是一個(gè)很小的常數(shù)，用來避免分子被零除。由式(12)、式(13)可知，當(dāng)煙花粒子的適應(yīng)度越好，即f(xi)越小時(shí)，該煙花粒子的爆炸半徑越小，爆炸數(shù)目越多。采用這樣的爆炸策略有利于在適應(yīng)度較優(yōu)的粒子附近尋找到最優(yōu)解。

為了防止爆炸產(chǎn)生的火花數(shù)目過多或者過少，采用式(14)所示的策略對(duì)Ni進(jìn)行限制。

(14)

假設(shè)煙花的維數(shù)為E，然后在每個(gè)即將爆炸的煙花xi中隨機(jī)抽取一些維度k(1≤k≤rand(0,1)·E)，并采用式(15)所示的策略對(duì)爆炸產(chǎn)生火花的每一維位置進(jìn)行計(jì)算。

(15)

式中：xi,j為煙花xi爆炸產(chǎn)生的第j(1≤j≤Ni)個(gè)火花。根據(jù)式(15)即可計(jì)算所有煙花爆炸產(chǎn)生火花的每一維位置。

假若爆炸產(chǎn)生火花的第k維度的值超出了可行域[xlow,xup]，則采用式(16)所示取模的方法將其映射到可行域內(nèi)。

(16)

最后對(duì)所有爆炸產(chǎn)生的火花計(jì)算其各自的適應(yīng)度函數(shù)值。

步驟3：差分變異。借鑒差分進(jìn)化算法中交叉、變異的操作[10]，產(chǎn)生一定數(shù)量的變異火花。首先在當(dāng)前種群內(nèi)部任意選取4個(gè)不同的個(gè)體Q1、Q2、Q3、Q4以及適應(yīng)度最優(yōu)個(gè)體Qbest，按照式(17)的計(jì)算方式交叉產(chǎn)生第i個(gè)變異火花Ui，F(xiàn)為縮放因子。

Ui=Qbest+F·(Q1-Q2)+F·(Q3-Q4)

(17)

然后在種群內(nèi)部隨機(jī)選取一個(gè)未選擇過的煙花或火花粒子Qi，并按照所設(shè)定的交叉率CR對(duì)粒子Ui中的第j維信息進(jìn)行變異操作，產(chǎn)生式(18)所示的最終變異火花Ui，并計(jì)算其適應(yīng)度函數(shù)值。

(18)

步驟4：選擇。首先選取當(dāng)前種群(包括煙花、子代火花、變異火花)中適應(yīng)度最優(yōu)的個(gè)體參與下一次迭代，然后采用輪盤賭的方式在其余的所有個(gè)體中選取參與下一次迭代的其余個(gè)體。每個(gè)體被選中的概率采用式(19)所示的策略進(jìn)行計(jì)算。

(19)

步驟5：判斷。若算法已達(dá)到最大迭代次數(shù)或者最優(yōu)解滿足所需要求則結(jié)束迭代尋優(yōu)過程。反之，跳至步驟2繼續(xù)循環(huán)迭代尋優(yōu)。

整個(gè)改進(jìn)煙花算法的流程如圖2所示。

3 數(shù)值仿真

3.1 改進(jìn)煙花算法性能測(cè)試

圖2 改進(jìn)煙花算法流程圖

1)標(biāo)準(zhǔn)測(cè)試函數(shù)Beale 函數(shù)如式(20)所示。

J1(x,y)=(1.5-x+xy)2+(2.25-x+xy2)2+

(2.625-x+xy3)2

(20)

J1(x,y)在其定義域x∈[-4.5, 4.5],y∈[-4.5, 4.5] 內(nèi)是一個(gè)多模態(tài)函數(shù)，存在多個(gè)極小值點(diǎn)，全局最小值點(diǎn)為J1(3,0.5)=0。其函數(shù)圖像如圖3所示，使用上述3種優(yōu)化算法搜索函數(shù)的最小值，仿真結(jié)果如圖4所示。

圖3 Beale函數(shù)圖像

根據(jù)適應(yīng)度變化曲線可以看出，使用改進(jìn)后的煙花算法收斂速度更快，認(rèn)為當(dāng)適應(yīng)度函數(shù)的值小于1×10-4時(shí)，優(yōu)化算法已經(jīng)找到最優(yōu)解。使用傳統(tǒng)煙花算法找到最優(yōu)解需要的迭代次數(shù)為20次，使用改進(jìn)的煙花算法需要6次，使用差分進(jìn)化算法需要28次，改進(jìn)的煙花算法需要的次數(shù)最少，證明了改進(jìn)煙花算法具有較好的收斂性。

圖4 適應(yīng)度函數(shù)變化曲線

2)標(biāo)準(zhǔn)測(cè)試函數(shù)Eggholder 函數(shù)如式(21)所示。

(21)

J2(x,y)在其定義域x∈[-512, 512],y∈[-512, 512] 內(nèi)存在眾多極小值點(diǎn)，其函數(shù)圖像如圖5所示，函數(shù)的全局最小值點(diǎn)為J1(512,404.2319)=-959.6407。使用上述3種優(yōu)化算法搜索函數(shù)的最小值，仿真結(jié)果如圖6所示。

圖5 Eggholder 函數(shù)圖像

圖6 適應(yīng)度函數(shù)變化曲線

根據(jù)適應(yīng)度變化曲線可以看出，使用改進(jìn)后的煙花算法，達(dá)到最大迭代次數(shù)后，使用改進(jìn)的煙花算法已經(jīng)找到了全局最優(yōu)解，且收斂速度較快，最終使用傳統(tǒng)煙花算法搜索的結(jié)果為J2(507.8374,398.3313)=-937.489，使用差分進(jìn)化算法搜索的結(jié)果為J2(-465.7,385.7107)=-894.579，使用改進(jìn)煙花算法搜索到的最優(yōu)解為：J2(512,404.2131)=-959.640，由仿真結(jié)果可以看出使用改進(jìn)煙花算法優(yōu)化得到的解更接近真實(shí)最小值點(diǎn)，證明改進(jìn)后的煙花算法具有更好的全局搜索能力。

3.2 使用改進(jìn)的煙花算法求解目標(biāo)分配問題

設(shè)執(zhí)行攔截任務(wù)的導(dǎo)彈共有6個(gè)，需要被攔截的目標(biāo)為4個(gè)，每一代火花數(shù)目選取為10個(gè)，導(dǎo)彈的位置與目標(biāo)位置如表1所示，導(dǎo)彈的速度均為300 m/s,目標(biāo)的速度為150 m/s,導(dǎo)彈的彈道偏角均為0° 。綜合優(yōu)勢(shì)函數(shù)的參數(shù)取值為c1=0.5,c2=0.5,M=5,G=2。根據(jù)當(dāng)前交戰(zhàn)狀態(tài)以及式(5)可以計(jì)算出當(dāng)前綜合優(yōu)勢(shì)函數(shù)矩陣S，之后采用改進(jìn)的煙花算法對(duì)分配方案進(jìn)行優(yōu)化。改進(jìn)煙花算法參數(shù)的設(shè)置與3.1節(jié)相同。

表1 導(dǎo)彈與目標(biāo)位置分布 m

煙花粒子采用如圖7所示的方式編碼：每一個(gè)煙花粒子共6維，第k(k=1～6)維的取值代表第k枚導(dǎo)彈攔截的目標(biāo)序號(hào)，按此方式編碼可滿足一枚導(dǎo)彈只攔截1個(gè)目標(biāo)的約束。在煙花算法的迭代過程中，檢測(cè)粒子是否滿足約束式(11)，如不滿足則該煙花粒子的綜合優(yōu)勢(shì)函數(shù)直接取0值。優(yōu)化過程適應(yīng)度函數(shù)變化曲線如圖8所示，最終目標(biāo)分配結(jié)果如圖9所示。

圖7 煙花粒子的編碼方式

圖8 綜合優(yōu)勢(shì)函數(shù)變化曲線

圖9 目標(biāo)分配結(jié)果

由仿真結(jié)果可以看出：經(jīng)過5次迭代后，改進(jìn)的煙花算法找到了最優(yōu)的目標(biāo)分配方案，找到的最優(yōu)分配方案與使用窮舉法計(jì)算出的最優(yōu)方案相同，即導(dǎo)彈1、導(dǎo)彈2攔截目標(biāo)1，導(dǎo)彈3攔截目標(biāo)2，導(dǎo)彈4、導(dǎo)彈5攔截目標(biāo)3，導(dǎo)彈6攔截目標(biāo)4，實(shí)現(xiàn)了最大的優(yōu)勢(shì)函數(shù)，且分配結(jié)果在幾何關(guān)系上適合各個(gè)導(dǎo)彈的攔截，并滿足目標(biāo)分配過程中的約束條件。找到最優(yōu)方案需要的時(shí)間小于0.4 s，滿足了快速目標(biāo)分配的要求。仿真結(jié)果證明了文中提出方法的有效性與優(yōu)越性。

4 總結(jié)

對(duì)導(dǎo)彈攔截情況下的目標(biāo)分配問題進(jìn)行了一定探索性研究，提出了一種基于改進(jìn)煙花算法的目標(biāo)分配方法。首先分析了交戰(zhàn)情況下的彈-目?jī)?yōu)勢(shì)關(guān)系，并建立了基于綜合優(yōu)勢(shì)函數(shù)的目標(biāo)分配數(shù)學(xué)模型。為了求解目標(biāo)分配模型，將差分進(jìn)化算法中的交叉變異操作引入到煙花算法中，提出了一種改進(jìn)的煙花算法。在數(shù)值仿真中，首先通過標(biāo)準(zhǔn)函數(shù)的測(cè)試證明了改進(jìn)煙花算法具有較好的收斂性與全局搜索能力，之后將改進(jìn)的煙花算法用于求解目標(biāo)分配問題，仿真結(jié)果證明使用提出的方法可以快速地找到最優(yōu)分配方法，驗(yàn)證了算法的有效性。