基于量子粒子群優化算法的多機協同目標分配問題研究

王記豐李崢葉文

（1.中國船舶工業系統工程研究院北京100094）（2.海軍航空工程學院兵器科學與技術系煙臺264001）

基于量子粒子群優化算法的多機協同目標分配問題研究

王記豐1李崢1葉文2

（1.中國船舶工業系統工程研究院北京100094）（2.海軍航空工程學院兵器科學與技術系煙臺264001）

針對粒子群優化算法易陷入局部極值、搜索空間有限等不足，將量子理論與粒子群優化算法相結合，采用量子粒子群優化算法來解決于多機協同目標分配問題。量子粒子群優化算法中的粒子采用向量表示，該向量由多機協同目標分配問題中的每個分配方案組成，由此在解空間內搜索最優解。仿真表明，該算法收斂速度快、全局收斂性能好，更加適合于目標分配問題求解。

多機協同；目標分配；粒子群算法；量子粒子群算法

Class NumberTP301.6

1 引言

多機協同目標分配問題就是在綜合考慮多種約束條件下，對攻擊的目標進行合理分配，確保飛機編隊以最小代價獲取最大攻擊效果。多機協同目標分配問題的實質是進行組合優化，常用的方法主要有精確搜索和啟發式搜索兩種，前者主要是窮舉搜索法，后者主要有遺傳算法和禁忌搜索等。但是這些方法都存在巨大的計算代價，這也是組合優化問題急需解決的難點問題。

目前，粒子群優化算法（particle swarm optimi?zation，PSO）與經典的啟發式搜索算法相比，具有較大的優勢和可行性。但在應用過程中，PSO算法也會經常出現早熟現象［1～2］。針對這些不足，本文將粒子的量子行為引入到粒子群算法當中，并采用其來解決多機協同目標分配問題，該算法比PSO算法具有更好的全局搜索能力，能夠有效地避免PSO算法陷入局部最優解，提高了算法的收斂速度。

2 問題描述

假設Vi（Vi∈V，i=1，2，…，NV）表示飛機，Ti(Ti∈T，i=1，2，…，NT)表示目標，Pi(Pi∈P，i=1，2，…，NP)表示威脅或者禁飛區。設集合

集合，則多機協同目標分配就是在要求的時間內將所有目標分配給各架飛機，即

并且滿足整體作戰效能最大，如圖1所示。

多機協同目標分配的最優目標是多架飛機的整體作戰效能最大，其評價指標主要有飛機的損耗程度、目標的價值收益和飛行航程的長度［3～4］。所以，將飛機損耗最小、目標價值收益最大、飛行航程最短作為衡量多機協同目標分配方案優劣的重要性能指標。

1）飛機損耗最小指標

該指標主要是引導目標分配方案向著減小飛機自身損耗的方向搜索，使飛機所受的威脅度最小，趨向于在安全航路飛行。假設飛機u攻擊目標i的生存概率為PSi，則飛機攻擊該目標時的損耗為HSi=1-PSi。因此，在進行目標分配時，盡量使得所有飛機的損耗之和最小，即

2）目標價值收益最大指標

該指標主要是引導目標分配方案向著飛機作戰效能最大化的方向搜索，使飛機盡量攻擊價值高的目標。假設飛機u攻擊目標i的殺傷概率為PKi，目標i的價值為vi，則目標價值收益為Vi=vi·PKi。因此，在進行目標分配時，盡量使得總收益最大，即

3）飛行航程最短指標

該指標主要是引導目標分配方案向各個飛機近距離任務目標進行搜索。假設飛機u與目標i間的距離為Di，則在進行目標分配時，盡量使得總航程最小，即：

綜上所述，多機協同目標分配的性能指標函數為

其中，ω1，ω2，ω3為加權系數。

3 量子粒子群目標分配算法

在粒子群優化算法中，主要是通過粒子的運動來搜索，而粒子的運動由速度和位置來決定，并且具有一定的軌跡和滿足一定的規律。因此，在傳統粒子群算法搜索過程中，存在不能搜索整個可行空間的可能，達不到全局收斂，易陷入局部最優［5］。

孫俊根據量子力學理論對粒子群優化算法進行了改進，提出了新的算法，這種算法被命名為量子粒子群優化算法［6～8］。該算法將量子的行為應用于粒子的運動，用波函數來確定粒子的狀態，將整個解可行空間作為量子空間，粒子在量子空間中進行搜索，從而避免算法陷入局部極值，提高算法的全局搜索能力。

3.1 量子粒子群優化算法數學模型

在傳統的PSO算法中，粒子的位置和速度共同決定了粒子的運行軌跡，粒子沿著確定的軌跡運動。但是，根據量子力學理論和不確定性原理，軌跡是沒有意義的，粒子的位置和速度是無法同時確定的。因此，如果將量子行為作用于PSO中的粒子，那么，PSO算法的工作方式將是不一樣的。孫俊等人給出了量子粒子群優化算法。該算法描述如下：

在量子粒子群優化算法中，用波函數來確定粒子的狀態，整個解可行空間作為量子空間，粒子在整個量子空間中進行搜索，從而提高算法的全局搜索能力［9］。因此，可以根據薛定愕方程得到的粒子出現的概率密度來表示粒子在量子空間中的位置，即粒子的隨機位置方程為

式中u為［0，l］區間的隨機數，并且服從均勻分布，L由下式確定：

QPSO算法的進化方程：其中i=1，2，…，m；d=1，2，…，D；u、r1和r2為［0，1］區間的隨機數；t為當前算法搜索的迭代次數；粒子的維數為D，種群數目為M，u和p是為［0，l］區間的隨機數，Pi(t)表示粒子的當前最佳位置，Pg(t)表示粒子的全局最佳位置，mbest(t)表示群體中平均最佳位置，pid(t)為Pi(t)和Pg(t)之間的隨機點。β為該算法中唯一的一個重要參數，即收縮擴張系數，其值具有多種設置方法，可以為固定值，也可為變值，如按遞增或遞減的方式變化，在通常情況下一般采用下式來進行該參數的取值：

β隨著迭代線性地從m遞減到n，通常m=1，n=0.5，式中MaxTimes是迭代的最大次數。當β≤0.5時，式中采用減號；當β＞0.5時，式中采用加號。

3.2 量子粒子群優化算法流程

步驟1：進行群體規模、迭代次數、種群個數、維數的初始化；

步驟2：計算各自粒子的最好位置，得到Pi和Pg；

步驟3：優化過程，按照量子粒子群算法的進化方程更新QPSO算法中的所有粒子；

步驟4：計算粒子位置，進行局部極值和全局極值的更新，即更新Pi和Pg；

步驟5：搜索結果是否滿足要求判斷，滿足則停止搜索并輸出最優解，不滿足則跳到步驟3繼續搜索。

QPSO算法描述如下：

初始化所有粒子的位置向量，記錄個體極值和全局極值

4 基于量子粒子群算法的多機協同目標分配

4.1 粒子的編碼

QPSO本質上是連續的，因此在將QPSO應用于目標分配問題求解中，需要將連續解映射到離散解上，本文采用直接取整法的整數規格化方法來對粒子位置參數處理。直接取整法就是在搜素迭代過程中，直接將各粒子的位置參數值取整處理，來滿足目標分配離散問題求解的需要。

采用自然數編碼進行粒子的編碼，將目標的總數作為粒子向量的長度，各粒子位置向量的各個分量為對應的各個目標被分配的相應飛機序號。比如，飛機數目n為8，目標數目m為15，一個粒子為

即X=[3 7 8 4 7 2 6 7 1 8 5 5 2 4 3]表示為粒子的位置向量，具體含義為第3架飛機攻擊第1個目標，第7架飛機攻擊第2個目標，…，第4架飛機攻擊第14個目標，第3架飛機攻擊第15個目標。同時，粒子的位置向量還要滿足一定岳蘇條件，如每一個目標必須分配一個飛機的限制，單位粒子取值范圍為[1，n]，以及飛機的最大攻擊目標數目限制，即單架飛機攻擊的目標總數不能超過其最大攻擊能力。

4.2 初始粒子群的確定

在該算法中，一個可行的分配方案就可用一個粒子表示，即對應于一個一維數組。為了確保粒子群在初始狀態有比較好的分散度，對于每一個目標，隨機的在［1，n］中選擇一架飛機分配給該目標，如果隨機選擇的飛機已經達到其最大攻擊目標數，則重新生成隨機數選擇其它飛機來分配給該目標，形成一個可行解。根據同樣的規則，構造一定數量的初始粒子，形成初始粒子群。

算法的運行效率和效果在一定程度上還受粒子個數M的影響，粒子個數M過小時，有利于提高算法運行速度，但易陷入局部極值，即早熟收斂；粒子個數M過大時，則會降低算法的運行效率。一般M取值為30-60之間為宜，本文中取M=30。

4.3 適應度函數值的計算

根據衡量多機協同目標分配方案優劣的性能指標，即飛機損耗最小、目標價值收益最大、飛行航程最短，多機協同目標分配的適應度函數可確定為

其中，ω1，ω2，ω3為權系數。在本文的仿真實例中，主要是為了驗證協同目標分配算法的有效性，因此簡化了協同目標適應度函數，主要考慮以目標價值收益程度來指導目標分配，即權系數為ω1=1，ω2=0，ω3=0。

4.4 量子粒子群算法的流程設計

由于量子粒子群算法的進化方程是針對連續域中的問題求解來進行設計的，但是多機協同目標分配問題是離散域中的問題，因此，直接利用量子粒子群算法的進化方程進行粒子位置的更新，效果不是很理想。針對多機協同目標分配問題的特點，重新設計了量子粒子群算法的進化方程。

1）mbest(t)的計算

針對群體中平均最佳位置mbest(t)，不是進行直接的數值求平均方法來計算，而是通過粒子位置向量中每位上數值出現的頻率來計算，即某t時刻，假設群體中有m個粒子，將所有粒子位置向量的第i位數值取出進行比較，其中出現頻率最多的數值賦值于mbest(t)的第i位，即將m個粒子位置向量中在第i位上出現頻率最多的數值設定為群體中平均最佳位置mbest(t)的第i位數值。這樣，通過每一位數值出現頻率的比較，最終得到mbest(t)。

2）pid的計算

pid為Pi和Pg之間的隨機點，在量子粒子群算法的進化方程中，pid的計算公式也是針對連續域中的問題來進行設計的，因此，這里我們也進行了改進。針對pid中的每j位，通過隨機生成一個［0，1］的隨機數，當rand(0，1)≤0.5，則pid(j)= Pid(j)，當rand(0，1)＞0.5，則pid(j)=Pgd(j)。

3）Xid(t+1)的更新

Xid(t+1)的更新正常按照量子粒子群算法的進化方程進行更新，只是在每次更新完畢之后，采用直接取整法，將各粒子的位置參數值取整，計算其適應值，并提取Pi、mbest和Pg，接著計算下一個位置，進入下一次取整，直到滿足計算要求。

應用量子粒子群算法進行多機協同目標分配的流程描述如下：

（1）初始化粒子群，確定各粒子初始的隨機位置，同時計算Pi和Pg；

（2）動態調整收縮擴張系數；

（3）各粒子適應度函數值的計算；

（4）對于每個粒子，比較其適應值與當前pi(t)的適應值，若較好，則更新Pi(t)；比較其適應值與當前Pg(t)的適應值，若較好，則更新Pg(t)；

（5）算法收斂判斷，如滿足，則輸出Pg(t)，算法結束；否則，執行（6）；

（6）根據量子粒子群算法的進化方程生成新的粒子，轉到步驟（2）；

（7）輸出最佳分配方案作為優化結果，算法結束。

5 仿真驗證與分析

算例：8架無人機編隊對15目標協同目標分配

假設有8架無人機編隊和15個地面目標。采用表1中數據作為目標的價值、飛機對目標的殺傷概率。

根據這一想定，對上述問題分別采用遺傳算法、離散粒子群算法和量子粒子群算法進行仿真，并對比分析仿真結果。遺傳算法、離散粒子群算法和量子粒子群算法在60次迭代過程中最好解、平均解和最差解的變化曲線如圖2～圖4所示，仿真結果比較分析如圖5和表2所示。

表1 目標分配初始數據

表2 算法性能比較

從圖2～圖4的各種算法收斂速度和解的性能可以看出，相對于遺傳算法和離散粒子群算法，量子粒子群算法具有較好的收斂特性，可以較快地搜索到問題的最優解。此外，量子粒子群算法的優化效率也較高，能夠在較少的進化代數內，其解群就向最優解的方向收斂。

6 結語

本文針對粒子群優化算法搜索空間有限、容易陷入局部最優點的缺陷，應用基于量子行為的粒子群優化算法解決多機協同目標分配問題。通過自然數編碼，每個粒子表示一種可能的分配方案，由此在解空間內搜索最優解。實例仿真結果表明，該算法能夠有效解決多機協同目標分配問題。

［1］葉媛媛，多UCAV協同任務規劃方法研究［D］長沙：國防科學技術大學，2005.

［2］龍濤，多UCAV協同任務控制中分布式任務分配與任務協調技術研究［D］長沙：國防科學技術大學，2006.

［3］葉文，朱愛紅，歐陽中輝，范洪達.基于混合離散粒子群算法的多無人作戰飛機協同目標分配［J］.兵工學報，2010，03：331-336.

［4］葉文，朱愛紅，潘長鵬，范洪達.多UCAV協同目標分配算法研究［J］.系統工程與電子技術，2010，01：104-108.

［5］潘全科，王文宏，朱劍英.解決無等待流水車間調度問題的離散粒子群優化算法［J］.計算機集成制造系統. 2007.13（6）：1127-1132.

［6］周翠華.量子粒子群優化算法的研究及應用［D］.大慶：東北石油大學，2011.

［7］SUN Jun，FENG Bin，XU Wen-bo.Particle swarm opti?mization with particles having quantum behavior［C］// Proc of Congress on Evolutionary Computation.2004：325-331.

［8］SUN Jun，XU Wen-bo，FENG Bin.A global search strate?gy of quantum behaved particle swarm optimization［C］// Proc of IEEE Conference on Cybernetics and Intelligent Systems.2004：111-116.

［9］張蘭.量子粒子群算法及其應用［D］.西安：西北大學2010：25-40.

Multi-plane Cooperation Task Assignment Problem Based on Quantum-behaved Particle Swarm Optimization Algorithm

WANG Jifeng1LI Zheng1YE Wen2
（1.Systems Engineering Research Institute，Beijing100094）（2.Department of Ordnance Science and Technology，Naval Aeronautical Engineering Institute，Yantai264001）

multi-plane cooperation，task assignment，particle swarm optimization，quantum-behaved particle swarm opti?mization

TP301.6

10.3969/j.issn.1672-9730.2017.08.008

2017年2月3日，

2017年3月18日

航空科學基金（編號：20111784002）項目資助。

王記豐，男，碩士，高級工程師，研究方向：任務規劃技術、指揮自動化。李崢，男，碩士，高級工程師，研究方向：任務規劃技術，指揮自動化。葉文，男，博士，高級工程師，研究方向：作務規劃技術、航空軍械。

AbstraetCoping with such disadvantages of particle swarm optimization algorithm as finite sampling space，being easy to run into local optima，quantum-behaved particle swarm optimization is used to be solve the multi-plane cooperation task assign?ment problem.A vector composed of every assignment regarded as a particle in this algorithm to evolve.Then，the sampling space is searched for the global optima.The simulation results show that the algorithm has better global convergence ability and more rapid convergence，and it is superior to genetic algorithm and particle swarm optimization algorithm，and the proposed algorithm is effec?tive and feasible.