基于MODPSO-GSA的協同空戰武器目標分配

顧佼佼，趙建軍*，顏驥，陳學東

(1.海軍航空工程學院 科研部，煙臺264001;2.91352部隊，威海264208)

超視距協同空戰是現代空戰的主要形式，現代戰機均具備多目標攻擊能力，各戰斗機通過相互協作，對空中多目標實施攻擊.若不涉及作戰戰術，協同空戰的核心問題為交戰階段的協同多目標分配，使我方對敵機群的攻擊效果達到最優.

文獻［1-2］對目前解決武器目標分配(WTA)問題的國內外研究現狀進行了分析和展望:現有模型多是基于單純的以毀傷概率越大(或剩余威脅越小)越好為準則，只考慮盡量提高殺傷效果，一次性完全分配不符合現代空戰火力動態分配的實際.空戰是多階段的攻防過程，在進行武器目標分配時，要考慮在滿足毀傷概率的前提下減少火力資源消耗，以備后期作戰.文獻［3］考慮到這個問題并提出改進，在原有目標函數上附加新的約束變量，構造一個綜合的目標函數，仍是單目標決策.武器目標分配是一個多約束多變量的組合優化問題，構造一個目標函數形式復雜、求解復雜度偏高、不具備直觀性且難以滿足實時性等需求.

本文基于多目標決策理論構造目標分配模型并用進化多目標優化算法［4］求解，同時考慮殺傷效果和火力資源消耗，可在滿足毀傷門限的前提下為指揮員提供不同耗彈量下的最優分配方案集供決策參考.模型的求解采用多目標混合離散粒子群-引力搜索算法(MODPSO-GSA)，展現了良好的尋優能力.仿真驗證了該模型及其求解算法的有效性.

1 基于多目標決策的目標分配建模

某次空戰，我方機群B由M架戰機組成，B={i，i=1，2，…，M}，掛載導彈總數為 K，導彈集合為 A={A1，A2，…，Ar，…，AK};敵方機群 R 由 N 架飛機組成，R={j，j=1，2，…，N}.

文中基于多目標決策理論［5］構建 WTA模型，選取一次目標分配后敵方機群總期望剩余態勢優勢最小［6］和一次分配我方消耗導彈數量最小為兩個目標函數，構造多目標決策函數為

式中，E(π)為第1個目標函數;N(π)為第2個目標函數，以避免造成過度殺傷和火力浪費;Ω為導彈-目標分配空間;導彈集A中導彈Ar攻擊敵機Rj為 Ar→Rj，對敵機 Rj的摧毀概率為 drRj;XrRj為二值函數，如式(2)所示;第1個約束表示毀傷門限［3］以保證分配方案π對目標的最低殺傷;KRj表示第j個目標的毀傷門限，可根據戰場態勢等具體任務需要由指揮員制定;第2個約束表示每枚導彈只能攻擊1個目標.

2 進化多目標優化算法

2.1 多目標決策理論

多目標優化問題(MOPs)指目標函數多于1個且需同時處理的問題.多目標決策與單目標決策最大的不同在于解的尋優用Pareto占優進行度量，即“支配”關系，會同時存在多個Pareto非支配解，構成 Pareto最優解集(Pareto-optimal set)［4］.為便于后續討論給出定義如下.

定義1 Pareto占優.πA，πB∈Ω 是所求多目標函數的兩個可行解，稱與πB相比，πA是Pareto占優的，當且僅當

定義2 Pareto最優解.一個解π*∈Ω被稱為Pareto最優解，當且僅當

Pareto最優解的集合為Pareto最優解集P*.

定義3 Pareto前沿.Pareto最優解集 P*中的解對應目標值組成的曲面稱為 Pareto前沿F*:

2.2 進化多目標優化算法

進化多目標優化(EMO)通過在代與代之間維持由潛在解組成的種群來實現全局搜索.這種方法對于搜索Pareto最優解集是非常有效的，一些新穎的多目標優化算法相繼提出［7］.

EMO用基于支配關系的比較機制評價解的優劣，Pareto最優解集需設置一個外部種群保存.此類問題不僅要考慮解的收斂性，還要考慮解分布的均勻性，以保證解的多樣性，一般用自適應網格機制［4］，將外部種群按照目標函數空間均勻地劃分為網格.在刪除個體時，含有較多個體的網格中的粒子賦予較高選中概率;在選取個體作為進化種群的全局最優時，含有較少個體的網格中粒子賦予較高概率，基于轉盤賭方式進行選擇.

3 基于MODPSO-GSA的模型求解

文中分別采用多目標離散粒子群優化(MODPSO)、多目標引力搜索算法(MOGSA)及多目標離散粒子群-引力搜索算法MODPSO-GSA實現WTA模型求解.

3.1 基于MODPSO的模型求解

求解WTA問題的單目標離散粒子群(DPSO)算法可參見文獻［3，8-9］.在具體 WTA問題上，MODPSO用粒子位置代表一組分配方案，粒子位置矢量為 X=［X1，X2，…，XK］，K 為待分配導彈數量;粒子速度矢量為 V=［v1，v2，…，vK］.粒子按式(6)更新速度及位置:

式中，t為迭代次數;c1和c2為學習因子;r1和r2為(0，1)之間的隨機數;w為慣性權重;pbesti為粒子i搜索到的最優位置;prep為基于轉盤賭從外部種群選取的Pareto占優解來引導尋優.

3.2 基于MOGSA的模型求解

引力搜索算法(GSA)是一種基于萬有引力定律尋優的智能優化算法，算法將每個可能解視為在空間中有質量的個體，質量越大代表越優的位置，個體之間基于牛頓定律，通過萬有引力作用相互吸引產生運動，引導群體向最優解區域搜索［10］.圖1給出了 M2，M3，M4均對 M1產生引力作用.

圖1 個體之間引力相互作用構造合力F1Fig.1 Resultant force F1from other masses

GSA具有良好的全局尋優能力［11-13］，尚未應用在WTA問題.此處對GSA簡略介紹，可參見文獻［10］.單目標GSA主要步驟如下:

1)初始化.由N個個體組成搜索群體，搜索空間為K維，個體i位置定義為

2)計算個體質量Mi(t).

3)計算個體j對個體i的引力Fij(t).

4)計算個體j對個體i的引力加速度aij(t).

其中，Xi表示個體i的位置;Rij(t)表示Xi與Xj之間的歐式距離;ε表示最小門限，防止分母為0;G(t)表示此時的引力常數，以控制迭代步長.

5)根據牛頓運動定律，計算合力加速度如式(9)所示，控制變量Kbest隨時間遞減，表示只有前Kbest個適應值最好的個體產生引力，控制算法收斂到最優解;randj為隨機數.個體的速度及位置更新如式(10)所示.

6)若沒達到迭代次數，轉步驟2);否則停止計算.

MOGSA多目標優化改進采用基于支配關系的比較機制和基于自適應網格的外部種群.主要是如何在兩個目標函數與個體單一質量之間建立對應關系，此處參考NSGA-II根據個體間非支配關系為個體分級［14］來定義個體質量:定義不被其他個體支配的個體集合rank=1，只被一個個體支配的個體集合定義rank=2，以此類推.如下所示為非支配關系分級偽代碼，其中rank=1的個體集合就是Pareto最優解.

對于進化種群中的粒子p定義集合DomSetp存放被該粒子支配的粒子，變量DomedNump記錄該粒子被支配的次數.如果一個粒子被支配次數為0，則該粒子 rankp=1，該粒子集合記為 S1.對于第i等級的粒子集合Si中的粒子p，它所支配的粒子集合DomSetp中的每個粒子q的Domed-Numq減1后DomedNumq=0，則說明q只被粒子p支配，粒子q等級為i+1，存入i+1等級的粒子集合Fi+1，以此類推完成非支配分級.

3.3 基于MODPSO-GSA的模型求解

MODPSO收斂速度快，但易早熟收斂;MOGSA表現出良好的求解空間探索(exploration)能力，但缺乏有效加速機制［13］.文中將二者結合，用一種協同進化的形式［15］:將PSO算法速度更新中的“社會(social)部分”(即gbest)與GSA的加速度結合起來，混合算法的速度更新如式(11)所示.

式中，ai(t)表示MOGSA構造的加速度;VMax表示粒子速度限定;XMin，XMax分別表示位置的最大最小限定;其余變量與式(6)中變量意義相同.

在迭代過程中可能會產生“非法”個體，如分配中遺漏敵機或分配過多導彈攻擊同一目標.算法中引入局部調整adjustX:對分配方案中超過殺傷概率的目標嘗試刪除冗余分配;對于未達到毀傷概率的目標盡量彌補，從未分配導彈中選擇對于該目標毀傷概率最大的導彈分配給該目標.MOPSOGSA算法結構流程如圖2所示.

圖2 MODPSOGSA算法流程圖Fig.2 Procedure of MOPSOGSA

4 算例仿真及分析

為驗證模型及求解算法有效性，采用文獻［3］中算例進行仿真，我方編隊由4架戰機組成，每架戰機掛載4枚導彈;敵機編隊由10架飛機組成.各目標的毀傷概率門限可由指揮員進行設定，仿真中KRj均設為0.9.敵機的威脅權重矩陣dRB=［0.6，0.7，0.3，0.5，0.6，0.35，0.65，0.55，0.4，0.75］.經評估我導彈對目標的毀傷概率矩陣［3］如式(12)所示.

仿真時用文中提出的WTA模型建模，并同時用 NSGA-II［16］，MODPSO，MOGSA 及 MODPSOGSA這4種算法對該算例進行求解.進化種群規模均設置為60，迭代次數為100.NSGA-II中進化種群與外部種群是合一的，采用二元競賽圖選擇算子，交叉概率 Pc=0.8，變異概率 Pm=0.3;MODPSO，MOGSA，MODPSO-GSA的外部種群設置數量門限為10，網格設置為10×10.MODPSO中基本單目標參數設置參見文獻［3］，MODPSOGSA采用MODPSO和MOGSA中的參數設置.

仿真結果如圖3所示，橫坐標E(π)表示目標函數1;縱坐標N(π)表示目標函數2，直線為各算法尋到的Pareto最優解.NSGA-II收斂于尋到的Pareto最優解集;MODPSO尋到的Pareto最優解如圖中連線所示，進化種群如圖中點集所示;MOGSA迭代后基本收斂到Pareto最優解集;MODPSO-GSA尋到的Pareto最優解集如圖中連線所示，進化種群多樣性仍較好.由圖可知，MODPSO-GSA具備較好的尋優能力且粒子多樣性得到了保持.4種算法尋到的Pareto最優解比較如圖 4所示，MODPSO-GSA具備最佳尋優性能.

圖3 4種算法迭代結束狀態Fig.3 Last states of four algorithms

圖4 4種算法迭代結果比較Fig.4 Overall results of four algorithms

仿真可知:①耗彈量為13和14的分配方案是每種多目標優化算法都能尋到的穩定分配，也是其他WTA 算法［1，3］尋到的最優分配，證明了多目標優化的有效性;②多目標優化算法可一次運行尋得不同耗彈量下的多個最優目標分配方案，達到預設的目標毀傷概率，指揮員可根據空戰態勢進行分配方案優選，這更符合空戰實際情況;③MODPSO-GSA保持了粒子群算法的快速尋優能力，尋優性能是穩定的并優于其他算法.

圖5是MODPSO-GSA尋到的4個分配方案及達到的毀傷效果，圖中標示了每個分配方案的敵總期望剩余威脅和我方用彈量.4種方案均是可行分配，指揮員可根據不同的戰場態勢進行決策.

4種多目標優化算法各運行20次取平均性能如表1所示，MODPSO-GSA具備相對最好的綜合性能.

圖5 不同耗彈量下的毀傷效果及分配方案Fig.5 Killing probability and weapon-target assignment(WTA)for varied missiles used

表1 平均性能對比Table1 Comparison of average performance

5 結論

1)構建多目標決策模型，選取對敵殺傷效果最大和消耗火力資源最小作為決策目標，提出新的目標分配模型，模型具備直觀性.

2)提出基于混合離散粒子群-引力搜索的多目標優化算法求解所建多目標決策模型，展現了良好的尋優能力.

3)進化多目標優化的優勢在于一次運行可得到多個Pareto最優解，在文中模型可在滿足毀傷門限的前提下，尋到多個不同耗彈量下的最優分配方案，指揮員可根據不同空戰態勢決策優先，具備實戰意義.

4)文中所提多目標優化算法屬集中式WTA方式，對通信及指控中心依賴性強，當空戰態勢劇烈變化或通信質量難以保證時仍有待改進.

References)

［1］ 劉傳波，邱志明，吳玲，等.動態武器目標分配問題的研究現狀與展望［J］.電光與控制，2010，17(11):43-47.Liu C B，Qiu Z M，Wu L，et al.Review on current status and prospect of researches on dynamic weapon target assignment［J］.Electronics Optics ＆ Control，2010，17(11):43-47(in Chinese).

［2］ 陳閩.編隊協同作戰目標分配建模綜述［J］.電光與控制，2013，20(9):53-63.Chin M.A survey on modeling of target allocation for formation cooperative combat［J］.Electronics Optics ＆ Control，2013，20(9):53-63(in Chinese).

［3］ 李儼，董玉娜.基于SA-DPSO混合優化算法的協同空戰火力分配［J］.航空學報，2010，31(3):626-631.Li Y，Dong Y N.Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat［J］.Acta Aeronautica et Astronautica Sinca，2010，31(3):626-631(in Chinese).

［4］ 公茂果，焦李成，楊咚咚，等.進化多目標優化算法研究［J］.軟件學報，2009，20(2):271-289.Gong M G，Jiao L C，Yang D D，et al.Evolutionary multi-objective optimization algorithms［J］.Journal of Software，2009，20(2):271-289(in Chinese).

［5］ 岳超源.決策理論與方法［M］.北京:科學出版社，2006:151-169.Yue C Y.Decision theory and methods［M］.Beijing:Science Press，2006:151-169(in Chinese).

［6］ 段海濱.蟻群算法原理及其應用［M］.北京:科學出版社，2006:312-317.Duan H B.Ant colony algorithms:theory and applications［M］.Beijing:Science Press，2006:312-317(in Chinese).

［7］ Coello C C，Veldhuizen V D，Lamont G.Evolutionary algorithms for solving multi-objective problems［M］.2nd ed.New York:Springer-Verlag，2007:1-10.

［8］ 段海濱，張翔銀，徐春芳.仿生智能計算［M］.北京:科學出版社，2011:63-85.Duan H B，Zhang X Y，Xu C F.Bio-inspired computing［M］.Beijing:Science Press，2011:63-85(in Chinese).

［9］ 郭文忠，陳國龍.離散粒子群優化算法及其應用［M］.北京:清華大學出版社，2012:13-16.Guo W Z，Chen G L.Discrete particle swarm optimization algorithm and its application［M］.Beijing:Tsinghua University Press，2012:13-16(in Chinese).

［10］ Esmat R，Hossein N，Saeid S.GSA:a gravitational search algorithm［J］.Information Sciences，2009，179(13):2232-2248.

［11］ 楊晶，黎放，狄鵬.免疫萬有引力搜索算法的研究與仿真［J］.兵工學報，2012，33(12):1533-1538.Yang J，Li F，Di P.Research and simulation for the gravitational search algorithms with immunity［J］.Acta Armamentarh，2012，33(12):1533-1538(in Chinese).

［12］ 谷文祥，李向濤，朱磊，等.求解流水線調度問題的萬有引力搜索算法［J］.智能系統學報，2010，5(5):411-418.Gu W X，Li X T，Zhu L，et al.A gravitational search algorithm for flow shop scheduling［J］.CAAI Transactions on Intelligent Systems，2010，5(5):411-418(in Chinese).

［13］ 李沛，段海濱.基于改進萬有引力搜索算法的無人機航路規劃［J］.中國科學:技術科學，2012，42(10):1130-1136.Li P，Duan H B.Path planning of unmanned aerial vehicle based on improved gravitational search algorithm［J］.Scientia Sinica Technologica，2012，42(10):1130-1136(in Chinese).

［14］ Hadi N，Mahdi N，Patrick S.A multi-objective gravitational search algorithm based on non-dominated sorting［J］.International Journal of Swarm Intelligence Research，2012，3(3):32-49.

［15］ Seyedali M，Siti Z M H.A new hybrid PSOGSA algorithm for function optimization［C］//International Conference on Computer and Information Application.Piscataway，NJ:IEEE，2010:374-377.

［16］ Kalyanmoy D，Amrit P，Sameer A，et al.A fast elitist multi-objective genetic algorithm:NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6(2):182-197.