蘇 山，馬澤遠，張 立，周夢平，劉昊東

(上海機電工程研究所，上海 201109)

0 引言

隨著進攻導(dǎo)彈技術(shù)的不斷發(fā)展,單一攔截彈防空模式已經(jīng)無法滿足現(xiàn)代作戰(zhàn)需求[1-3],因此多攔截器技術(shù)(multiple kill vehicle,MKV)應(yīng)運而生。通常多攔截器技術(shù)是指通過一次導(dǎo)彈發(fā)射,釋放出多個攔截器,同時摧毀多個來襲威脅目標(biāo)的技術(shù),以增加對來襲導(dǎo)彈的攔截概率并提高攔截效率。在多攔截器技術(shù)眾多分支中,目標(biāo)分配技術(shù)極為重要,受到研究者的普遍重視。

針對武器目標(biāo)分配問題(weapon target allocation,WTA),Shi等[4]引入一種大規(guī)模稀疏問題的進化算法(SparseEA),解決了特定問題初始化方法,帶有獎勵策略的遺傳算子能夠考慮變量的稀疏性高效生成解的問題,并提出了一種改進的非支配解選擇方法來處理約束。Fu等[5]提出了一種變概率賦值技術(shù),用概率分配方式代替隨機均勻分配方式對遺傳算法變量進行初始化,生成接近最優(yōu)個體的初始種群個體,表現(xiàn)出了比傳統(tǒng)初始化方法更優(yōu)的計算結(jié)果。Wang等[6]設(shè)計了一種基于遺傳算法的變值控制方法,以克服智能算法在解決WTA時由于問題規(guī)模過大或無法獲得可行解而導(dǎo)致求解速度過慢的缺點。Zhang等[7]開發(fā)一種基于差分進化的粒子群優(yōu)化算法求解器以求解多任務(wù)優(yōu)化問題,展示出了比傳統(tǒng)算法更優(yōu)的計算效果。吳詩輝等[8]以分配方案末速度差之和最大為優(yōu)化目標(biāo),以給定均勻分配度為約束條件,將其轉(zhuǎn)化為帶約束的非平衡任務(wù)分配問題,并用線性規(guī)劃方法進行求解。目前,針對WTA問題的研究方向依然主要集中在傳統(tǒng)智能啟發(fā)式優(yōu)化算法的改進上,通常通過融合不同的啟發(fā)式算法,或加入更優(yōu)的初始化策略以提高算法的計算效率以及其他性能。在相似領(lǐng)域中,Zammit等[9]針對3維無人機路徑規(guī)劃問題,比較了A*算法與快速探索(RRT)隨機樹算法,開發(fā)了一組變體來減輕標(biāo)準(zhǔn)算法中固有的缺點,通過相同場景下的計算發(fā)現(xiàn)改進后的A*算法性能更優(yōu)。Chen等[10]通過引入人工勢場法與A*算法進行結(jié)合,極大的改進了A*算法的計算速度,并有效縮短了所規(guī)劃的路徑長度。Li等[11]提出了一種基于高斯分布信息素揮發(fā)的蟻群算法來解決復(fù)雜環(huán)境下的機器人避障及路徑規(guī)劃問題,實現(xiàn)了更高效的避障效果。Alnowibet等[12]針對多約束優(yōu)化問題提出了一種混合梯度模擬退火算法,在效率、質(zhì)量、魯棒性上都得到了一定程度的提升。

文中以防空攔截器為研究對象,開展基于改進粒子群優(yōu)化的多攔截器目標(biāo)分配方法研究。首先建立多攔截器目標(biāo)分配數(shù)學(xué)模型,將目標(biāo)分配問題轉(zhuǎn)化為離散優(yōu)化問題;然后針對傳統(tǒng)離散粒子群算法(DPSO)計算效率不足的問題,引入改進粒子群優(yōu)化算法,進行編解碼策略和分配算法的設(shè)計,并以一種包含三種鄰域結(jié)構(gòu)的變鄰域搜索算法,分別解決了傳統(tǒng)粒子群算法求解離散優(yōu)化和局部收斂的問題;接著設(shè)計了局部跳出策略的啟動準(zhǔn)則,以平衡算法的算力開銷,提高算法適應(yīng)性;最后在數(shù)值仿真中設(shè)計了三種不同的工況,驗證了所設(shè)計的改進粒子群優(yōu)化算法有效性。

1 多攔截器目標(biāo)分配數(shù)學(xué)模型

文中目標(biāo)分配問題建立在如下的條件或假設(shè)上:

1)進攻飛行器以及攔截器實時位置速度矢量均已知;

2)每枚攔截器最多分配給1枚進攻飛行器。

文中主要對收益適應(yīng)度函數(shù)進行建模,用以表征分配效能。收益包含進攻飛行器對攔截方設(shè)施威脅程度、攔截成功概率等指標(biāo)。威脅程度可以用威脅距離、進攻飛行器飛行速度以及打擊目標(biāo)的重要程度等來衡量。文中將進攻飛行器Ej威脅程度適應(yīng)度函數(shù)Fr,j定義為:

Fr,j=τ1exp(Rt+(1-sgn(Rt))r+
τ2(1-exp(-v))+τ3Fr3)

(1)

根據(jù)文獻[13],攔截器Pi對進攻飛行器Ej的攔截概率估計模型函數(shù)表示為:

(2)

當(dāng)采用M枚攔截器(Pi,i=1,2,…,M)對N個進攻飛行器(Ej,j=1,2,…,N)進行攔截時,為保證最佳的整體攔截效果,指定所有攔截器都需要分配到進攻飛行器,而每枚攔截器至多分配給一個進攻飛行器。設(shè)計所有分配到的攔截器對進攻飛行器Ej的攔截成功率定義為:

(3)

式中,Λij表示分配矩陣Λ中的元素,并且

(4)

設(shè)計目標(biāo)分配總收益適應(yīng)度為總的進攻飛行器威脅程度與攔截概率的組合,記為:

(5)

2 改進粒子群優(yōu)化算法

下面首先介紹粒子編碼解碼策略,解決傳統(tǒng)粒子群算法無法解決離散優(yōu)化的問題;然后引入改進粒子群優(yōu)化算法,利用變鄰域搜索算法(VNS)鄰域結(jié)構(gòu)變換的特點,解決粒子群優(yōu)化算法容易陷入局部最優(yōu)問題,并在算法中引入了跳出準(zhǔn)則以平衡變鄰域搜索算力消耗問題。

2.1 粒子編碼解碼策略

對于最優(yōu)目標(biāo)分配問題,其求解類似于整數(shù)規(guī)劃問題,而粒子群優(yōu)化算法的更新是一個連續(xù)變化的過程,難以避免出現(xiàn)非整數(shù)的解。因此對于連續(xù)變化的粒子需要通過合適策略進行編解碼才能匹配問題的解。

由前面分析可知,每一Λ矩陣都代表一個分配結(jié)果,其具體含義為:矩陣行代表同一個攔截器編號,列代表同一個目標(biāo)飛行器編號。矩陣中元素Λij=0代表攔截器i不分配給目標(biāo)j,Λij=1則反之。由于同一枚攔截器最多只能分配給一個目標(biāo),因此可以很容易得知,應(yīng)滿足約束矩陣無窮范數(shù)應(yīng)當(dāng)小于或等于1,即

(6)

因此該優(yōu)化問題可表示為:

(7)

式中F*表示最優(yōu)適應(yīng)度函數(shù)。

文中以粒子分配矩陣Λ作為粒子的位置,欲得到滿足要求的分配矩陣,則需要對連續(xù)變化的粒子位置進行解碼。

首先,可以明確得知每一種分配結(jié)果的適應(yīng)度值以及分配約束;其次,最優(yōu)分配對應(yīng)的分配矩陣元素值為1,而其他值為0?；谏鲜鰲l件,給出以下引理。

根據(jù)上述引理,文中設(shè)計粒子Λ位置初值滿足Λij∈[0,1],那么根據(jù)適應(yīng)度函數(shù)式(5)進行迭代的粒子群優(yōu)化算法能夠收斂到極值點,且滿足式(7)。以下給出證明過程。

證明:考慮適應(yīng)度函數(shù)式(5)與式(3),則

(8)

(9)

對式(9)取極大值可得:

(10)

由定義可知粒子矩陣Λ僅在列上有約束,而各行取值完全獨立,則有

(11)

當(dāng)設(shè)計此任務(wù)分配問題的適應(yīng)度函數(shù)為式(8)的形式時,運行粒子群優(yōu)化算法,粒子的位置會自發(fā)向整數(shù)解上收斂。因此,粒子充分收斂后的位置可以滿足式(7)約束,即為該離散優(yōu)化問題的解。

2.2 引入VNS算法改進策略

PSO算法執(zhí)行過程中,容易陷入局部收斂,從而導(dǎo)致最終收斂到的非全局最優(yōu)解。下面設(shè)計基于變鄰域搜索(VNS)算法的局部跳出策略,從而保證算法能夠有效跳出局部極值進而找到全局最優(yōu)解。

VNS算法的核心思想是利用不同的鄰域結(jié)構(gòu)進行交替搜索,從而跳出原來的解,擴展算法搜索范圍。而對于文中給出的粒子形式,其鄰域結(jié)構(gòu)意義十分明確。首先對于一個矩陣有行變換和列變化兩種基本的變換方式,而由粒子矩陣Λ定義可知,不同的行和列分別表示不同的攔截器和不同的目標(biāo)飛行器。于是行變換和列變化均能夠在不破壞原粒子離散特性的基礎(chǔ)上,改變當(dāng)前分配策略并形成新的分配,進而找到全局最優(yōu)解。

由上述定義可以得知,Λ矩陣行變換和列變換均能改變當(dāng)前的分配策略,跳出局部解并擴大搜索范圍。于是在文中定義如下三種鄰域結(jié)構(gòu)。

1)第一鄰域結(jié)構(gòu)(交換鄰域,swaped nerghborhood):選取Λ矩陣中第i行與第j行進行交換,且i=random{1,2,…,M},j=random{1,2,…,M},i≠j;同時選取第k列與第l列進列交換,且k=random{1,2,…,N},l=random{1,2,…,N},k≠l。

2)第二鄰域結(jié)構(gòu)(轉(zhuǎn)置鄰域,inverted neighborhood):在Λ矩陣中任選第i行,并將該行元素進行對稱轉(zhuǎn)置,且i=random {1,2,…,M},Λij=Λi(N-j+1),j∈{1,2,…,N},其余部分保持不變。

3)第三鄰域結(jié)構(gòu)(置換鄰域,exchanged neighborhood)向量,隨機生成一個滿足粒子約束的行向量,并將該行向量替換Λ矩陣中任意第i行,i=random{1,2,…,M},組成新的Λ矩陣。

根據(jù)以上三種鄰域結(jié)構(gòu),設(shè)計對應(yīng)鄰域抖動算法。算法設(shè)計思路為:針對每一種鄰域結(jié)構(gòu),設(shè)定搜索次數(shù)K,在每次搜索中,執(zhí)行相應(yīng)變鄰域操作,并將操作前后適應(yīng)度值進行比較,記錄更優(yōu)解。

得到上述三種鄰域抖動算法之后,設(shè)計變鄰域搜索算法,將這三種鄰域操作包括進來,形成完整的變鄰域搜索策略。由于任何一種鄰域結(jié)構(gòu)的成功改變均能夠改變原先分配策略,因此設(shè)計當(dāng)鄰域結(jié)構(gòu)改變能夠使得適應(yīng)度函數(shù)值增加時,應(yīng)當(dāng)針對改變后的分配矩陣從第一鄰域結(jié)構(gòu)重新開始新一輪搜索。包含三種鄰域結(jié)構(gòu)的變鄰域算法流程如圖1所示。

圖1 VNS算法框架示意圖Fig.1 VNS algorithm Framework

由上面的分析可以看出,對于一個陷入局部收斂的PSO算法,將一個分配矩陣當(dāng)作PSO算法中的一個粒子,通過進行上述的操作鄰域就能夠?qū)崿F(xiàn)收斂局部的廣度搜索,進而增加求得全局最優(yōu)解的可能性。

當(dāng)進行粒子群算法求解時,粒子位置會自發(fā)收斂到一個非0即1的整數(shù)序列,此時適應(yīng)度值將保持不變,粒子群算法可以看作進入了局部收斂,且此時進入變鄰域搜索不會破壞粒子收斂性。因此文中以粒子的適應(yīng)度函數(shù)值變化情況作為粒子是否進入局部收斂狀態(tài)的判斷,并以此作為變鄰域搜索的啟動準(zhǔn)則,增加了變鄰域算法的自適應(yīng)性。同時由于局部跳出策略計算量大,為了平衡計算開銷,設(shè)計一定的跳出間隔,當(dāng)?shù)谝淮翁龊?經(jīng)過指定的迭代次數(shù),并且滿足粒子適應(yīng)度不發(fā)生變化時(局部收斂)進行跳出算法的執(zhí)行。

于是,一種結(jié)合變鄰域搜索的粒子群優(yōu)化算法的流程圖如圖2所示。算法劃分為粒子群優(yōu)化以及變鄰域搜索兩大部分,二者通過變鄰域算法啟動準(zhǔn)則連接。當(dāng)達到啟動準(zhǔn)則后,則對粒子加入變鄰域的操作,使得粒子跳出局部收斂。

圖2 改進粒子群算法流程圖Fig.2 Flow chart of improved particle swarm optimization

3 數(shù)值仿真及結(jié)果分析

針對提出的改進粒子群優(yōu)化算法分別設(shè)置三組仿真工況:

1)對比貪婪算法(greedy algorithm,GA)、傳統(tǒng)粒子群算法(particle swarm optimization,PSO,采用文中的編解碼策略)、離散粒子群(discrete particle swarm optimization,DPSO)算法及遍歷算法(traversal algorithm,TA),驗證改進粒子群優(yōu)化算法(improved particle swarm optimization,IPSO)優(yōu)越性。

2)通過調(diào)整系數(shù)驗證啟動準(zhǔn)則的有效性。

3)場景變化時的目標(biāo)分配算法。

設(shè)置仿真場景:

1)10枚攔截器參數(shù)見表1,包括位置坐標(biāo)、速度、攻擊距離及最大探測距離。

表1 攔截器參數(shù)Table 1 Interceptor parameters

2)8枚進攻飛行器參數(shù)見表2,包括位置坐標(biāo)、速度及重要程度。

表2 目標(biāo)飛行器參數(shù)Table 2 Target vehicle parameters

3.1 仿真試驗1

使用文中設(shè)計的改進粒子群優(yōu)化算法與傳統(tǒng)粒子群優(yōu)化算法、DPSO算法及貪心算法進行比較,分配結(jié)果的適應(yīng)度函數(shù)變化如圖3所示。

圖3 算法收斂曲線比較Fig.3 Algorithm convergence curve comparison

圖3展示了分別采用文中給出的改進粒子群優(yōu)化算法、傳統(tǒng)粒子群算法、DPSO算法和貪婪算法針對給出的仿真場景進行分配仿真的計算結(jié)果。橫坐標(biāo)表示迭代的代數(shù),縱坐標(biāo)表示全局最優(yōu)適應(yīng)度函數(shù)。紅線表示改進粒子群優(yōu)化算法的最優(yōu)適應(yīng)度變化曲線,藍色虛線表示傳統(tǒng)粒子群算法的最優(yōu)適應(yīng)度變化曲線,“x”型點為進行變鄰域搜索的代數(shù),黑色虛線表示貪婪算法適應(yīng)度變化曲線,藍色實線表示DPSO算法收斂曲線。比較傳統(tǒng)粒子群算法曲線可以得知,在粒子群優(yōu)化算法還未收斂時,兩算法的收斂曲線大致保持一致;粒子開始收斂時,二者出現(xiàn)明顯不同,可以看出,在傳統(tǒng)粒子群優(yōu)化算法迭代到第30代左右時,粒子已經(jīng)陷入了收斂狀態(tài),此后變一直保持局部收斂的狀態(tài)。而對比改進粒子群優(yōu)化算法,在第30代之后,當(dāng)滿足進入變鄰域局部搜索的條件時(圖中“x”型點),算法便會進行一次變鄰域搜索,找到一個新的更優(yōu)的解,從而讓粒子群算法跳出局部最優(yōu)的狀態(tài),并向全局最優(yōu)進行收斂。對比離散粒子群優(yōu)化算法(DPSO),由于此離散算法在粒子空間中無收斂的概念,精細搜索(局部搜索)能力較差,表現(xiàn)為適應(yīng)度收斂速度慢且很難找到全局最優(yōu)解。由貪心算法的適應(yīng)度變化曲線可以看出,在迭代10次時,其實算法已經(jīng)計算完成,并且收斂到了一個較差的結(jié)果。

由表3目標(biāo)分配結(jié)果可以看出,采用幾種算法最終收斂結(jié)果都能使得目標(biāo)分配矩陣元素收斂到0或1,并且滿足一枚攔截器最多分配給一個目標(biāo)的約束;由于仿真場景中攔截器數(shù)量多于進攻目標(biāo)的數(shù)量,因此可以看出有些目標(biāo)被分配給多于一枚的攔截器,符合實際情況。同時,對比三種分配算法的分配結(jié)果也可以看出,使用改進粒子群優(yōu)化算法的最優(yōu)適應(yīng)度值更大,更接近遍歷算法得到的全局最優(yōu)值。

表3 目標(biāo)分配結(jié)果Table 3 Target assignment result

3.2 仿真試驗2

驗證改進粒子群優(yōu)化算法中局部跳出算法啟動準(zhǔn)則的合理性。試驗次數(shù)為5,試驗結(jié)果記錄如表4所示。

表4 跳出準(zhǔn)則合理性試驗結(jié)果Table 4 Out of the criterion rationality test results

表5 新增進攻飛行器參數(shù)Table 5 Adding parameters of attacking aircraft

由上面試驗結(jié)果可以看出,隨著間隔代數(shù)的增加,算法執(zhí)行所花費的時間就越多,當(dāng)間隔代數(shù)設(shè)置為7時,算法平均收斂時間為0.168 9 s;同時,間隔代數(shù)增加也意味著算法計算結(jié)果更好,綜合時間開銷與計算結(jié)果準(zhǔn)確性的平衡,可以取間隔代數(shù)為15。

3.3 仿真試驗3

設(shè)置一個額外的進攻飛行器,模擬一個在目標(biāo)分配算法運行途中突然發(fā)現(xiàn)新的目標(biāo)需要進行計算的場景。原場景與上面仿真場景相同,在算法迭代次數(shù)為75時,發(fā)現(xiàn)了一個新的目標(biāo),則此時的目標(biāo)分配場景變?yōu)?0枚攔截器分配給9枚進攻飛行器的場景。

仿真結(jié)果如圖6所示。圖中對比了算法執(zhí)行途中加入新進攻飛行器與不加新進攻飛行器的最優(yōu)適應(yīng)度。其中紅色實線代表原改進粒子群優(yōu)化算法的適應(yīng)度變化曲線,藍色虛線代表新增進攻飛行器的改進粒子群優(yōu)化算法的最優(yōu)適應(yīng)度變化曲線。由圖中曲線可以看出,在迭代次數(shù)為75之前,兩次仿真變化趨勢基本一致并且收斂到同一個最優(yōu)適應(yīng)度;迭代次數(shù)為75時,由于新增了一架進攻飛行器,目標(biāo)分配算法將基于之前的計算結(jié)果進行粒子元素擴充,在改進粒子群優(yōu)化算法的作用下,適應(yīng)度值快速增加,對應(yīng)的目標(biāo)分配結(jié)果也產(chǎn)生了變化,結(jié)果如圖4所示。由圖4曲線可以看出,中途出現(xiàn)任務(wù)變化時,算法可以在利用原計算結(jié)果的基礎(chǔ)上繼續(xù)進行計算,不用重新設(shè)定場景重新計算,節(jié)省了大量的算力。

圖4 試驗3最優(yōu)適應(yīng)度變化曲線Fig.4 Experiment 3 optimal fitness curve

4 結(jié)論

文中主要針對多飛行器攔截過程中的目標(biāo)分配問題進行了算法設(shè)計和仿真分析,通過設(shè)計一種改進粒子群優(yōu)化算法解決了一般離散粒子群優(yōu)化算法容易陷入局部收斂的問題,同時通過設(shè)計適應(yīng)度函數(shù)模型確保連續(xù)收斂的算法最終能夠收斂到離散的點,并滿足目標(biāo)分配的約束條件。經(jīng)過仿真分析證明文中設(shè)計的改進粒子群優(yōu)化算法能夠收斂到滿足分配約束的粒子位置,且相對傳統(tǒng)算法分配效能提高了9.4%,收斂結(jié)果與全局最優(yōu)偏差不超過0.1%。

考慮到文中算法中,變鄰域搜索接入方式為在PSO算法收斂后間隔指定代數(shù)串行參與計算,導(dǎo)致算法計算效率相較PSO算法有所降低。未來研究可考慮變鄰域算法的并行同步計算,進一步提高算法效率。