基于粒子群算法的多攔截器分配優化策略*

李瑞康 史秉政 張 召 荊武興

1.上海機電工程研究所，上海201109 2.哈爾濱工業大學，哈爾濱150001

?

基于粒子群算法的多攔截器分配優化策略*

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

1.上海機電工程研究所，上海201109 2.哈爾濱工業大學，哈爾濱150001

研究了大氣層外攔截多目標分配策略。基于目標威脅度和攔截有效程度建立目標分配模型，設計了一種基于粒子群算法的目標分配策略，針對算法存在的缺陷，利用遺傳算法交叉思想對粒子更新策略進行了改進，并對其性能進行了數值仿真分析。結果表明，改進的算法能有效克服基本粒子群算法的弱點，具有收斂性快、穩定性好的特點，沒有出現優化退化現象且對不同攔截場景具有較強適應能力。 關鍵詞 多攔截器；目標分配策略；遺傳算法；粒子群算法

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

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

與傳統防空領域面對的作戰環境不同，本文研究了彈道導彈中段攔截中WTA策略問題，需要考慮非合作、大相對速度及多攔截數量等因素，要求目標分配策略具有快速性和穩定性。本文嘗試利用粒子群算法設計分配策略，并對其進行了改進，以提高分配性能，通過與遺傳算法分配結果[11]比較，改進后的分配算法顯示出更優的綜合性能。

1 多攔截器目標分配模型

假設我方有m個子攔截器，現探測到n個來襲目標，并對其進行攔截。現規定： 1)每個子攔截器只能攔截1個目標； 2)每個目標可分配給任何子攔截器，但不同子攔截器攔截同一目標的攔截有效程度不同。

設計決策變量：

(1)

則目標分配基本優化模型為[11]：

(2)

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

目標威脅程度Wj可以通過運動、紅外和電磁等特征進行評估，攔截有效程度Pij通過零控脫靶量的相對量進行評估，可參閱相關文獻，不再贅述，性能評估時認為Wj和Pij是已知。

2 基于粒子群算法的目標分配實現

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

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

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

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

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

(3)

(4)

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

(5)

式中：ωmax，ωmin為慣性權值最大、最小值；iter為當前迭代次數，itermax為總的迭代次數。

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

均勻設計表的構造方法比較多，好格子點法被廣泛使用，該方法能產生試驗數和水平數為n、列數為m(m是n的歐拉數)的設計表，其構造方法如下：

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

2)均勻設計表的第i列元素為

uij=jhi[modn]

(6)

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

uij可以遞推生成：

uij=hi,

(7)

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

CD2(P)=

(8)

從均勻設計表Un(nm)中選取s列來構成試驗方案，要使試驗方案的中心化L2-偏差(即CD2)最小。

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

假設MKV和目標數量均為20個，每個目標的威脅度為：

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)

每個MKV對每個目標的攔截有效程度為

P=[Pij]20×20

(10)

本文假設P是給定的，下同。

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

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

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

3 粒子更新策略

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

令P1表示當前解，P2表示個體極值和全局極值，具體策略如下：

交叉策略：

1)隨機產生一個交叉點；

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

變異策略：

1)隨機產生變異點和變異值；

2)將P1上與變異值相同的首個基因用變異點處的基因替換；

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

4 仿真算例分析

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

圖2 改進粒子群目標分配方案(m=n)

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

仿真結果說明，在攔截器與目標數不對等的情況下，設計的目標分配算法仍然有效，說明算法具有較好的適應性。

圖3 改進粒子群目標分配方案(m≠n)

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

圖4 適應度函數F(V)變化曲線(m=n，單次結果)

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

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

5 結論

嘗試利用粒子群算法解決多攔截任務分配問題，針對原始粒子群算法容易陷入局部最優，分配效果不佳的問題，本文利用遺傳算法的交叉思想對粒子更新策略進行了改進，仿真結果顯示，改進后的算法取得了更好的優化結果，與遺傳算法相比，改進后的算法具有更強的穩定性，沒有出現優化退化問題，在計算量方面，改進算法略大于遺傳算法，但是在優化結果上遠好于遺傳算法，綜合計算量和優化效果，改進粒子群算法顯示出較好的性能，說明本文選擇和設計的優化算法是有效的，具有一定的參考價值，后續將進一步考慮對分配時效性以及目標存在轉移等不確定因素下的動態分配策略設計問題。

[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] 李勇君, 黃卓, 郭波.武器-目標分配問題綜述[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混合優化算法的協同空戰火力分配[J].航空學報, 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] 顧佼佼, 趙建軍, 顏驥, 陳學東.基于MODPSO-GSA的協同空戰武器目標分配[J].北京航空航天大學學報, 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] 麻士東, 龔光紅, 韓亮.目標分配的蟻群-模擬退火算法及其改進[J].系統工程與電子技術, 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] 張春美, 陳杰, 辛斌.武器目標分配問題的離散差分進化算法[J].北京理工大學學報, 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] 劉傳波, 丘志明, 吳玲.動態武器目標分配問題的研究現狀與展望[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] 馬亞邦.大氣層外多攔截器協同反導任務若干問題研究[D]. 哈爾濱工業大學碩士學位論文, 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.)

北京航天自動控制研究所牽手曼徹斯特大學共建聯合實驗室

2016年3月16日，北京航天自動控制研究所與英國曼徹斯特大學在英國簽署了中英先進控制系統技術聯合實驗室合作協議，標志著北京航天自動控制研究所首家海外研發機構正式成立。

自2015年啟動聯合實驗室建設工作以來，在集團和院領導的關懷下，在有關部門和單位的大力支持下，中英雙方通過講學交流和互訪等方式增進了解，圍繞深化合作進行了多輪次洽談，對聯合實驗室的研究方向、運行模式、知識產權歸屬等進行廣泛討論，并就合作協議達成一致。

據悉，該聯合實驗室后續將聯合開展先進控制技術研發、成果轉化和學術交流，同時作為創新人才培養的前沿陣地與窗口，還將聯合國內外優勢資源，吸納國際先進智力成果，培養國際化的優秀創新人才，推進多學科的交叉融合，進一步促進航天控制技術的整體發展。(王 森)

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-)，男，江西瑞金人，博士，高級工程師，主要研究方向為系統建模、導彈動力學與控制；史秉政(1984-)，男，太原人，工程師，主要研究方向為指揮控制系統；張 召(1989-)，男，河北河間人，碩士研究生，主要研究方向為飛行動力學與控制；荊武興(1965-)，男，河南鹿邑人，博士生導師，主要從事空間飛行器動力學與控制、系統辨識、非線性制導及自主導航等方面的科研與教學工作。

V448.2

A

1006-3242(2016)02-0066-05

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