反導攔截中的目標分配問題研究

劉韜，廖承城

（四川大學計算機學院，成都610065）

0 引言

攔截分導式彈道導彈的目標分配問題，本質上是一類多約束優化問題，也是一類武器-目標分配（Weapon-Target Assignment，WTA）問題。分導式彈道導彈再入大氣層，完成彈頭分離后，將形成多個獨立的威脅目標。如何通過多枚攔截導彈攔截這些目標，WTA 問題是多導彈協同攔截中的重要部分。在任務過程中，針對我方多個裝備同類型武器的作戰單元與多個來襲威脅目標，如何對我方具有相同殺傷力的武器進行快速合理地分配，形成反應速度最快、攔截效率最大的反導攔截方案，將至關重要。

當前，關于WTA 的研究比較多，具體的目標分配方法包括：基于貪婪算法和枚舉求最優解的目標分配方法[1]、基于匈牙利算法求解目標分配問題的方法[2]、基于改進遺傳算法來求解目標分配的方法[3]、基于免疫蟻群算法求解目標分配的方法[4]、基于模糊多目標規劃的目標分配方法[5]、基于改進粒子群算法的目標分配方法[6]。

本文主要根據現有研究成果，結合反導攔截作戰特點，提出一種基于改進遺傳算法的任務分配方案，以提高任務整體效能。

1 問題描述

本文主要討論反導攔截過程中的攔截彈目標分配問題。具體問題可描述為，分導式彈道導彈再入大氣層，完成彈頭分導后，形成多個獨立的威脅目標，向我方重要目標飛去，我方多個反導單元準備發射多枚攔截彈對來襲目標進行攔截。關于如何將多枚攔截彈分配給多個目標就是本文討論的重點，而評判目標分配問題的標準就是發射的攔截彈能夠最快且同時到達目標。

2 任務分配模型

2.1 彈頭目標假設

本文主要討論多枚攔截彈的目標分配問題，側重于研究優化問題，因此，我們對目標的界定可以相對簡化，認為所有目標均為一致的，存在差異的只是當前所處的位置。

2.2 攔截彈假設

對于攔截導彈，影響其攔截效率的因素較多，型號、速度、距離、角度等都有影響。考慮到本文的實際，對攔截彈也進行簡化處理。假設所有攔截導彈的型號一致，分別部署在不同的火力單元。所以，對攔截導彈來說，唯一的區別在于其所處的火力單位到目標的距離，進而影響其到達目標的時間。

2.3 模型建立

假設有n 個來襲彈道導彈目標T1,T2,…,Tn，已再入大氣層向我方區域飛來。在本區域配備有m 個導彈攔截火力單元W1,W2,…,Wm，其中，每個火力單元標配攔截導彈k 枚。為了充分發揮攔截武器性能，本文根據攔截目標的特點，對目標分配問題考慮以下約束條件：

（1）對所有的來襲目標都要分配一枚攔截導彈進行攔截；

（2）每一枚攔截導彈只能攔截一個來襲目標；

（3）單個火力單元中的導彈數量k 要小于來襲目標數量，全部火力單元中的導彈數量k·m 要大于來襲目標數量；

（4）為了避免來襲目標察覺攔截后，進行主動變軌，增加攔截難度，要求所有攔截導彈同時命中來襲目標；

（5）在實現上述約束條件的基礎上，要求以最快的時間完成導彈目標攔截。

令火力單元到彈道導彈的距離為smn，矩陣表示為：

令火力單元是否攔截彈道導彈的決策變量xmn為：

則目標分配的決策矩陣為：

受限于每個火力單元的導彈數量，約束條件：

確定適應度函數時，要充分考慮目標分配問題的限制條件，在本文中，就是所有攔截彈最快且同時攔截目標。為了同時到達目標，在不改變導彈飛行參數的情況下，我們以最晚到達的導彈為準，前面的導彈依次晚于某個時點發射即可。故適應度函數的選擇就是在每個可行解中選出最晚到達的目標時間，并與其他解進行比較，確定最優解。故適應度函數可表示為：

3 改進遺傳算法設計

3.1 基因編碼設計

染色體是由基因組成的串，一個染色體就是一次選擇結果，也就是一個目標分配的決策矩陣。考慮到本文染色體的特殊性，在進行編碼前可以將問題換一個表述方式，即攔截第i 個目標的攔截彈來自第j 個火力單元。當火力單元數量不多（m ＜10）時，可以比較方便地采用十進制的方式對染色體進行編碼，將染色體表示為[ ]a1,a2,…,ai,…,an，代表對n 個來襲目標依次分配的結果，其中ai表示攔截第i 個目標的攔截彈來自火力單元ai。此外，當m ＞10，使用2n 個十進制數組成的基因串表示即可。

關于將染色體再轉換為決策矩陣的問題，即解碼過程比較簡單，以ai為例，只需要將初始矩陣的第ai行i 列的元素設為1，以此類推，將n 個矩陣元素設為1后，剩下的矩陣元素設為0，即可。

在編碼過程中，要注意約束條件的影響，即每個火力單元的攔截彈數量k，即每個火力單元對應數字在一個基因串中的出現次數不能超過k 次。

3.2 初始種群的選取及適應度計算

在生成初始種群時，一方面以目標到火力單元的距離屬性作為啟發式信息，例如，若某一火力單元到目標的距離較之其他火力單元明顯小一些，則優先考慮選擇該火力單元。通過這種啟發式的方式可以產生一部分初始種群，這部分種群的適應度較好。另一方面，還需要保持初始種群的多樣性，本文考慮通過Tent 映射再生成一部分種群[7]。結合這兩種方式生成的初始種群將同時具有多樣性和高適應性，這將有利于后續算法的收斂，提高運算效率。

Tent 映射產生混沌序列的表達式是：

式中，z(t)∈[0 ,1] 。運算時，在[0 ,1] 的區間內生成1個的隨機數，按照（6）式進行混沌變換，依次循環，直達在[0 ,1] 的區間內生成n 個混沌變量。再將混沌變量映射到變量空間，即乘以m 后，向上取整，完成一個染色體的生成，重復數次完成另一部分初始種群的生成。

由于每個火力單元對應的數字出現頻率不能超過k，故需要采用計數器的方式，在生成初始種群過程中進行控制，對不滿足條件的基因重新生成。

生成初始種群后，按照3.1 小節中所述的方法將染色體轉化為決策矩陣的形式，并依照式（5）的適應度計算方法，計算初始種群個體的適應度。

3.3 選擇操作

輪盤賭選擇算法作為選擇操作的常用方法，優勢明顯，有利于適應度高的個體被選中。但在個體適應度很相近時，存在缺陷，有導致種群進化停滯的可能。本文結合實際問題，對選擇操作進行了改進，首先將種群個體按照適應度的大小進行排序[8]，借鑒精英保留原則的思想，將適應度最高的個體直接復制到子代中。在選擇過程中，直接選擇適應度位于優勢位置前1/3 的個體，再對剩余需求在種群中進行隨機選擇。具體方法是：隨機抽取兩個個體，將其適應度進行比較，將適應度較高者選擇出來，再重復抽取兩個個體進行比較，直至完成選擇量要求為止。這種選擇方式將有助于提高選出種群的適應度，在選擇出適應度較高個體的同時，兼顧種群的多樣性，提高遺傳算法的效率和實用性。

3.4 交叉和變異操作

交叉操作是基因進化的基礎，進行基因重組，生成相對父代波動較大的基因，故交叉概率pc主要控制種群新群體產生的速度。若pc取值太大，會破壞個體的優良遺傳特征；若pc取值太小，可能導致最優解出現過早的收斂。變異操作是基因進化的補充，是保持遺傳多樣性的重要途徑，是對交叉過程可能丟失的某種遺傳基因進行修復和補充，可有效避免遺傳算法過快收斂到局部最優解[9]。變異概率pm主要控制基因擾動，若pm取值過大，會使算法變成隨機搜索算法；若pm取值過小，可避免某種單個基因的丟失。

本文引入一種改進的自適應調節思想，使得交叉概率pc和遺傳概率pm，能夠根據進化進度調整大小[10]。目的是使得交叉概率pc在遺傳算法初期較大，后期變得較小；變異概率pm在遺傳算法初期較小，后期變得較大。概率pc和pm表達式為：

式中，pc1和pm1分別是交叉概率和變異概率的初始值，i 是當前進化代數，n 是最高進化次數，count 是累積最優解不改變的次數。當count 為0 的時候，pc為pc1，pm為pm1/2。交叉概率pc大，變異概率pm小。當count 變大時，交叉概率pc小，變異概率pm大。

交叉操作，本文根據交叉概率pc，選取兩個父代個體x=( x1,x2,…xm)∈[ L,U ]，y=( y1,y2,…yn)∈[ L,U ]，進行兩點交叉，交叉點為i1和i2，交叉后的兩個子代分別為：

其中：

式 中，[ L,U ]={(x1,x2,…,xm)||li?xi?ui,i=1,2,…,

表示可行解空間，a 和b 是[0,1]區間的隨機數。完成交叉操作后判斷是否滿足約束條件，如不滿足，則恢復到交叉前的數據，重新進行交叉操作，直到滿足條件為止。采用這種混合交叉算子的交叉方式獲得子代個體，可在進化前期，加快收斂速度。

變異操作，本文根據交叉概率pm，對交叉后的子代，隨機選擇某一位，改變其數值，并判斷是否滿足約束條件，如不滿足，則再次變換數值，產生一個新個體。

3.5 算法描述

Step1 設置初始Gen、Pc1、Pm1。

Step2 根據啟發信息及Tent 映射生成初始種群。

Step3 計算種群適應度值，并按適應度值大小進行排序。

Step4 執行精英保留操作，根據適應度值，進行選擇操作。

Step5 更新交叉概率Pc、變異概率Pm的值

Step6 根據概率Pc、Pm，進行交叉操作、變異操作，產生新的種群。

Step7 判斷是否滿足終止條件，若滿足，輸出最優解；不滿足，則Gen=Gen+1，跳轉至Step3 繼續執行。

4 仿真實驗

本文使用MATLAB 工具進行仿真實驗，實驗數據為8 個來襲分導式彈頭目標，5 個攔截火力單元，每個火力單元標配攔截導彈3 枚，各火力單元到各導彈的距離如表1 所示。

表1 火力單元到目標的距離

對遺傳算法參數進行設定，初始種群數量為40，最大進化代數為100，交叉概率初始值為0.7，變異概率初始值為0.1。根據設定條件，分別采用標準遺傳算法和改進遺傳算法進行迭代仿真實驗。其實驗結果，以遺傳代數為橫軸，平均適應度值為縱軸，通過MTALAB軟件生成坐標圖直觀地表現出來。如圖1 所示，改進遺傳算法的計算結果更接近最優值，且收斂性好，能夠較好地解決反導攔截中的目標分配問題。

圖1 反導攔截中導彈目標分配結果對比圖

5 結語

反導武器目標分配，是反導攔截中的重要環節。本文在建立任務目標模型的基礎上，利用改進遺傳算法，完成了武器目標分配。仿真結果表明，改進遺傳算法較標準遺傳算法，更能適應特定的較復雜問題，其收斂速度更快，穩定性也更好，而且能夠快速尋找到全局最優解，避免陷入到局部最優解。