基于粒子群算法的多攔截器分配優(yōu)化策略*

李瑞康 史秉政 張 召 荊武興

1.上海機(jī)電工程研究所，上海201109 2.哈爾濱工業(yè)大學(xué)，哈爾濱150001

?

基于粒子群算法的多攔截器分配優(yōu)化策略*

李瑞康1史秉政1張 召2荊武興2

1.上海機(jī)電工程研究所，上海201109 2.哈爾濱工業(yè)大學(xué)，哈爾濱150001

研究了大氣層外攔截多目標(biāo)分配策略?；谀繕?biāo)威脅度和攔截有效程度建立目標(biāo)分配模型，設(shè)計(jì)了一種基于粒子群算法的目標(biāo)分配策略，針對算法存在的缺陷，利用遺傳算法交叉思想對粒子更新策略進(jìn)行了改進(jìn)，并對其性能進(jìn)行了數(shù)值仿真分析。結(jié)果表明，改進(jìn)的算法能有效克服基本粒子群算法的弱點(diǎn)，具有收斂性快、穩(wěn)定性好的特點(diǎn)，沒有出現(xiàn)優(yōu)化退化現(xiàn)象且對不同攔截場景具有較強(qiáng)適應(yīng)能力。 關(guān)鍵詞 多攔截器；目標(biāo)分配策略；遺傳算法；粒子群算法

為了克服彈道導(dǎo)彈中段攔截過程中多目標(biāo)識別難題，美國提出一種MKV(MKV，Multiple Kill Vehicle)技術(shù)，它通過運(yùn)載器將一個(gè)攜帶多個(gè)微小型攔截器的母艙送至指定位置，對一定范圍內(nèi)所有威脅目標(biāo)實(shí)施有效殺傷[1]。殺傷過程中對攔截器進(jìn)行目標(biāo)分配是研究工作的重點(diǎn)之一，武器-目標(biāo)分配(WTA，Weapon-Target Assignment)問題在當(dāng)今作戰(zhàn)決策和火力運(yùn)用中具有重要地位。

WTA問題主要包括分配建模和分配算法設(shè)計(jì)2大部分[2-3]。面對日益復(fù)雜的戰(zhàn)場環(huán)境，對目標(biāo)分配策略的研究經(jīng)歷了傳統(tǒng)算法到智能算法、靜態(tài)分配到動態(tài)分配的過程[4-10]。在算法設(shè)計(jì)方面，文獻(xiàn)[4-5]分別采用不同粒子群混合算法對空戰(zhàn)中合作目標(biāo)攔截火力進(jìn)行分配設(shè)計(jì)，取得了較好的效果，其他的一些智能方法，如蟻群、模糊及離散差分等在解決某一特定問題上也得到了較好的研究[6-8]，體現(xiàn)了智能算法在復(fù)雜戰(zhàn)場環(huán)境下的設(shè)計(jì)優(yōu)勢。此外，動態(tài)武器-目標(biāo)分配(DWTA，Dynamic Weapon-Target Assignment)問題也逐漸得到研究[9-10]，但相對靜態(tài)分配問題，需要考慮時(shí)間和隨機(jī)因素影響，求解更加復(fù)雜，目前更多處于探索階段，成果并不多見。

與傳統(tǒng)防空領(lǐng)域面對的作戰(zhàn)環(huán)境不同，本文研究了彈道導(dǎo)彈中段攔截中WTA策略問題，需要考慮非合作、大相對速度及多攔截?cái)?shù)量等因素，要求目標(biāo)分配策略具有快速性和穩(wěn)定性。本文嘗試?yán)昧Ｗ尤核惴ㄔO(shè)計(jì)分配策略，并對其進(jìn)行了改進(jìn)，以提高分配性能，通過與遺傳算法分配結(jié)果[11]比較，改進(jìn)后的分配算法顯示出更優(yōu)的綜合性能。

1 多攔截器目標(biāo)分配模型

假設(shè)我方有m個(gè)子攔截器，現(xiàn)探測到n個(gè)來襲目標(biāo)，并對其進(jìn)行攔截?，F(xiàn)規(guī)定： 1)每個(gè)子攔截器只能攔截1個(gè)目標(biāo)； 2)每個(gè)目標(biāo)可分配給任何子攔截器，但不同子攔截器攔截同一目標(biāo)的攔截有效程度不同。

設(shè)計(jì)決策變量：

(1)

則目標(biāo)分配基本優(yōu)化模型為[11]：

(2)

其中：F(V)為性能函數(shù)，Wj為第j個(gè)目標(biāo)的威脅程度，Pij為第i個(gè)子攔截器攔截第j個(gè)目標(biāo)的攔截有效程度。

目標(biāo)威脅程度Wj可以通過運(yùn)動、紅外和電磁等特征進(jìn)行評估，攔截有效程度Pij通過零控脫靶量的相對量進(jìn)行評估，可參閱相關(guān)文獻(xiàn)，不再贅述，性能評估時(shí)認(rèn)為Wj和Pij是已知。

2 基于粒子群算法的目標(biāo)分配實(shí)現(xiàn)

粒子群算法(PSA, Particle Swarm Algorithm)基本概念源于對鳥群覓食行為的研究，它從生物種群行為特性中得到啟發(fā)并用于求解最優(yōu)化問題。在粒子群算法中，每個(gè)優(yōu)化問題都可以想象成d維搜索空間上的一個(gè)點(diǎn)，稱之為“粒子”，所有的粒子都有一個(gè)被目標(biāo)函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定其飛翔的方向和距離，然后其他粒子“追隨”當(dāng)前的最優(yōu)粒子在解空間搜索。

由n個(gè)粒子組成的群體對Q維空間進(jìn)行搜索，每個(gè)粒子表示為：Xi=(Xi1,Xi2,...,XiQ)，i=1,2,...,n，每個(gè)粒子對應(yīng)的速度可以表示為vi=(vi1,vi2,...,viQ)，每個(gè)粒子在搜索時(shí)要考慮以下2個(gè)因素：

1)自己搜索到的歷史最優(yōu)值pi，pi=(pi1,pi2,...,piQ)；

2)全部粒子搜索到的最優(yōu)值pg，pg=(pg1,pg2,...,pgQ)，注意這里的pg只有一個(gè)。

粒子群算法的位置速度更新公式如下：

(3)

(4)

其中：ω是保持原來速度的系數(shù)，稱為慣性權(quán)重；c1是粒子跟蹤自己歷史最優(yōu)值的權(quán)重系數(shù)，表示粒子自身的認(rèn)識，稱為“認(rèn)知”，通常取2；c2是粒子跟蹤群體最優(yōu)值的權(quán)重系數(shù)，表示粒子對整個(gè)群體的認(rèn)識，稱為“社會認(rèn)知”或“社會”，通常取2；ξ，η是[0,1]內(nèi)均勻分布隨機(jī)數(shù)；系數(shù)r稱為約束因子。

(5)

式中：ωmax，ωmin為慣性權(quán)值最大、最小值；iter為當(dāng)前迭代次數(shù)，itermax為總的迭代次數(shù)。

提高初始種群對設(shè)計(jì)空間的覆蓋性(即種群能全面的表征設(shè)計(jì)空間)有利于提高粒子群多樣性和算法搜索效率。本文將應(yīng)用均勻設(shè)計(jì)對粒子群算法的粒子種群進(jìn)行初始化。

均勻設(shè)計(jì)表的構(gòu)造方法比較多，好格子點(diǎn)法被廣泛使用，該方法能產(chǎn)生試驗(yàn)數(shù)和水平數(shù)為n、列數(shù)為m(m是n的歐拉數(shù))的設(shè)計(jì)表，其構(gòu)造方法如下：

1)給定試驗(yàn)數(shù)n，找比n小的正整數(shù)h，要使n與h的最大公約數(shù)為1，將符合條件的正整數(shù)組成列向量h=[h1h2…h(huán)m]T；

2)均勻設(shè)計(jì)表的第i列元素為

uij=jhi[modn]

(6)

式中：[modn]表示同余運(yùn)算后取整，如果jhi大于n，則其要減去n的一個(gè)合適倍數(shù)，使差落在[1,n]之間。

uij可以遞推生成：

uij=hi,

(7)

式中：i=1,...,n,j=1,...,m。

CD2(P)=

(8)

從均勻設(shè)計(jì)表Un(nm)中選取s列來構(gòu)成試驗(yàn)方案，要使試驗(yàn)方案的中心化L2-偏差(即CD2)最小。

粒子群算法的本質(zhì)是利用個(gè)體極值和全局極值2個(gè)信息，來指導(dǎo)粒子下一步迭代位置。對于 WTA問題，其解用矩陣表示，為了簡化問題，采用十進(jìn)制編碼方式，每個(gè)粒子長度與攔截器所攜帶的MKV數(shù)目相等，這樣每個(gè)粒子對應(yīng)一種分配方案，如[5 3 4 1 2]表示將目標(biāo)5分配給MKV_1,目標(biāo)3分配給MKV_2，依次類推，這樣做的目的是使每個(gè)攔截器都有目標(biāo)與之對應(yīng)，且形成映射關(guān)系。

假設(shè)MKV和目標(biāo)數(shù)量均為20個(gè)，每個(gè)目標(biāo)的威脅度為：

W=[0.17 0.97 0.76 0.62 0.48 0.970.330.84 0.54 0.25 0.45 0.76 0.43 0.64 0.57

0.12 0.25 0.76 0.84 0.76]

(9)

每個(gè)MKV對每個(gè)目標(biāo)的攔截有效程度為

P=[Pij]20×20

(10)

本文假設(shè)P是給定的，下同。

按照上述推理，直觀想法是對粒子位置向上或向下取整，假設(shè)粒子個(gè)數(shù)為100個(gè)，迭代次數(shù)為400次，得到分配結(jié)果如圖1所示。

從仿真結(jié)果可以看出，一些目標(biāo)未被很好分配，即認(rèn)為不攔截，如序號3，8，19目標(biāo)威脅程度很高，但并未被分配，顯然算法存在不合理之處。這是由于設(shè)計(jì)過程中沒有給優(yōu)化加入約束，僅以適應(yīng)度函數(shù)(目標(biāo)函數(shù)F(V))值最大為目標(biāo)，而適應(yīng)度函數(shù)值是威脅程度W和攔截有效程度P的函數(shù)，當(dāng)攔截有效程度過低時(shí)，即使威脅程度很高也會在優(yōu)化中被舍棄。所以，有必要對粒子群進(jìn)行約束，并加以改進(jìn)。

圖1 基本粒子群目標(biāo)分配方案(m=n)

3 粒子更新策略

對于WTA問題，若按基本粒子群算法，其速度難于表達(dá)，這里引進(jìn)遺傳算法交叉操作思想：讓當(dāng)前所有解與個(gè)體極值和全局極值分別作交叉操作，產(chǎn)生的解為新的位置；針對粒子群算法容易陷入局部最優(yōu)解，且效率不高的問題，考慮遺傳算法中變異操作思想，在經(jīng)過交叉操作后，再進(jìn)行變異操作；同時(shí)，為了避免優(yōu)化過程出現(xiàn)退化現(xiàn)象，在產(chǎn)生新粒子后，加入一步粒子判斷，如果新粒子的適應(yīng)度值小于舊粒子，則不進(jìn)行更新，該個(gè)體仍使用舊粒子。

令P1表示當(dāng)前解，P2表示個(gè)體極值和全局極值，具體策略如下：

交叉策略：

1)隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)；

2)用P2交叉點(diǎn)之后的基因段替換掉P1交叉點(diǎn)后的基因段。

變異策略：

1)隨機(jī)產(chǎn)生變異點(diǎn)和變異值；

2)將P1上與變異值相同的首個(gè)基因用變異點(diǎn)處的基因替換；

3)將P1上變異點(diǎn)處的基因用變異值替換。

4 仿真算例分析

依照上節(jié)給出的粒子更新策略，條件同上，重新對目標(biāo)分配方案進(jìn)行仿真，結(jié)果如圖2所示。從仿真結(jié)果可以看出，分配取得比較合理的效果，說明改進(jìn)后的粒子群算法是有效的。

圖2 改進(jìn)粒子群目標(biāo)分配方案(m=n)

同理，考慮MKV為20個(gè)，目標(biāo)為16個(gè)時(shí)，其它參數(shù)設(shè)置同上(限于篇幅，W,P不再列出)，得到的分配方案如圖3所示。

仿真結(jié)果說明，在攔截器與目標(biāo)數(shù)不對等的情況下，設(shè)計(jì)的目標(biāo)分配算法仍然有效，說明算法具有較好的適應(yīng)性。

圖3 改進(jìn)粒子群目標(biāo)分配方案(m≠n)

假設(shè)MKV與目標(biāo)數(shù)量均為20個(gè)，運(yùn)行單次改進(jìn)粒子群算法與遺傳算法，改進(jìn)粒子群算法中，粒子個(gè)數(shù)為100個(gè)，迭代次數(shù)為400；遺傳算法中個(gè)體數(shù)目為100個(gè)，最大遺傳代數(shù)為400，交叉率取0.7，變異率取0.05，兩種分配算法的適應(yīng)度值變化曲線對比如圖4所示。從圖中可以看出，改進(jìn)粒子群算法獲得的最終適應(yīng)度值為10.59，要大于遺傳算法的10.52，兩者收斂均較為平穩(wěn)，但改進(jìn)粒子群算法在收斂速度上要比遺傳算法快，如迭代50次，改進(jìn)粒子群算法的適應(yīng)度值達(dá)到10.1，達(dá)到最大值的95.4%，而遺傳算法僅為9.7，為最大值的92.2%。在相同配置機(jī)器上，2種算法分別連續(xù)運(yùn)行100次，利用統(tǒng)計(jì)方法對分配性能進(jìn)行對比，遺傳算法總運(yùn)行時(shí)間為209.68s，改進(jìn)粒子群算法為219.96s，相比遺傳算法慢4.9%，得到最終適應(yīng)度值高于10.5的情況，遺傳算法為54次，改進(jìn)粒子群算法為99次，概率分別為0.54和0.99，相比高83.33%。改進(jìn)粒子群算法由于要進(jìn)行交叉操作，在運(yùn)行時(shí)間上劣于遺傳算法，但在收斂速度、穩(wěn)定性上好于遺傳算法。

圖4 適應(yīng)度函數(shù)F(V)變化曲線(m=n，單次結(jié)果)

同理，圖5對比了MKV為20個(gè)、目標(biāo)為16個(gè)時(shí)，改進(jìn)粒子群算法與遺傳算法的結(jié)果對比。從圖中可以看出在彈目數(shù)量不等的情況下，2種算法收斂速度相當(dāng)，但改進(jìn)的粒子群算法具有更優(yōu)的適應(yīng)度值F，為12.3，相比遺傳算法提高了3.4%。將算法連續(xù)運(yùn)行100次得到統(tǒng)計(jì)結(jié)果為：總運(yùn)行時(shí)間，遺傳算法為238.88s，改進(jìn)粒子群算法為240.03s，基本相當(dāng)；適應(yīng)度值F>11.5的次數(shù)，改進(jìn)粒子群算法為100次，遺傳算法為86次，相比增加16.27%。通過對比，改進(jìn)粒子群算法在適應(yīng)性上也優(yōu)于遺傳算法，在獲取更優(yōu)性能的分配結(jié)果上改進(jìn)粒子群算法具有優(yōu)勢。

圖5 適應(yīng)度函數(shù)F(V)變化曲線(m≠n，單次)

5 結(jié)論

嘗試?yán)昧Ｗ尤核惴ń鉀Q多攔截任務(wù)分配問題，針對原始粒子群算法容易陷入局部最優(yōu)，分配效果不佳的問題，本文利用遺傳算法的交叉思想對粒子更新策略進(jìn)行了改進(jìn)，仿真結(jié)果顯示，改進(jìn)后的算法取得了更好的優(yōu)化結(jié)果，與遺傳算法相比，改進(jìn)后的算法具有更強(qiáng)的穩(wěn)定性，沒有出現(xiàn)優(yōu)化退化問題，在計(jì)算量方面，改進(jìn)算法略大于遺傳算法，但是在優(yōu)化結(jié)果上遠(yuǎn)好于遺傳算法，綜合計(jì)算量和優(yōu)化效果，改進(jìn)粒子群算法顯示出較好的性能，說明本文選擇和設(shè)計(jì)的優(yōu)化算法是有效的，具有一定的參考價(jià)值，后續(xù)將進(jìn)一步考慮對分配時(shí)效性以及目標(biāo)存在轉(zhuǎn)移等不確定因素下的動態(tài)分配策略設(shè)計(jì)問題。

[1] Rober W. Future Ballistic Missile Interceptor May Carry Dozens of Kill[J]. Aviation Week&Space Technology, 2004, 160(1):50-57.

[2] Matlin Samuel. Review of the Literature on the Missile Allocation Problem[J]. Operations Research. 1970, 18(3):334-373.

[3] 李勇君, 黃卓, 郭波.武器-目標(biāo)分配問題綜述[J]. 兵工自動化, 2009, 28(11): 1-5.(Li Yong-jun, Huang Zhou, Guo Bo. Review of Weapon-Target Assignment Problem[J]. Ordnance Industry Automation, 2009, 28(11):1-5.)

[4] 李儼, 董玉娜.基于SA-DPSO混合優(yōu)化算法的協(xié)同空戰(zhàn)火力分配[J].航空學(xué)報(bào), 2010, 31(3):626-631. (Li Yan, Dong Yu′na. Weapon-target Assignment Based on Simulated Annealing and Discrete Particle Swarm Optimization in Cooperative Air Combat[J]. Acta Aeronautica Et Astronautica Sinica, 2010,31(3):626-631.)

[5] 顧佼佼, 趙建軍, 顏驥, 陳學(xué)東.基于MODPSO-GSA的協(xié)同空戰(zhàn)武器目標(biāo)分配[J].北京航空航天大學(xué)學(xué)報(bào), 2015, 41(2):252-268. (Gu Jiaojiao, Zhao Jianjun, Yan Ji, Chen Xuedong. Cooperative Weapon-target Assignment Based on Multi-objective Discrete Particle Swarm Optimization-gravitational Search Algorithm in Air Combat[J].Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(2):252-258.)

[6] 麻士東, 龔光紅, 韓亮.目標(biāo)分配的蟻群-模擬退火算法及其改進(jìn)[J].系統(tǒng)工程與電子技術(shù), 2011, 33(5): 1182-1186.(Ma Shidong, Gong Guanghong, Han Liang. Hybrid Strategy with Ant Colony and Simulated Annealing Algorithm and Its Improvement in Target Assignment[J]. Systems Engineering and Electronics. 2011,33(5):1182-1186.)

[7] Mehmet A.S, Kemal L. Approximating the Optimal Mapping for Weapon Target Assignment by Fuzzy Reasoning[J]. Elsevier Information Sciences. 2014, 255:30-44.

[8] 張春美, 陳杰, 辛斌.武器目標(biāo)分配問題的離散差分進(jìn)化算法[J].北京理工大學(xué)學(xué)報(bào), 2014,34(3):289-293. (Zhang Chunmei, Chen Jie, Xin Bin. A Discrete Differential Evolution Algorithm for the Weapon Target Assignment Problem[J]. Transaction of Beijing Institute of Technology, 2014, 34(3):289-293.)

[9] Xin B, Chen J, Zhang J. Efficient Decision Makings for Dynamic Weapon-target Assignment by Virtual Permutation and Tabu Search Heuristics[J]. IEEE Transaction on Systems Man, and Cyber-netics.,Part C: Application and Re-views,2010,40(6):649-662.

[10] 劉傳波, 丘志明, 吳玲.動態(tài)武器目標(biāo)分配問題的研究現(xiàn)狀與展望[J].電光與控制, 2010,17(11):43-48.(Liu Chuanbo, Qiu Zhiming, Wu Ling. Review on Current Status and Prospect of Researches on Dynamic Weapon target Assignment[J]. Electronics Optics & Control, 2010,17(11):43-48.)

[11] 馬亞邦.大氣層外多攔截器協(xié)同反導(dǎo)任務(wù)若干問題研究[D]. 哈爾濱工業(yè)大學(xué)碩士學(xué)位論文, 2013:29-37.(Ma Yabang.Study on Antimissile-Cooperation Problems for Exo-Atmospheric Multiple Kill Vehicle[D]. Master Degree Dissertation of Harbin Institute of Technology, 2013:29-37.)

北京航天自動控制研究所牽手曼徹斯特大學(xué)共建聯(lián)合實(shí)驗(yàn)室

2016年3月16日，北京航天自動控制研究所與英國曼徹斯特大學(xué)在英國簽署了中英先進(jìn)控制系統(tǒng)技術(shù)聯(lián)合實(shí)驗(yàn)室合作協(xié)議，標(biāo)志著北京航天自動控制研究所首家海外研發(fā)機(jī)構(gòu)正式成立。

自2015年啟動聯(lián)合實(shí)驗(yàn)室建設(shè)工作以來，在集團(tuán)和院領(lǐng)導(dǎo)的關(guān)懷下，在有關(guān)部門和單位的大力支持下，中英雙方通過講學(xué)交流和互訪等方式增進(jìn)了解，圍繞深化合作進(jìn)行了多輪次洽談，對聯(lián)合實(shí)驗(yàn)室的研究方向、運(yùn)行模式、知識產(chǎn)權(quán)歸屬等進(jìn)行廣泛討論，并就合作協(xié)議達(dá)成一致。

據(jù)悉，該聯(lián)合實(shí)驗(yàn)室后續(xù)將聯(lián)合開展先進(jìn)控制技術(shù)研發(fā)、成果轉(zhuǎn)化和學(xué)術(shù)交流，同時(shí)作為創(chuàng)新人才培養(yǎng)的前沿陣地與窗口，還將聯(lián)合國內(nèi)外優(yōu)勢資源，吸納國際先進(jìn)智力成果，培養(yǎng)國際化的優(yōu)秀創(chuàng)新人才，推進(jìn)多學(xué)科的交叉融合，進(jìn)一步促進(jìn)航天控制技術(shù)的整體發(fā)展。(王 森)

The Weapon-Target Assignment Optimal Strategy Based on Particle Swam Algorithm in Multiple Kill Vehicle Interceptor

Li Ruikang1，Shi Bingzheng1, Zhang Zhao2, Jing Wuxing2

1.Shanghai Electro-Mechanical Engineering Institute, Shanghai 201109，China 2.Department of Aerospace Engineering, Harbin Institute of Technology, Harbin 150001，China

Theweapon-targetassignment(WTA)strategyprobleminexoatmosphericinterceptsceneisresearchedtoberesolvedinthispaper.Firstly,theobjectivefunctionisestablished,whichisbasedonthetargetthreatandinterceptioneffectiveness.Then,thetargetassignmentstrategyisdesignedbyusingbasicparticleswarmoptimizationalgorithm.Duetothedrawbacksofbasicparticleswarmalgorithm,animprovedparticleswarmoptimizationalgorithmispresentedbyusingthegeneticcrossovertheory.Finally,theimprovedparticleswarmalgorithmsimulationanalysisisimplemented.Thesimulationresultsdemonstratethattheweaknessofthebasicparticleswarmoptimizationalgorithmisovercomeandtheimprovedoptimizationalgorithmhasbetterperformancebycomparingwiththegeneticalgorithminconvergence,stabilityandadaptability.

Multiplekillvehicle;Targetassignmentstrategy;Geneticalgorithm;Particleswarmalgorithm

2015-06-01

李瑞康(1982-)，男，江西瑞金人，博士，高級工程師，主要研究方向?yàn)橄到y(tǒng)建模、導(dǎo)彈動力學(xué)與控制；史秉政(1984-)，男，太原人，工程師，主要研究方向?yàn)橹笓]控制系統(tǒng)；張 召(1989-)，男，河北河間人，碩士研究生，主要研究方向?yàn)轱w行動力學(xué)與控制；荊武興(1965-)，男，河南鹿邑人，博士生導(dǎo)師，主要從事空間飛行器動力學(xué)與控制、系統(tǒng)辨識、非線性制導(dǎo)及自主導(dǎo)航等方面的科研與教學(xué)工作。

V448.2

A

1006-3242(2016)02-0066-05

*上海市科學(xué)技術(shù)委員會資助(13QB1401600)