一種新的精英遺傳算法及在多彈攔截分配策略的應(yīng)用*

王 儲 南 英 許 航

南京航空航天大學(xué)航天學(xué)院，南京 211100

0 引言

武器-目標(biāo)分配問題(WTA)是多對多飛行器智能協(xié)同作戰(zhàn)中指揮決策的重要問題，其求解方法主要有枚舉法、分支界定法等精確算法[1]和遺傳算法，模擬退火算法，蟻群算法，粒子群算法等啟發(fā)式算法[2-6]。其中，遺傳算法(Genetic algorithm，GA)是一種有導(dǎo)向的隨機(jī)搜索算法，適合解決群體搜索最優(yōu)化問題[7]，但其求解效率會隨著問題復(fù)雜程度逐漸降低，且容易陷入局部最優(yōu)。一些學(xué)者為抑制其盲目尋優(yōu)和過早收斂的局限性[8]，進(jìn)行了很多研究。比如，Zhou等[9]將遺傳算法的均勻變異和交叉概念引入粒子群算法中，生成算法的更新方程。Wang等[10]將自適應(yīng)遺傳算法與自適應(yīng)變量鄰域搜索算法相結(jié)合，以平衡搜索和開發(fā)能力。Zhao等[11]引入自適應(yīng)交叉與變異算子和模擬退火操作，抑制了算法早熟現(xiàn)象。王少蕾等[12]通過進(jìn)化過程中變異、交叉因子的動態(tài)自適應(yīng)策略，避免算法陷入局部最優(yōu)。李瑞康等[13]將遺傳算法的交叉思想引入到粒子群更新的策略中，有效提升了算法的性能，擁有更好的綜合搜索能力。王光源等[14]根據(jù)種群多樣性測度動態(tài)調(diào)整粒子群算法的慣性權(quán)重，來抑制算法陷入局部最優(yōu)。參考上述方法可知，引入自適應(yīng)策略，一定程度上可以抑制算法陷入局部最優(yōu)，但算法的收斂速度仍需改善，且合理地將遺傳算法與其他算法或策略融合可以改善算法的性能，但單一種群進(jìn)化的多樣性遠(yuǎn)不如多個種群協(xié)同進(jìn)化好。因此，為了進(jìn)一步提升算法的性能，快速收斂得到更好的最優(yōu)解，還需擴(kuò)大種群的多樣性，增強(qiáng)算法的搜索能力。

針對空戰(zhàn)戰(zhàn)場中多導(dǎo)彈對多目標(biāo)的攔截-突防目標(biāo)分配問題，本文采用一種基于自適應(yīng)策略的改進(jìn)多種群精英遺傳算法，即多種群自適應(yīng)遺傳算法(MAGA)，來抑制算法過早收斂的情況，加快收斂速度尋找最優(yōu)解。該算法在遺傳算法的基礎(chǔ)上，增加種群群落數(shù)量，引入自適應(yīng)策略和遷移算子，采用精英選擇與備份策略，迭代計(jì)算得出最優(yōu)解。選用3種算法與本算法進(jìn)行對比，并通過數(shù)值仿真算例，驗(yàn)證本文算法的有效性。

1 多彈攔截目標(biāo)分配問題的數(shù)學(xué)描述

1.1 問題的數(shù)學(xué)描述

本文的研究背景為空中敵方多無人機(jī)來襲，我方發(fā)射多枚空空導(dǎo)彈進(jìn)行攔截，導(dǎo)彈發(fā)射前將進(jìn)行快速目標(biāo)分配。本文導(dǎo)彈與目標(biāo)均設(shè)為質(zhì)點(diǎn)，且不考慮他們的空氣動力、環(huán)境影響等。

假定攔截導(dǎo)彈表示為Mi(i=1,2,…,m)，目標(biāo)無人機(jī)表示為Nj(j=1,2,…,n)。每枚導(dǎo)彈對目標(biāo)的擊毀概率已知，設(shè)導(dǎo)彈Mi對目標(biāo)無人機(jī)Nj的擊毀概率矩陣為(pij)m×n。目標(biāo)第j個無人機(jī)的威脅系數(shù)為wj，目標(biāo)的威脅系數(shù)越大，則被分配的導(dǎo)彈數(shù)量越多。導(dǎo)彈攻擊目標(biāo)的武器-目標(biāo)分配決策矩陣為：

(1)

式中：vij∈Z(i=1,2,…,m;j=1,2,…,n)為第i個導(dǎo)彈分配給第j個目標(biāo)無人機(jī)的火力單元數(shù)[12]。若vij=1，則表示導(dǎo)彈Mi攻擊目標(biāo)Nj；若vij=0，則表示導(dǎo)彈Mi不攻擊目標(biāo)Nj。

1.2 綜合優(yōu)勢函數(shù)的構(gòu)造

綜合優(yōu)勢函數(shù)是一項(xiàng)用來評估目標(biāo)分配結(jié)果好壞的重要指標(biāo)。本文主要考慮2部分因素：1)考慮導(dǎo)彈攻擊目標(biāo)的擊毀概率最大，即所有導(dǎo)彈毀傷目標(biāo)的期望最大，可建立優(yōu)勢函數(shù)f1，見式(2)。2)考慮導(dǎo)彈與目標(biāo)在作戰(zhàn)中彈目的相對角度、相對速度與相對距離的限制與影響，參考文獻(xiàn)[15]，本文建立優(yōu)勢函數(shù)f2，見式(3)。建立總的綜合優(yōu)勢函數(shù)F=max(f1+f2)，見式(4)：

(2)

f2=c1sγsR+c2sγsv

(3)

(4)

1.3 約束條件

在多導(dǎo)彈攔截作戰(zhàn)的目標(biāo)分配問題中，為盡可能還原真實(shí)作戰(zhàn)場景，增加了一些約束條件：

1) 進(jìn)行目標(biāo)分配時(shí)，每個目標(biāo)都必須在其對應(yīng)的攔截導(dǎo)彈的可攔截范圍內(nèi)。

2) 當(dāng)彈目距離小于或等于50m時(shí)，就認(rèn)為目標(biāo)無人機(jī)將被導(dǎo)彈擊毀。

Rm={R≤50}

(5)

3) 為盡最大能力攔截目標(biāo)，每個目標(biāo)必須被分配導(dǎo)彈。

(6)

式中：s表示某目標(biāo)無人機(jī)最多允許分配的火力單元數(shù)。本文根據(jù)目標(biāo)的威脅系數(shù)wj分配對應(yīng)的導(dǎo)彈數(shù)量。

4) 模擬真實(shí)作戰(zhàn)中的資源分配不平等，導(dǎo)彈的數(shù)量一般應(yīng)多于或等于目標(biāo)數(shù)量。

(7)

根據(jù)以上建立的多導(dǎo)彈對多目標(biāo)攔截的目標(biāo)分配數(shù)學(xué)模型及約束條件，將其運(yùn)用至下一節(jié)設(shè)計(jì)的算法中。

2 多種群自適應(yīng)遺傳算法設(shè)計(jì)

MAGA曾被用于解決電網(wǎng)配電系統(tǒng)重構(gòu)、TSP問題等。本文將其應(yīng)用于空戰(zhàn)戰(zhàn)場中多導(dǎo)彈對多目標(biāo)攔截對抗的目標(biāo)分配問題。圖1為MAGA的框架圖。

圖1 多種群自適應(yīng)遺傳算法框架圖

本算法建立多個群落種群協(xié)同進(jìn)化，擴(kuò)大種群多樣性。每個種群均采用自適應(yīng)策略動態(tài)改變交叉、變異概率，保留優(yōu)秀個體，抑制算法早收斂。引入遷移算子，增加多種群間的聯(lián)系，設(shè)定精英選擇算子進(jìn)行選擇與備份。該算法能有效抑制局部最優(yōu)，加快收斂速度，獲得更優(yōu)的分配結(jié)果。下面將在2.1～2.6節(jié)中詳細(xì)介紹本算法各環(huán)節(jié)算子的設(shè)計(jì)，并在2.7節(jié)中給出算法的詳細(xì)步驟。

2.1 基因編碼設(shè)計(jì)

初始種群PoPi(i=1,2,…,n)內(nèi)的每條染色體個體編碼均代表目標(biāo)分配的一個可行解。本文選用十進(jìn)制整數(shù)編碼形式，根據(jù)目標(biāo)的威脅度值，隨機(jī)生成初始種群，并保證個體編碼序列內(nèi)無遺漏。導(dǎo)彈編號M從左到右依次遞增，染色體內(nèi)編碼信息為目標(biāo)無人機(jī)編號N，導(dǎo)彈與目標(biāo)一一對應(yīng)。以我方發(fā)射10枚導(dǎo)彈攔截?cái)撤?0架無人機(jī)為例，染色體編碼形式如圖2所示。

圖2 十進(jìn)制整數(shù)編碼形式

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用來評估個體是否達(dá)到最優(yōu)的重要指標(biāo)。本文的適應(yīng)度函數(shù)主要考慮目標(biāo)損毀率、角度、速度和距離等因素，選用1.2節(jié)中提出的綜合優(yōu)勢函數(shù)F定義，見式(4)。根據(jù)式(4)計(jì)算每條染色體個體的適應(yīng)度函數(shù)值，適應(yīng)度值越大的個體，分配效果整體越優(yōu)。

2.3 遺傳算子

遺傳算子主要包括選擇算子、交叉算子與變異算子。選擇算子能有效提升算法的收斂速度，交叉、變異算子能擴(kuò)大種群多樣性，防止算法過早收斂。

1)選擇算子。采用輪盤賭法選擇優(yōu)良個體，根據(jù)式(8)計(jì)算每個個體在子代中被選中的概率，并按照此概率選擇個體，構(gòu)成子代種群進(jìn)行下一步迭代。適應(yīng)度值越大的個體被選中的概率越大。

(8)

2)交叉算子。核心思想是：在一個父代染色體P1中隨機(jī)選擇幾個位置，并在另一個父代染色體個體P2上找到相同信息的位置。分別將兩個父代染色體被選中的基因按照順序，互相填入對方的基因序列中，一次生成兩個子代染色體個體C1和C2。算法示意圖如圖3。

圖3 交叉算子示意圖

3)變異算子。采用交換變異的方式，每條染色體隨機(jī)選擇2個位置，互相交換編碼信息。在父代染色體P1內(nèi)隨機(jī)選擇2個位置進(jìn)行交換，產(chǎn)生子代染色體C1。算法示意圖如圖4。

圖4 變異算子示意圖

2.4 自適應(yīng)策略

交叉變異概率固定不變，存在優(yōu)秀個體流失的風(fēng)險(xiǎn)。本文根據(jù)適應(yīng)度函數(shù)的值自適應(yīng)地改變交叉概率與變異概率，可以有效增加收斂速度，加速保留優(yōu)良個體，淘汰低劣個體。本文設(shè)計(jì)的自適應(yīng)交叉變異概率函數(shù)，見式(9)。

(9)

計(jì)算當(dāng)前種群內(nèi)個體的適應(yīng)度函數(shù)值F，如果當(dāng)前適應(yīng)度值大于或等于平均適應(yīng)度值，則通過式(9)計(jì)算交叉、變異概率；如果當(dāng)前適應(yīng)度值小于平均適應(yīng)度值，則仍保持原來的交叉、變異概率進(jìn)行遺傳操作。

2.5 遷移算子

遷移算子的主要作用是增加多群落之間的聯(lián)系，促進(jìn)種群協(xié)同進(jìn)化。本文將第1個種群PoP1適應(yīng)度值排名前10的個體賦值給初始遷移種群MPoP。根據(jù)圖1的流程順序，每次迭代都將遷移種群MPoP與n個種群PoPi(i=2,3,…,n)依次互相更新進(jìn)化，用適應(yīng)度函數(shù)值靠前的前10個個體更新遷移種群MPoP′，同時(shí)按照種群容量擇優(yōu)更新當(dāng)前種群PoP′。

2.6 精英選擇算子

精英選擇策略是選擇種群中一部分優(yōu)秀個體，組成一個精英種群保存?zhèn)浞荩苑乐咕€體在自適應(yīng)交叉變異操作中流失。精英種群中的全部個體不參與交叉變異等遺傳操作。

分別將種群PoPi(i=1,2,…,n)的前k個優(yōu)秀個體保存于各自的精英種群GPoPi(i=1,2,…,n)中，并隨著每次循環(huán)迭代，保證每個精英種群中始終保存各自種群發(fā)展過程中的前k個優(yōu)秀個體。

2.7 MAGA算法描述

采用MAGA解決多導(dǎo)彈對多目標(biāo)攔截對抗的目標(biāo)分配問題，具體算法流程框圖見圖5，算法步驟如下：

圖5 多種群自適應(yīng)遺傳算法流程框圖

1)種群初始化。設(shè)定種群數(shù)目x，每個種群內(nèi)含有個體數(shù)目y，隨機(jī)產(chǎn)生共x×y條染色體。導(dǎo)彈數(shù)目M，目標(biāo)無人機(jī)數(shù)目N。設(shè)定循環(huán)迭代次數(shù)t，最大交叉概率Pc1，最小交叉概率Pc2，最大變異概率Pm1，最小變異概率Pm2。

2)計(jì)算適應(yīng)度值。解碼種群內(nèi)每條染色體個體，得到武器-目標(biāo)分配決策矩陣V，根據(jù)式(4)計(jì)算每條染色體個體的種群適應(yīng)度值。

3)遺傳操作。根據(jù)式(8)進(jìn)行輪盤賭選擇操作。根據(jù)式(9)計(jì)算每條染色體個體的自適應(yīng)交叉與變異概率，進(jìn)行交叉、變異操作，得到每個種群內(nèi)的新子代種群。

4)遷移操作。對每個種群內(nèi)的個體按照適應(yīng)度值大小進(jìn)行排序，選擇更新每個種群的遷移種群MPoP與當(dāng)前子種群。

5)精英選擇與備份。按照精英選擇策略，對每個種群進(jìn)行精英選擇與備份操作，每次迭代都將更新精英種群。

6)判斷。判斷是否達(dá)到最大迭代次數(shù)t，若是，則進(jìn)行7)；若否，則轉(zhuǎn)2)循環(huán)迭代。

7)最優(yōu)選擇。將n個種群中的精英種群，根據(jù)適應(yīng)度值進(jìn)行逐一比較，得出最優(yōu)染色體個體，即多對多攔截對抗的目標(biāo)分配問題的最優(yōu)解。算法結(jié)束運(yùn)行。

3 數(shù)值仿真與分析

以多導(dǎo)彈對多目標(biāo)的攔截對抗目標(biāo)分配問題為背景，通過數(shù)值仿真分析，驗(yàn)證算法性能。假定我方共有5個火力平臺，每個火力平臺可發(fā)射3枚導(dǎo)彈，導(dǎo)彈總數(shù)目M=15，導(dǎo)彈均采用三維比例導(dǎo)引法來攔截目標(biāo)。敵方目標(biāo)無人機(jī)分3組進(jìn)攻，目標(biāo)總數(shù)目N=10，目標(biāo)分別做不同類型的sin型機(jī)動。假設(shè)導(dǎo)彈的類型各不相同，每枚導(dǎo)彈都對特定目標(biāo)有高毀傷概率，如0.7～0.9，對其他目標(biāo)的毀傷概率為0.5，毀傷概率值設(shè)定見表1。本文根據(jù)目標(biāo)的威脅值分配相應(yīng)數(shù)量的導(dǎo)彈攔截，假定目標(biāo)的威脅值為wj=[1,2,1,3,1,2,1,1,2,1]。

表1 導(dǎo)彈對目標(biāo)的攻擊毀傷概率表

其他參數(shù)設(shè)定為：種群數(shù)目x=3，每個種群內(nèi)含有個體數(shù)目y=30，循環(huán)迭代次數(shù)t=500，隨機(jī)產(chǎn)生最大交叉概率Pc1=0.8+rand(0,0.1)，最小交叉概率Pc2=0.7，隨機(jī)產(chǎn)生最大變異概率Pm1=0.1+rand(0,0.1)，最小變異概率Pm2=0.05，適應(yīng)度函數(shù)常數(shù)c1=0.5,c2=0.5。rand(0,0.1)表示在(0,0.1)區(qū)間均勻分布的隨機(jī)數(shù)。

應(yīng)用MAGA進(jìn)行武器-目標(biāo)分配，為驗(yàn)證本文設(shè)計(jì)算法的有效性，選用遺傳算法(GA)，自適應(yīng)遺傳算法(AGA)，多種群遺傳算法(MGA)進(jìn)行對比分析。通過20組數(shù)值仿真驗(yàn)證，可得到MAGA算法的最優(yōu)目標(biāo)分配方案為：[1,6,5,9,4,7,2,10,3,4,6,2,9,4,8]，最優(yōu)適應(yīng)度為15.713。四種算法的最優(yōu)適應(yīng)度平均值與最大值，見表2。

表2 四種算法的最優(yōu)適應(yīng)度值

基于MAGA算法導(dǎo)彈攔截目標(biāo)的軌跡，見圖6～7?？梢姳舅惴梢詫C(jī)動目標(biāo)很好地進(jìn)行分配，且當(dāng)目標(biāo)威脅度大于1時(shí)，可分配多個導(dǎo)彈進(jìn)行攔截。四種算法的最佳適應(yīng)度變化曲線和最優(yōu)適應(yīng)度函數(shù)箱型圖，見圖8～9。

圖6 基于MAGA算法的多對多攔截軌跡俯視圖

圖7 基于MAGA算法的多對多攔截三維軌跡圖

圖8 四種算法的適應(yīng)度對比

分析圖8的仿真結(jié)果，對比曲線GA與MGA可知，MGA尋找的最優(yōu)解遠(yuǎn)優(yōu)于GA尋找的最優(yōu)解，單種群遺傳算法容易陷入局部最優(yōu)，多種群遺傳算法能有效地?cái)U(kuò)大種群多樣性，抑制算法早熟；對比曲線MGA與MAGA可知，MAGA的收斂速度優(yōu)于MGA，MAGA約在迭代20步左右收斂到較優(yōu)解，MGA則約在80步左右收斂到較優(yōu)解。可見引入自適應(yīng)策略，可以有效增加算法的收斂速度，還可以抑制算法局部最優(yōu)。

由圖9的箱形圖和表2可知，MGA與MAGA的平均適應(yīng)度值很高且變化幅度很小，但MGA存在一些離散點(diǎn)，穩(wěn)定性略差于MAGA；GA與AGA相比可知，AGA整體優(yōu)于GA，可見加入自適應(yīng)策略還可以獲得更好的最優(yōu)解。

圖9 四種算法的最優(yōu)適應(yīng)度箱形圖

4 結(jié)束語

本文在多導(dǎo)彈對多目標(biāo)的攔截對抗目標(biāo)分配問題的實(shí)戰(zhàn)背景下，提出將多種群自適應(yīng)遺傳算法(MAGA)應(yīng)用于武器-目標(biāo)分配問題中，總結(jié)如下：

1)適應(yīng)度函數(shù)與約束條件。本文選用武器擊毀目標(biāo)概率最大為評估標(biāo)準(zhǔn)，增加導(dǎo)彈與目標(biāo)的相對距離、速度和角度等變量，使得問題描述地更精確真實(shí)，求解精度得到提高。

2)多個種群與遷移算子。本文采用多個種群做并行迭代計(jì)算，通過遷移算子加強(qiáng)種群間的聯(lián)系，有效擴(kuò)大種群多樣性，抑制算法過早收斂。

3)自適應(yīng)策略與精英選擇策略。本文引入自適應(yīng)策略動態(tài)改變交叉、變異概率，有效保留優(yōu)秀個體，加速淘汰低劣個體。引入精英選擇策略來選擇備份優(yōu)秀個體。

通過與GA、MGA、AGA算法進(jìn)行對比分析，驗(yàn)證了本文設(shè)計(jì)的MAGA算法能有效提高求解精度與收斂速度，抑制局部最優(yōu)。在多導(dǎo)彈攔截多機(jī)動目標(biāo)的算例中，證明了該算法可用于解決一定規(guī)?？諔?zhàn)中的武器-分配問題，對多導(dǎo)彈攔截多目標(biāo)作戰(zhàn)的智能決策有一定的參考價(jià)值。