基于離散映射的量子粒子群優化算法求解WTA問題

劉琨　潘翔宇

摘 要： 針對武器目標分配（WTA）問題及其特點， 提出一種基于離散映射的量子粒子群優化算法。 通過武器系統對目標攻擊過程中得到的毀傷收益建立了目標分配模型， 提出一種基于離散映射的編碼調整方式， 將連續型粒子位置矢量投影至離散空間上， 避免產生不滿足模型約束條件的非法解， 從而提高粒子利用率。 通過仿真對比驗證， 論文算法具有較高的收斂速度與穩定性， 表明該方法能有效求解WTA問題。

關鍵詞： 武器目標分配（WTA）； 量子粒子群優化算法； 離散映射； 編碼調整

中圖分類號： TJ760.1； TP18 文獻標識碼： A文章編號： 1673-5048（2018）03-0037-07

0 引 言

武器目標分配（Weapon Target Assignment， WTA）問題是典型的組合優化問題， 旨在求解武器與目標的合理分配組合， 達到己方資源損傷最小化或敵方資源毀傷最大化的目的。 WTA問題本身是一個多參數、 多約束的非確定多項式（Non-Deterministic Polynomial， NP）問題[1]。 目前應用于求解WTA 問題的算法主要有遺傳算法[2-3]、 粒子群優化算法[4]等。 但其在解算的過程中不可避免會產生不滿足約束條件的非法解， 使粒子的利用率較低， 也會增加算法不必要的時間消耗。

基于PSO算法實現簡單及運算耗時短等優點， 使其在求解WTA優化問題得到廣泛應用[4-6]， 文獻[4]與[7]均利用粒子群算法分別采用實數整形與二進制矩陣編碼及一系列改進措施求解多機協同攻擊目標分配問題。 但相關文獻的算法分配模型中同時或部分存在以下不足：（1）算法對模型約束條件處理單純依靠懲罰函數， 無法提高種群粒子利用率； （2）局限于目標個數等于武器個數的目標分配， 缺少對目標個數與武器個數存在差異情況下的相關研究。

因此， 本文提出目標個數大于武器個數與目標個數小于武器個數兩種武器目標分配模型， 同時為提高算法的粒子利用率， 增強算法運算效能， 提出一種基于離散映射的編碼調整方式， 將連續型粒子位置矢量投影至離散空間上， 減少算法求解最優解的迭代次數。

1 武器目標分配模型

1.1 問題描述

為便于研究， 對戰場環境作以下假設：

（1） 假定武器對各目標殺傷概率、 目標威脅參數已知。

1.3 評價函數

評價函數是對智能搜索算法求解優劣的判定函數， 針對編隊對地攻擊任務分配問題， 現階段的研究大多數都以單目標優化模型為求解框架[8-9]。 本文構建了考慮目標剩余價值、 編隊攻擊損耗的多目標優化模型。 為簡化求解難度， 通過線性加權的方法設置合理的權重系數， 將多指標函數轉化為單指標評判函數， 其表達式如下：

2.3 非法解的離散映射處理

整形實數編碼方式易產生不滿足目標方案約束條件的非法解， 本文提出一種基于雙排序離散映射的編碼調整方式， 處理算法迭代運算中產生的非法解， 并對連續性實數編碼進行離散化投影至有效解空間上。

由于約束條件式（7）～（10）規定對每架戰機至多能對兩個目標實施打擊， 因此當2M

步驟1 對更新求解后的粒子位置矢量Popold每個維度按照數值大小由左向右依次排序得到Popsort， 并記錄下Popold和Popsort間的排序映射關系。

步驟7 根據之前保存的Popold和Popsort間的排序映射對應關系， 對Popadapt每一維度位置進行逆映射， 即可得到調整后的粒子位置矢量Popnew。

圖2～3針對武器資源數溢出與目標數溢出兩種武器目標分配情況， 以具體實例描述了基于排序雙映射的離散化編碼調整方式的操作流程。 粒子編碼經過同比例離散化調整結束后， 連續性武器分配矢量被映射到合法解的離散空間上。 非法解的處理可確保進化后的粒子每一維投影至離散空間， 并保證粒子參與算法下一次迭代時保持原有的搜索方向。 基于排序映射的編碼調整方式將提高參與迭代有效解所占種群比例， 大大增強了整個種群的粒子利用率。 相對于利用懲罰函數等傳統處理非法解的方式， 本文設計的編碼調整過程并未對非法解簡單舍棄， 而是對其進行改造， 擴充了有效解的數量與種類。

3 仿真實驗

仿真實驗共設置兩組不同規模的武器目標數。 在兩組仿真中， 分別對攻擊編隊攜帶武器數目大于目標數、 攻擊編隊攜帶目標數小于目標數兩種情況進行仿真分析。 檢驗基于離散映射的量子粒子群優化算法（QuantumBehaved Particle Swarm Optimization Algorithm with Discrete Mapping， DMQPSO）， 求解武器目標分配問題。

通過對比最優適應值變化曲線， 兩組不同規模的武器目標數下DMQPSO算法粒子種群均能以最小迭代次數搜索出全局最優解。 SA-GA算法雖然能夠最終搜尋到全局最優解， 但算法收斂速度緩慢需要迭代次數較多， 消耗時間較DMQPSO算法時間長；基本QPSO算法和PSO算法在20次迭代內收斂速度較快， 甚至在情況2中， QPSO算法最優適應值短時間內優于DMQPSO算法， 但其在搜索求解過程中易陷入局部最優解。

針對算例1仿真50次， 表5統計4種算法收斂至最優解的算法時間， 并對比4種算法在搜索時間上的差異。 DMQPSO在搜索至最優解的算法平均耗時上優于SA-GA與PSO算法， 略遜于QPSO算法， 但QPSO算法易陷于局部最優解， 通過搜索時間對比， DMQPSO算法滿足對目標分配算法實時性的要求。

（2） 增加編隊內戰機數量與目標數量。 情況1： 假設有12部待攻擊雷達T1， T2， …， T12， 攻擊編隊為8架戰機： F1， F2， …， F8。 每架戰機最大武器裝配數設置為Wi=2， i=1， 2， 3， …， 8。 各架戰機對目標的毀傷概率如表6所示， 被擊落概率如表7所示。 情況2： 攻擊目標數目不變但減少編隊戰機數目， 即裁撤編號為6， 7， 8的三架戰機， 其余各架戰機攜帶武器數量、 殺傷概率均與情況1相同。 分別利用DMQPSO算法、 SA-GA算法、 QPSO算法、 PSO算法對上述兩類情況求解最優目標分配方案， 并對4種算法性能進行對比分析， 迭代次數均設置為300。

最優適應值變化情況見圖6～7， 通過比較可以得出： DMQPSO算法粒子種群均能以最小迭代次數搜索出全局最優解； SA-GA算法由于問題規模增大已不能收斂至全局最優； 基本QPSO與PSO算法收斂速度較快， 但易陷入局部最優。 算法運算初期， 4種算法的搜索性能大致相同， 隨著迭代次

數增加， DMQPSO算法收斂性明顯優于其余三種算法。 通過對比觀察可以得出， DMQPSO算法在100次迭代內仍能快速搜尋到全局最優解； SA-GA算法由于問題規模增大已不能收斂至全局最優， 且收斂速度緩慢； 基本QPSO算法在50次迭代內有較強的收斂速度， 即在短時間內搜索到的全局最優適應值甚至會高于DMQPSO算法， 但仍會陷入局部最優； PSO算法在收斂性和全局最優解的搜索精度上與DMQPSO算法有較大差距。

表8中列出最優武器分配方案中， 對分配攻擊目標T1， T3， T4， T5， T7， T9， T11的戰機均是對其毀傷概率最高的戰機且對分配攻擊T1， T3， T5目標的戰機生存概率均最高， 表9中列出的最優武器分配方案中對分配攻擊目標T5， T10， T11的戰機均是對其毀傷概率最高的戰機， 均滿足論文提出的分配最優解判定準則。

針對算例2仿真20次， 表10對提高運算規模后4種算法的搜索時間進行統計對比。 4種算法在運算規模提高后搜索時間均有所有增長， DMQPSO算法搜索最優解平均耗時明顯優于SA-GA算法， 與QPSO與PSO算法相當， 具有良好的實時性。

4 結 論

本文針對QPSO算法求解WTA問題中連續型粒子編碼方式易產生非法解、 影響算法收斂速度及粒子利用率低等問題， 提出一種新的基于離散映射的方法將非法解進行優化處理， 提高粒子種群利用率。 通過對比仿真， 說明改進后的算法具有較高的精度和較快的收斂速度以及良好穩定性， 具有求解較大規模WTA問題的能力， 算法的可行性、 有效性得到了驗證。

參考文獻：

[1] 劉躍峰， 張安. 有人機/無人機編隊協同任務分配方法[J]. 系統工程與電子技術， 2010， 32（3）： 584-588.

Liu Yuefeng， Zhang An.Cooperative Task Assignment Method of Manned/Unmanned Aerial Vehicle Formation[J]. Systems Engineering and Electronics， 2010， 32（3）： 584-588.（in Chinese）

[2] 王然輝， 王超. 面向對地打擊武器-目標分配問題的遺傳算法變量取值控制技術[J]. 兵工學報， 2016， 37（10）： 1889-1895.

Wang Ranhui， Wang Chao.Variable Value Control Technology of Genetic Algorithm for WTA of Ground Target Attacking[J]. Acta Armamentarii， 2016， 37（10）： 1889-1895.（in Chinese）

[3] 鄧道靖， 馬云紅， 龔潔， 等. 基于并行GAPSO算法的多無人機協同任務規劃[J].電光與控制， 2016， 23（11）： 18-22.

Deng Daojing， Ma Yunhong， Gong Jie， et al. Cooperative Mission Planning of Multiple UAVs Based on Parallel GAPSO Algorithm[J]. Electronics Optics & Control， 2016， 23（11）： 18-22.（in Chinese）

[4] 夏維， 劉新學， 范陽濤， 等.基于改進型多目標粒子群優化算法的武器-目標分配[J].兵工學報， 2016， 37（11）： 2085-2092.

Xia Wei， Liu Xinxue， Fan Yangtao， et al.WeaponTarget Assignment with an Improved MultiObjective Particle Swarm Optimization Algorithm[J]. Acta Armamentarii， 2016， 37（11）： 2085-2092.（in Chinese）

[5] 王強， 張安， 宋志蛟.UAV 協同任務分配的改進DPSO 算法仿真研究[J].系統仿真學報， 2014， 26（5）： 1149-1155.

Wang Qiang， Zhang An， Song Zhijiao.Simulation Study on Improved Discrete Particle Swarm Optimization Algorithm for Multiple UAV Cooperation Task Assignment[J].Journal of System Simulation， 2014， 26（5）： 1149-1155.（in Chinese）