改進粒子群優化多攔截器目標分配方法研究

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

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

0 引言

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

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

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

1 多攔截器目標分配數學模型

文中目標分配問題建立在如下的條件或假設上:

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

設計目標分配總收益適應度為總的進攻飛行器威脅程度與攔截概率的組合,記為:

(5)

2 改進粒子群優化算法

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

2.1 粒子編碼解碼策略

對于最優目標分配問題,其求解類似于整數規劃問題,而粒子群優化算法的更新是一個連續變化的過程,難以避免出現非整數的解。因此對于連續變化的粒子需要通過合適策略進行編解碼才能匹配問題的解。

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

(6)

因此該優化問題可表示為:

(7)

式中F*表示最優適應度函數。

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

首先,可以明確得知每一種分配結果的適應度值以及分配約束;其次,最優分配對應的分配矩陣元素值為1,而其他值為0。基于上述條件,給出以下引理。

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

證明:考慮適應度函數式(5)與式(3),則

(8)

(9)

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

(10)

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

(11)

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

2.2 引入VNS算法改進策略

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

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

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

1)第一鄰域結構(交換鄰域,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)第二鄰域結構(轉置鄰域,inverted neighborhood):在Λ矩陣中任選第i行,并將該行元素進行對稱轉置,且i=random {1,2,…,M},Λij=Λi(N-j+1),j∈{1,2,…,N},其余部分保持不變。

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

根據以上三種鄰域結構,設計對應鄰域抖動算法。算法設計思路為:針對每一種鄰域結構,設定搜索次數K,在每次搜索中,執行相應變鄰域操作,并將操作前后適應度值進行比較,記錄更優解。

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

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

由上面的分析可以看出,對于一個陷入局部收斂的PSO算法,將一個分配矩陣當作PSO算法中的一個粒子,通過進行上述的操作鄰域就能夠實現收斂局部的廣度搜索,進而增加求得全局最優解的可能性。

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

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

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

3 數值仿真及結果分析

針對提出的改進粒子群優化算法分別設置三組仿真工況:

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

2)通過調整系數驗證啟動準則的有效性。

3)場景變化時的目標分配算法。

設置仿真場景:

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

表1 攔截器參數Table 1 Interceptor parameters

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

表2 目標飛行器參數Table 2 Target vehicle parameters

3.1 仿真試驗1

使用文中設計的改進粒子群優化算法與傳統粒子群優化算法、DPSO算法及貪心算法進行比較,分配結果的適應度函數變化如圖3所示。

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

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

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

表3 目標分配結果Table 3 Target assignment result

3.2 仿真試驗2

驗證改進粒子群優化算法中局部跳出算法啟動準則的合理性。試驗次數為5,試驗結果記錄如表4所示。

表4 跳出準則合理性試驗結果Table 4 Out of the criterion rationality test results

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

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

3.3 仿真試驗3

設置一個額外的進攻飛行器,模擬一個在目標分配算法運行途中突然發現新的目標需要進行計算的場景。原場景與上面仿真場景相同,在算法迭代次數為75時,發現了一個新的目標,則此時的目標分配場景變為10枚攔截器分配給9枚進攻飛行器的場景。

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

圖4 試驗3最優適應度變化曲線Fig.4 Experiment 3 optimal fitness curve

4 結論

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

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