劉韜，廖承城

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

0 引言

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

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

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

1 問題描述

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

2 任務分配模型

2.1 彈頭目標假設

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

2.2 攔截彈假設

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

2.3 模型建立

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

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

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

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

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

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

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

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

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

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

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

3 改進遺傳算法設計

3.1 基因編碼設計

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

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

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

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

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

Tent 映射產(chǎn)生混沌序列的表達式是：

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

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

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

3.3 選擇操作

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

3.4 交叉和變異操作

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

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

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

交叉操作，本文根據(jù)交叉概率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]區(qū)間的隨機數(shù)。完成交叉操作后判斷是否滿足約束條件，如不滿足，則恢復到交叉前的數(shù)據(jù)，重新進行交叉操作，直到滿足條件為止。采用這種混合交叉算子的交叉方式獲得子代個體，可在進化前期，加快收斂速度。

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

3.5 算法描述

Step1 設置初始Gen、Pc1、Pm1。

Step2 根據(jù)啟發(fā)信息及Tent 映射生成初始種群。

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

Step4 執(zhí)行精英保留操作，根據(jù)適應度值，進行選擇操作。

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

Step6 根據(jù)概率Pc、Pm，進行交叉操作、變異操作，產(chǎn)生新的種群。

Step7 判斷是否滿足終止條件，若滿足，輸出最優(yōu)解；不滿足，則Gen=Gen+1，跳轉(zhuǎn)至Step3 繼續(xù)執(zhí)行。

4 仿真實驗

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

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

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

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

5 結(jié)語

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