改進人工免疫算法的多機協(xié)同空戰(zhàn)目標(biāo)分配方法

高陽陽, 陳雙艷, 余敏建, 海靜, 房瑞躍

1．中國人民解放軍93175 部隊，吉林長春130000; 2．空軍工程大學(xué)空管領(lǐng)航學(xué)院，陜西西安710051;3．中國人民解放軍94754 部隊，浙江嘉興314000; 4．中國人民解放軍95026 部隊，廣東佛山528000

近年來,隨著高新技術(shù)的快速發(fā)展,戰(zhàn)斗機協(xié)同空戰(zhàn)已成為現(xiàn)代空戰(zhàn)的主要作戰(zhàn)樣式。在多機協(xié)同空戰(zhàn)中,如何根據(jù)戰(zhàn)場態(tài)勢,合理分配目標(biāo),充分發(fā)揮多機協(xié)同空戰(zhàn)的整體作戰(zhàn)效能,是多機協(xié)同空戰(zhàn)指揮決策中最為關(guān)鍵的問題之一。目前,用于求解目標(biāo)分配問題的方法有粒子群算法[1]、遺傳算法[2]、蟻群算法[3]、螢火蟲算法[4]及其混合優(yōu)化算法[5]等。但這些算法收斂速度很慢,有時得不到穩(wěn)定的解,嚴(yán)重影響指揮員進行空戰(zhàn)決策。

人工免疫算法從提出至今已被廣泛應(yīng)用于各領(lǐng)域,如模式識別[6]、網(wǎng)絡(luò)安全[7]、圖像處理[8]等。文獻[9]在采用自適應(yīng)錦標(biāo)賽選擇算子的基礎(chǔ)上,引入“(1+λ)-選擇”全局更新技術(shù)對人工免疫算法進行改進,解決了武器-目標(biāo)分配問題;文獻[10]提出了一種新的編碼方案和親合度算法對免疫算法進行改進,解決了編隊防空火力分配問題;文獻[11]為防止人工免疫算法提前陷入局部最優(yōu),對抗體群進行改造,解決了火力分配問題。隨著免疫算法越來越受到學(xué)者的關(guān)注,出現(xiàn)了一些與并行免疫算法有關(guān)的研究成果。文獻[12]為求解大規(guī)模TSP問題,提出了一種基于TMSM的并行免疫記憶克隆選擇算法;文獻[13]為克服克隆選擇算法收斂速度慢的缺陷,采用定向突變的自適應(yīng)并行搜索策略對傳統(tǒng)免疫算法進行了改進;文獻[14]為克服傳統(tǒng)遺傳算法在求解路徑規(guī)劃問題時,不能以概率1進行收斂的缺陷,提出了一種基于抗體-抗原親合度、抗體-抗體親合力自適應(yīng)動態(tài)調(diào)整的偽并行免疫算法。但以上算法存在如下問題:缺少種群間信息的交換,搜索效率低,容易出現(xiàn)早熟收斂現(xiàn)象。

基于此,本文在研究了傳統(tǒng)和改進人工免疫算法的基礎(chǔ)上,設(shè)計了一種并行人工免疫算法以提高算法搜索效率,并采用新的移民算子實現(xiàn)2個種群間的信息交換,從而保證種群的多樣性。最后利用改進人工免疫算法求解多機協(xié)同空戰(zhàn)問題,得到了最優(yōu)分配方案。

1 多機協(xié)同空戰(zhàn)目標(biāo)分配數(shù)學(xué)模型

多機協(xié)同空戰(zhàn)目標(biāo)分配是指揮決策過程中一個十分重要的環(huán)節(jié)。本文以多機協(xié)同空戰(zhàn)為背景,采用簡明實用的非參量法對多機協(xié)同空戰(zhàn)目標(biāo)分配問題進行數(shù)學(xué)建模。傳統(tǒng)的綜合優(yōu)勢函數(shù)主要是根據(jù)角度優(yōu)勢、距離優(yōu)勢和能量優(yōu)勢進行構(gòu)造,但隨著戰(zhàn)機性能在空戰(zhàn)中發(fā)揮的作用越來越明顯,傳統(tǒng)的綜合優(yōu)勢函數(shù)已經(jīng)不適用于現(xiàn)代空戰(zhàn)中的多機協(xié)同目標(biāo)分配問題。因此本文以傳統(tǒng)模型為基礎(chǔ),考慮戰(zhàn)機性能優(yōu)勢,建立如下空戰(zhàn)優(yōu)勢評價指標(biāo)體系:

圖1 空戰(zhàn)優(yōu)勢評價指標(biāo)體系

1.1 角度優(yōu)勢

(1)

式中,ψa為目標(biāo)方位角,ψt為目標(biāo)進入角。其中:ψa∈[0,180];ψt∈[0,180]。

1.2 距離優(yōu)勢

(2)

式中,rij為我方第i架戰(zhàn)機與敵方第j架戰(zhàn)機之間的距離,rimissle和riradar分別為我方第i架戰(zhàn)機的導(dǎo)彈射程和雷達最大探測距離。

1.3 能量優(yōu)勢

(3)

式中,Eg為戰(zhàn)機單位質(zhì)量的能量,h為戰(zhàn)機高度,v為戰(zhàn)機速度,g為重力加速度。根據(jù)(3)式建立能量優(yōu)勢函數(shù)如下所示

(4)

式中,Egi為我方第i架戰(zhàn)機單位質(zhì)量的能量,Egj為敵方第j架戰(zhàn)機單位質(zhì)量的能量。

1.4 戰(zhàn)機性能優(yōu)勢

H=h/max(h)

(5)

式中

h=

[lnB+ln∑A1+1+ln∑A2+1]ε1ε2ε3ε4,

B為機動參數(shù),A1為火力參數(shù),A2為探測能力參數(shù),ε1為操縱效能參數(shù),ε2為生存力參數(shù),ε3為航程系數(shù),ε4為電子對抗能力系數(shù)。根據(jù)(5)式建立戰(zhàn)機性能優(yōu)勢函數(shù)如下所示

(6)

式中,Hi為我方第i架戰(zhàn)機的空戰(zhàn)指數(shù),Hj為敵方第j架戰(zhàn)機的空戰(zhàn)指數(shù)。

1.5 綜合優(yōu)勢函數(shù)

S=k1S1+k2S2+k3S3+k4S4

(7)

式中,k1,k2,k3,k4為指標(biāo)權(quán)重。傳統(tǒng)權(quán)重值的確定,常常是由人為給出,有很大的主觀性和盲目性。為了更加合理地處理客觀信息,本文采用文獻[15]中改進的熵權(quán)法確定指標(biāo)權(quán)重。

1.6 綜合優(yōu)勢函數(shù)矩陣

假設(shè)在一次空戰(zhàn)中,我方戰(zhàn)機n架,敵方戰(zhàn)機m架。根據(jù)(7)式可得我方第i架戰(zhàn)機對敵方第j架戰(zhàn)機的綜合優(yōu)勢值Sij。從而可以建立起綜合優(yōu)勢函數(shù)矩陣S。

S={Sij},i=1,2,3…,n;j=1,2,3…,m

(8)

多機協(xié)同空戰(zhàn)目標(biāo)分配目標(biāo)函數(shù)定義為

(9)

式中,xij表示我方第i架戰(zhàn)機是否分配給敵方第j架戰(zhàn)機,xij=1表示是,xij=0表示否。

約束條件:

2 改進的人工免疫算法

2.1 初始種群的產(chǎn)生

傳統(tǒng)的人工免疫算法采用單種群方式進行進化,容易產(chǎn)生早熟收斂現(xiàn)象。有些并行人工免疫算法采用多種群并行進化的方式,但是多采用比較單一的隨機方式產(chǎn)生初始種群,通過移民算子進行多種群間的個體交換后,很難打破各種群內(nèi)部的平衡,其保持種群多樣性的效果不是十分明顯。

本文設(shè)計的并行人工免疫算法采用2種不同的方式產(chǎn)生初始種群,分別為隨機和人工方式。隨機方式是在滿足4個約束條件的前提下,隨機產(chǎn)生的初始解,具有較強的隨機性。人工方式是由人為確定的滿足約束條件的初始解,具有較強的主觀性。分別采用隨機和人工方式產(chǎn)生的2個初始種群,使2個種群在產(chǎn)生之處就具有不同的特征,通過移民算子進行種群間個體交換后,能夠打破2種群內(nèi)部的平衡,增強種群多樣性,使種群向著更高級別進行進化,從而得到全局最優(yōu)解。

2.2 親合度函數(shù)和編碼方式的選擇

人工免疫算法是模仿生物信息系統(tǒng)中的抗原識別、記憶等功能而提出的一種智能計算方法。多機協(xié)同空戰(zhàn)目標(biāo)分配問題與人工免疫系統(tǒng)(AIS)有很多相似之處,如表1所示。

表1 AIS與多機協(xié)同空戰(zhàn)目標(biāo)分配問題比較

由表1和2.1節(jié)可知,人工免疫算法的抗原為公式(9),抗體為滿足公式(9)和約束條件1)～4)的解?？贵w-抗原親合度直接采用歸一化后的目標(biāo)函數(shù)進行評價

(10)

本文采用傳統(tǒng)的整數(shù)編碼方式,以我方戰(zhàn)機數(shù)量為編碼長度,即基因長度為n。抗體位上記錄的編號為敵方戰(zhàn)機代號,抗體位序號為我方戰(zhàn)機代號。具體編碼過程如圖2所示。

圖2 抗體編碼過程

2.3 交叉、變異算子

為了保持種群的多樣性,防止過早收斂,通常要進行交叉、變異操作。通過選擇算子保留下來的抗體按照一定的概率進行配對交叉,然后根據(jù)變異概率進行變異操作,從而得到新的抗體。

本文分別采用2種交叉、變異算子,具體變換如下所示:

交叉算子1

交叉前

2313………67

13556………21

交叉后

13313………67

22556………21

交叉算子2

交叉前

27125………46

25651………34

交叉后

65125………4625271………34

變異算子1

變異前

22315………14

變異后

43315………14

變異算子2

變異前

25421………63

變異后

25241………63

2.4 移民算子

移民算子的作用是為了實現(xiàn)2個種群間信息的交流,使種群向著更高級別進化,保持種群的多樣性。本文在傳統(tǒng)移民算子的基礎(chǔ)上提出了一種新的移民算子。算法步驟如下所示:①確定2個初始種群,計算2個種群內(nèi)每個個體親合度。②將2個種群內(nèi)的個體按照親合度大小進行排序。③將2個種群內(nèi)排序好的個體按照親合度大小平均分成大、中、小3段。④設(shè)定種群間個體交換規(guī)模,本文取15%。⑤按照優(yōu)者多選,劣者少選的原則,將2個種群內(nèi)的每段按15%×(1,0.9,0.1),15%×(1,0.7,0.3),15%×(1,0.8,0.6)比例選擇。⑥將選出的個體進行種群間交換重新產(chǎn)生2個新種群。

以比例(1,0.7,0.3)為例,將上述思想用圖形表示。

圖3 種群間個體交換示意圖

2.5 并行人工免疫算法設(shè)計

傳統(tǒng)人工免疫算法多采用單種群進化方式,缺少種群間信息之間的交流,搜索效率低,難以保持種群多樣性,容易陷入局部最優(yōu)。基于此,本文設(shè)計了一種并行人工免疫算法,具體操作流程和算法流程圖如圖4所示。

具體操作流程如下。

1) 分別采用隨機和人工2種方式產(chǎn)生初始種群A、B。采用整數(shù)編碼方式對種群中的個體進行編碼,以(10)式作為親合度函數(shù)。

2) 設(shè)置獨立運行代數(shù)n,種群A、B分別采用不同的選擇策略、交叉操作、變異操作進行進化。

3) 當(dāng)種群A、B進化到指定代數(shù)時,采用新的移民算子進行兩種群間個體交換。

4) 設(shè)置獨立進化代數(shù)m,按照上圖獨立運行方式繼續(xù)進行進化操作。

5) 判斷是夠滿足終止條件。如果滿足條件則輸出結(jié)果,否則返回步驟3)。

6) 2條子線計算結(jié)束后,選擇親合度函數(shù)值大的結(jié)果作為問題的最優(yōu)解。

圖4 并行人工免疫算法流程圖

3 仿真分析

3.1 算例仿真

在某次空戰(zhàn)中我方戰(zhàn)機7架與敵方5架遭遇。其中我方1架戰(zhàn)機只能攻擊敵方1架戰(zhàn)機,敵方戰(zhàn)機2,3,5可同時被我方2架戰(zhàn)機攻擊。g取9.8,k1=0.239 730,k2=0.304 524,k3=0.186 341,k4=0.269 405。根據(jù)戰(zhàn)場某一時刻敵我雙方的態(tài)勢信息,由公式(1)～(7)求得我方戰(zhàn)機對地方戰(zhàn)機的綜合優(yōu)勢值，如表2所示。

表2 我方對敵方戰(zhàn)機綜合優(yōu)勢表

2個初始種群大小取50,獨立運行代數(shù)分別設(shè)定為10代、40代,選擇、交叉、變異操作采用圖4中方法,交叉概率取0.7,變異概率取0.05。針對3種遷徙比例A(15%,13.5%,1.5%),B(15%,12%,9%),C(15%,10.5%,4.5%)按照本文提出的改進人工免疫算法進行仿真。3種遷徙比例對應(yīng)的最優(yōu)親合度演變過程如圖5所示,最優(yōu)目標(biāo)分配方案如表3所示。

圖5 3種遷徙比例最優(yōu)親合度演變

從圖5可以看出,改進的免疫算法采用遷徙比例(15%,12%,9%)時,在最優(yōu)值求解上要優(yōu)于另外2種比例。

表3 最優(yōu)目標(biāo)分配方案

表3為采用遷徙比例為(15%,12%,9%)時,得出的最優(yōu)分配方案。分配方案為我方戰(zhàn)機5攻擊敵方戰(zhàn)機1;我方戰(zhàn)機6攻擊敵方戰(zhàn)機2;我方戰(zhàn)機1、4同時攻擊敵方戰(zhàn)機3;我方戰(zhàn)機2攻擊敵方戰(zhàn)機4;我方戰(zhàn)機3,7同時攻擊敵方戰(zhàn)機5。目標(biāo)分配后,多機協(xié)同整體作戰(zhàn)效能為2.826 7。

3.2 改進人工免疫算法性能分析

為了進一步分析本文所提算法性能,現(xiàn)將本文算法與傳統(tǒng)人工免疫算法、文獻[11]中的改進人工免疫算法和文獻[14]中的并行免疫算法進行比較,本文所提算法分別采用遷徙比例A,B和C分別對文獻[11]中的算例進行30次仿真。4種算法最優(yōu)值求解和消耗時間統(tǒng)計結(jié)果如表4～表7所示。

表4 本文算法最優(yōu)值和消耗時間統(tǒng)計結(jié)果

表5 傳統(tǒng)算法最優(yōu)值和消耗時間統(tǒng)計結(jié)果

表6 文獻[11]算法最優(yōu)值和消耗時間統(tǒng)計結(jié)果

表7 文獻[14]算法最優(yōu)值和消耗時間統(tǒng)計結(jié)果

從表4可以看出,采用本文算法對文獻[11]中的算例進行仿真,在采用遷徙比例B時,效果最好,采用遷徙比例C時,效果其次,采用遷徙比例A時,效果最差。將表4分別與表5、表6和表7進行對比可得:本文算法在采用遷徙比例B時,與其他3種算法相比具有比較明顯的優(yōu)勢;本文算法在采用遷徙比例C時,較傳統(tǒng)算法和文獻[11]中算法有比較明顯的優(yōu)勢,較文獻[14]中算法,優(yōu)勢很小;本文算法在采用遷徙比例A時,與傳統(tǒng)算法相比較,有明顯的優(yōu)勢,與文獻[11]中的算法相比較,優(yōu)勢很小,與文獻[14]中的算法相比較,具有一定的劣勢。進一步說明了本文中改進人工免疫算法的性能受遷徙比例的影響,在采用遷徙比例(15%,12%,9%)時,算法效果最優(yōu)。采用并行運行方式并增加遷徙操作,能夠?qū)崿F(xiàn)2個不同種群間信息的交流,增強種群多樣性,從而有效地改善最優(yōu)策略的求解精度,提高算法收斂速度。

4 結(jié) 論

本文在分析了多機協(xié)同空戰(zhàn)目標(biāo)分配問題特點的基礎(chǔ)上,提出了改進人工免疫算法的多機協(xié)同空戰(zhàn)目標(biāo)分配方法。建立了多機協(xié)同空戰(zhàn)目標(biāo)分配數(shù)學(xué)模型,設(shè)計了一種并行人工免疫算法,給出了改進人工免疫算法的具體流程,并針對3種遷徙比例進行了仿真分析,驗證了改進人工免疫算法在采用遷徙比例B時,能夠取得更優(yōu)的結(jié)果。將改進人工免疫算法與3種人工免疫算法進行了比較,在大多數(shù)情況下,改進人工免疫算法與其他3種人工免疫算法相比,能夠在更短的時間內(nèi)求得更優(yōu)的結(jié)果。