基于離散映射的量子粒子群優(yōu)化算法求解WTA問(wèn)題

劉琨　潘翔宇

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

關(guān)鍵詞： 武器目標(biāo)分配（WTA）； 量子粒子群優(yōu)化算法； 離散映射； 編碼調(diào)整

中圖分類號(hào)： TJ760.1； TP18 文獻(xiàn)標(biāo)識(shí)碼： A文章編號(hào)： 1673-5048（2018）03-0037-07

0 引 言

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

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

因此， 本文提出目標(biāo)個(gè)數(shù)大于武器個(gè)數(shù)與目標(biāo)個(gè)數(shù)小于武器個(gè)數(shù)兩種武器目標(biāo)分配模型， 同時(shí)為提高算法的粒子利用率， 增強(qiáng)算法運(yùn)算效能， 提出一種基于離散映射的編碼調(diào)整方式， 將連續(xù)型粒子位置矢量投影至離散空間上， 減少算法求解最優(yōu)解的迭代次數(shù)。

1 武器目標(biāo)分配模型

1.1 問(wèn)題描述

為便于研究， 對(duì)戰(zhàn)場(chǎng)環(huán)境作以下假設(shè)：

（1） 假定武器對(duì)各目標(biāo)殺傷概率、 目標(biāo)威脅參數(shù)已知。

1.3 評(píng)價(jià)函數(shù)

評(píng)價(jià)函數(shù)是對(duì)智能搜索算法求解優(yōu)劣的判定函數(shù)， 針對(duì)編隊(duì)對(duì)地攻擊任務(wù)分配問(wèn)題， 現(xiàn)階段的研究大多數(shù)都以單目標(biāo)優(yōu)化模型為求解框架[8-9]。 本文構(gòu)建了考慮目標(biāo)剩余價(jià)值、 編隊(duì)攻擊損耗的多目標(biāo)優(yōu)化模型。 為簡(jiǎn)化求解難度， 通過(guò)線性加權(quán)的方法設(shè)置合理的權(quán)重系數(shù)， 將多指標(biāo)函數(shù)轉(zhuǎn)化為單指標(biāo)評(píng)判函數(shù)， 其表達(dá)式如下：

2.3 非法解的離散映射處理

整形實(shí)數(shù)編碼方式易產(chǎn)生不滿足目標(biāo)方案約束條件的非法解， 本文提出一種基于雙排序離散映射的編碼調(diào)整方式， 處理算法迭代運(yùn)算中產(chǎn)生的非法解， 并對(duì)連續(xù)性實(shí)數(shù)編碼進(jìn)行離散化投影至有效解空間上。

由于約束條件式（7）～（10）規(guī)定對(duì)每架戰(zhàn)機(jī)至多能對(duì)兩個(gè)目標(biāo)實(shí)施打擊， 因此當(dāng)2M

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

步驟7 根據(jù)之前保存的Popold和Popsort間的排序映射對(duì)應(yīng)關(guān)系， 對(duì)Popadapt每一維度位置進(jìn)行逆映射， 即可得到調(diào)整后的粒子位置矢量Popnew。

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

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)共設(shè)置兩組不同規(guī)模的武器目標(biāo)數(shù)。 在兩組仿真中， 分別對(duì)攻擊編隊(duì)攜帶武器數(shù)目大于目標(biāo)數(shù)、 攻擊編隊(duì)攜帶目標(biāo)數(shù)小于目標(biāo)數(shù)兩種情況進(jìn)行仿真分析。 檢驗(yàn)基于離散映射的量子粒子群優(yōu)化算法（QuantumBehaved Particle Swarm Optimization Algorithm with Discrete Mapping， DMQPSO）， 求解武器目標(biāo)分配問(wèn)題。

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

針對(duì)算例1仿真50次， 表5統(tǒng)計(jì)4種算法收斂至最優(yōu)解的算法時(shí)間， 并對(duì)比4種算法在搜索時(shí)間上的差異。 DMQPSO在搜索至最優(yōu)解的算法平均耗時(shí)上優(yōu)于SA-GA與PSO算法， 略遜于QPSO算法， 但QPSO算法易陷于局部最優(yōu)解， 通過(guò)搜索時(shí)間對(duì)比， DMQPSO算法滿足對(duì)目標(biāo)分配算法實(shí)時(shí)性的要求。

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

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

數(shù)增加， DMQPSO算法收斂性明顯優(yōu)于其余三種算法。 通過(guò)對(duì)比觀察可以得出， DMQPSO算法在100次迭代內(nèi)仍能快速搜尋到全局最優(yōu)解； SA-GA算法由于問(wèn)題規(guī)模增大已不能收斂至全局最優(yōu)， 且收斂速度緩慢； 基本QPSO算法在50次迭代內(nèi)有較強(qiáng)的收斂速度， 即在短時(shí)間內(nèi)搜索到的全局最優(yōu)適應(yīng)值甚至?xí)哂贒MQPSO算法， 但仍會(huì)陷入局部最優(yōu)； PSO算法在收斂性和全局最優(yōu)解的搜索精度上與DMQPSO算法有較大差距。

表8中列出最優(yōu)武器分配方案中， 對(duì)分配攻擊目標(biāo)T1， T3， T4， T5， T7， T9， T11的戰(zhàn)機(jī)均是對(duì)其毀傷概率最高的戰(zhàn)機(jī)且對(duì)分配攻擊T1， T3， T5目標(biāo)的戰(zhàn)機(jī)生存概率均最高， 表9中列出的最優(yōu)武器分配方案中對(duì)分配攻擊目標(biāo)T5， T10， T11的戰(zhàn)機(jī)均是對(duì)其毀傷概率最高的戰(zhàn)機(jī)， 均滿足論文提出的分配最優(yōu)解判定準(zhǔn)則。

針對(duì)算例2仿真20次， 表10對(duì)提高運(yùn)算規(guī)模后4種算法的搜索時(shí)間進(jìn)行統(tǒng)計(jì)對(duì)比。 4種算法在運(yùn)算規(guī)模提高后搜索時(shí)間均有所有增長(zhǎng)， DMQPSO算法搜索最優(yōu)解平均耗時(shí)明顯優(yōu)于SA-GA算法， 與QPSO與PSO算法相當(dāng)， 具有良好的實(shí)時(shí)性。

4 結(jié) 論

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

參考文獻(xiàn)：

[1] 劉躍峰， 張安. 有人機(jī)/無(wú)人機(jī)編隊(duì)協(xié)同任務(wù)分配方法[J]. 系統(tǒng)工程與電子技術(shù)， 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] 王然輝， 王超. 面向?qū)Φ卮驌粑淦?目標(biāo)分配問(wèn)題的遺傳算法變量取值控制技術(shù)[J]. 兵工學(xué)報(bào)， 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算法的多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃[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] 夏維， 劉新學(xué)， 范陽(yáng)濤， 等.基于改進(jìn)型多目標(biāo)粒子群優(yōu)化算法的武器-目標(biāo)分配[J].兵工學(xué)報(bào)， 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] 王強(qiáng)， 張安， 宋志蛟.UAV 協(xié)同任務(wù)分配的改進(jìn)DPSO 算法仿真研究[J].系統(tǒng)仿真學(xué)報(bào)， 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）