基于改進煙花算法的多導彈目標分配方法*

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

(1 華中科技大學人工智能與自動化學院， 武漢 430074；2 多譜信息處理技術國家級重點實驗室， 武漢 430074)

0 引言

隨著現代戰爭需求的提升，單一導彈對目標進行攔截已經難以滿足作戰要求。在多個目標需要被攔截的情況下，需要多個導彈協同作戰。因此，在多導彈情況下的目標分配問題是作戰過程中需要被解決的重要問題。在分配過程中需要考慮不同導彈對目標攔截的優勢度，同時保證所有目標都被攔截，且不出現浪費火力的現象。已有不少學者對該問題進行了研究。

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

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

1 多導彈目標分配建模

導彈與目標在平面內的相對運動模型如圖1所示：其中M代表導彈，T代表目標，R代表導彈與目標的相對距離，VM為導彈的速度，VT為目標的速度，λ為視線角(LOS)，即導彈與目標的連線與基準線之間的夾角。導彈的導彈偏角為θM,目標的彈道偏角為θT，γ為導彈的速度前置角，即導彈速度方向與視線之間的夾角。

圖1 導彈-目標相對運動示意圖

根據幾何關系可以得到：

γ=θM-λ

(1)

在多導彈進行目標攔截的過程中，需要進行合理的目標分配，獲得最大的作戰效能。同時在分配的過程中應保證所有目標都被攔截，且不存在過多導彈攔截同一目標的火力浪費現象。因此需要根據導彈的物理狀態設計綜合優勢函數，保證分配的結果能使綜合優勢函數達到最大值,達到最優的攔截效能。在綜合優勢函數中主要需要考慮導彈的角度優勢，導彈的距離優勢以及導彈的速度優勢對攔截過程的影響[7-8]。首先假設目標全部在導彈導引頭的檢測范圍內，且多彈之間可以通過通訊網絡相互通訊。

下面對各優勢函數做具體分析：

1)導彈的角度優勢

導彈速度方向沿視線方向的分量為VMcosγ，導彈速度沿視線方向的分量越大，越有利于導彈對目標的攔截，速度前置角γ的取值范圍為[-π,π]，因此γ的絕對值越小，VMcosγ的值越大，當γ=0時，導彈可以獲得最大的角度優勢。根據以上分析定義如下的角度優勢函數：

(2)

隨著|γ|的增大，角度優勢Sγ逐漸減小，符合實際物理意義。

2)導彈的距離優勢

當目標進入導彈的導引頭檢測范圍時，相對距離越小，越有利于攔截。因此定義距離優勢函數：

(3)

其中：a為當前狀態下所有導彈與不同目標間距離的最大值。 設計的距離優勢函數隨著距離的增大而減小。

3)導彈的速度優勢

在一般情況下，提高導彈的速度更有利于對目標的攔截，因此定義速度優勢函數：

(4)

在實際交戰過程中，當導彈的距離優勢與速度優勢較大，但角度優勢較小，即導彈的速度沿視線分量較小時，綜合優勢函數也不會很大[7]。考慮以上特性，采用綜合優勢函數：

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

(5)

綜合優勢函數由兩部分組成，角度優勢與距離優勢的乘積項以及角度優勢與速度優勢的乘積項。其中：M>0為正常數，c1、c2為兩部分的權重因子，滿足條件c1>0,c2>0, 且c1+c2=1 。

設在交戰過程中，有i個導彈執行攔截任務，有j個目標需要被攔截，根據定義的綜合優勢函數可以計算出綜合優勢函數矩陣S為：

式中：si,j表示第i個導彈對第j個目標的綜合優勢函數值。

定義攔截矩陣D為：

式中：di,j的取值范圍為{0,1}，當di,j=1 時代表第i個導彈對第j個目標進行攔截，當di,j=0時代表第i個導彈不對第j個目標進行攔截。為保證每一個導彈對應一個目標，且每一個目標都被攔截到，應滿足條件：

(6)

(7)

為了避免出現過多導彈攔截同一目標造成火力浪費的現象，加入限制條件：

(8)

式中：G為針對同一目標的最大攔截彈數。

根據以上分析，可以將目標分配問題轉化成含有約束的非線性整數規劃問題：

(9)

約束條件為:

(10)

(11)

群體智能算法是求解非線性規劃問題的有效手段，相較于傳統的求解方法，在求解空間較大時具有較大的優勢，同時不需要函數的梯度信息，更有利于實際應用。因此提出一種改進的煙花算法并應用改進的煙花算法求解目標分配問題。

2 改進的煙花算法設計

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

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

(12)

(13)

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

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

(14)

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

(15)

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

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

(16)

最后對所有爆炸產生的火花計算其各自的適應度函數值。

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

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

(17)

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

(18)

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

(19)

步驟5：判斷。若算法已達到最大迭代次數或者最優解滿足所需要求則結束迭代尋優過程。反之，跳至步驟2繼續循環迭代尋優。

整個改進煙花算法的流程如圖2所示。

3 數值仿真

3.1 改進煙花算法性能測試

圖2 改進煙花算法流程圖

1)標準測試函數Beale 函數如式(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] 內是一個多模態函數，存在多個極小值點，全局最小值點為J1(3,0.5)=0。其函數圖像如圖3所示，使用上述3種優化算法搜索函數的最小值，仿真結果如圖4所示。

圖3 Beale函數圖像

根據適應度變化曲線可以看出，使用改進后的煙花算法收斂速度更快，認為當適應度函數的值小于1×10-4時，優化算法已經找到最優解。使用傳統煙花算法找到最優解需要的迭代次數為20次，使用改進的煙花算法需要6次，使用差分進化算法需要28次，改進的煙花算法需要的次數最少，證明了改進煙花算法具有較好的收斂性。

圖4 適應度函數變化曲線

2)標準測試函數Eggholder 函數如式(21)所示。

(21)

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

圖5 Eggholder 函數圖像

圖6 適應度函數變化曲線

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

3.2 使用改進的煙花算法求解目標分配問題

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

表1 導彈與目標位置分布 m

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

圖7 煙花粒子的編碼方式

圖8 綜合優勢函數變化曲線

圖9 目標分配結果

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

4 總結

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