基于改進量子粒子群優化算法的多UCAV 協同任務分配研究

趙雪森，王社偉，邵 校

(空軍航空大學飛行器控制系，長春 130022)

多UCAV 任務分配是近年來UAV 領域研究的熱點問題。多UCAV 協同任務分配目的是在滿足資源、平臺以及時間等約束條件下，將合適的任務在合適的時間分配給合適的UCAV，并使多UCAV 系統的整體任務效能達到最優［1］。它是一個約束條件眾多而復雜的優化問題，其解空間隨著目標總數的增加而增加，使其成為一個多參數、多約束的NP 問題。傳統的數學方法求解十分困難，而智能算法提供了解決問題的新途徑。量子粒子群算法［2］是智能優化算法中的一種，本文提出的改進型量子粒子群算法在量子粒子群算法的基礎上加入了混沌機制和變異算子，提高了算法的尋優能力，有效避免算法陷入局部最優和過早的收斂。

1 多UCAV 任務分配MOIP 模型

1.1 任務分配問題描述

本文假設UCAV 在一個二維空間內執行任務，戰場地形以及戰場中的目標位置信息已預先獲知。戰場中有m 架UCAV，V={V1，V2，…，Vm}，t 個作戰目標，T ={ T1，T2，…，Tt}，任務類型Mt={Classify，Attack，Verify}，分別代表偵察、攻擊和毀傷評估任務，但不是每個作戰目標都全部包含這3種任務類型，任務總數要求每架無人機至少執行一個任務，至多執行Tmax個任務，且每個任務被一架無人機執行。考慮無人機的能力約束和多無人機間的時間約束，使最終分配達到收益最大，損耗最小。

1.2 任務分配模型

首先定義二進制決策變量xi，j∈{0，1}，xi，j=1 時表示Vi執行任務Ti，xi，j=0 時無人機不執行任務。本文針對無人機在執行任務時的任務總飛行航程、任務完成時間、目標價值收益3 個重要指標進行分析。

1)任務總飛行航程J1。在實際作戰中，UCAV 執行任務的路程越長，執行任務的時間就越長，所消耗的燃油也越多，被敵方所擊落的概率也就越大，因此為了降低UCAV 所受的風險要縮短UCAV 編隊執行任務的總航程。

式(1)中，ti，j表示無人機Vi執行任務Tj的時間，speedi表示無人機的速度。

2)最長任務完成時間J2。戰場環境瞬息萬變，暴露在目標區域時間越長，無人機所受威脅越大。縮短完成任務時間最長的UCAV 的執行時間能夠有效減低UCAV 被敵方防空武器擊毀的概率。

3)目標價值收益J3。不同的任務相應具有不同的收益價值，在協同作戰中，UCAV 應該盡可能地攻擊高價值的目標，追求效益的最大化。

綜合考慮上述3 個指標，多UCAV 協同任務分配模型定義為式(4)，為了求得指標函數最小，J3取為-J3。

1.3 任務分配約束條件

多UCAV 協同控制任務分配問題是一類約束條件眾多的組合優化問題［3-4］，由于約束條件的耦合程度高，使得求解極為復雜，為了方便建模和算法的求解，下面從多機協同約束、任務時間約束、無人機任務類型及能力約束3 個方面進行考慮，給出協同控制約束條件的數學描述。

1.3.1 多機協同約束

每個任務只能被執行一次。

每架UCAV 一次只能執行一項任務。

每個目標包含的任務都要被執行。

1.3.2 任務時間約束

時間窗約束，給定時間窗口(aj，bj)，無人機Vi到達目標Tj時刻為tij。

1.3.3 無人機任務類型及能力約束

無人機任務類型約束，Mti，j為UCAV Vi執行的任務Mj的任務類型，MKind(Vi)為Vi所能執行的任務類型。

無人機能力約束，Di為UCAV Vi的最大航程。

2 改進的量子粒子群優化算法

2.1 量子粒子群優化算法

粒子群優化算法(Particle Swarm Optimization，PSO)是在1995年由美國社會心理學家Kennedy 和電氣工程師Eberhart提出的［5-6］，主要思想來源于對鳥類群體行為的研究。自提出以來，由于其計算簡單、收斂速度快、易于實現、控制參數少等特點，引起了國內外相關領域眾多學者的關注和研究，越來越多的被應用于優化問題中。但PSO 算法在優化過程中易出現早熟現象，不能保證收斂于到全局最優解，甚至于局部最優解。目前已提出了多種PSO 改進算法，如變異粒子群算法、自適應調整粒子群算法、免疫粒子群算法［7］，這些算法在一定程度上可避免PSO 陷入局部最優，但對算法易懂性、可操作性考慮太少，并且增加了算法的計算量。

為了更好地解決上述問題，sun 等［8-9］在研究了Clerc等人的關于粒子收斂行為的研究成果后，從量子力學的角度出發，提出了一種新的PSO 進化模型，這種模型以DELTA 勢阱為基礎，認為粒子具有量子行為，在模型的基礎上提出了量子粒子群優化算法。該算法對整個PSO 算法的進化搜索策略進行了修改，進化方程中不再需要速度向量，而且整個迭代方程參數更少，更容易控制。在量子空間中粒子滿足聚集態的性質完全不同，它可以在整個可行解空間中進行搜索，因而QPSO 算法的全局搜索性能遠遠優于標準PSO算法［10］。

QPSO 算法利用波函數φ(x，t)來描述粒子的狀態，并通過求解薛定諤方程得到粒子在空間某一點出現的概率密度函數，再通過Monte Carlo 隨機模擬得到粒子的位置方程為

式(11)中:u 是在［0，1］上服從均勻分布的隨機數;L 值由式確定，

則QPSO 算法的進化方程為

式(14)中:φ 和u 是［0，1］上均勻分布的隨機數，α 為收縮擴張系數，M 為種群中粒子的數目，N 為粒子的維數，Pi，j(t)和Gj(t)分別是粒子所經歷的最好位置和種群中所有粒子所經歷的最好位置。

2.2 混沌思想

混沌是一種貌似無規則的運動［11-13］，指在確定性非線性系統中不需要附加任何隨機因素即可以類似隨機的行為，隨機性使得搜索能夠避免陷入局部最優。混沌系統另一個最重要的特性就是遍歷性，它通過迭代產生的解能夠覆蓋目標區域內所有的點，只要控制得當，最終解可以以任意精度逼近真實的最優解。由于混沌系統的隨機性、遍歷性等特點，可以將混沌與量子粒子群算法相結合，來提高算法的性能。Logistic 映射是一種經典的混度映射，非常簡單且被廣泛應用，定義如下:

其中，μ∈(2，4］，當μ=4 且Z0∈(0，1)時方程處于完全混沌狀態。首先將決策變量xi，j按式(16)映射為［0，1］之間的混沌變量:

因為Logistic 映射在［0，1］上完全遍歷，所以將混沌系統應用到算法中，可以改善早熟收斂的問題。本文中采用采用混沌系統來初始化粒子的位置，這樣既不改變算法初始化時的隨機性，又可以利用混沌特性來提高種群的多樣性和搜索的遍歷性［12］。

2.3 高斯分布變異算子

混沌思想是在粒子初始化時增加群體的多樣性，而變異操作是在尋優過程中增加群體多樣性的有效手段。高斯概率分布是一類應用最廣泛的連續概率分布形式，當種群陷入局部最優時，通過增加一個擾動來解決這個問題。

其中ε 是預先規定的參數，本文設為ε=0.001，H 是滿足均值為0 方差為1 的高斯隨機分布。則式(14)變為

滿足高斯概率密度分布的變化方式具有很強的局部搜索能力，有利于提高算法的局部搜索精度。本文設置粒子群的變異作用隨著代數的迭加而降低，即在尋優初期作用于所有粒子，在尋優中期作用于部分粒子，而在尋優后期則不再變異，使粒子能夠在最優解鄰近區域進行精細搜索。高斯變異算子作用方式如圖1 所示。改進的量子粒子群算法(IQPSO)的流程如圖2 所示。

圖1 高斯變異算子作用方式示意圖

圖2 改進的QPSO 算法的流程

3 多UCAV 協同任務分配仿真

3.1 粒子編碼方式

多無人機任務計劃中的任務分配情況和執行次序都是自然數，因此需要對粒子的位置進行整數化處理。在粒子初始化和更新過程中，若某一維出現非整數，則按照四舍五入原則取整。編碼采用雙層整數編碼方式，第1 行表示執行任務的UCAVi，第2 行表示與第1 行UCAV 序列所對應的執行目標序列，如圖3 所示。

圖3 雙層編碼示意圖

圖中目標出現的次序表示對應UCAV 執行的任務類型，第1 次出現代表執行的為偵察任務，第2 次代表攻擊任務，第3 次代表評估任務。

3.2 適應度函數的建立

上述編碼方式可以滿足部分約束條件，但在任務超出無人機最大航程和不滿足時間窗約束時則需要對適應度函數加一個懲罰項將約束問題轉化為無約束問題。

式(20)中，系數a，b，c 用于對不同類型的懲罰進行一個尺度變換。

3.3 仿真示例

為驗證算法的有效性，針對3 架無人機對5 個敵方目標的任務進行仿真實驗，需要對目標進行偵查、攻擊以及評估3類任務，共計15 個待執行任務，分別用C、A、V 進行表示。UCAV 和敵方目標的位置如圖2 所示，具體數據如表1 ～表3所示，在不影響任務分配算法驗證的前提下簡化仿真實驗過程，假設飛行航路為直線，且所有待執行任務很短時間內即可完成。位置坐標均為km，無人機巡航速度360 km/h，最大航程3 500 km，任務價值經歸一化處理，每個算法運行30 次取最好值，最大迭代次數600，粒子數為50，PSO 算法中c1=c2=2，α 與β 范圍從0.9 到0.2 線性遞減。實驗初始設置圖如圖4 所示。

圖4 仿真實驗初始設置圖

3.4 仿真結果及分析

仿真的結果如下所示，表4 為3 種算法任務分配的結果，表5 為3 種算法在執行時間、整體代價和價值收益上的對比，圖5 為任務航程代價隨迭次數變化的曲線圖。

表1 無人機性能參數

表2 目標任務信息表

表3 任務時間窗約束

表4 PSO、QPSO、IQPSO 算法分配結果

表5 PSO、QPSO、IQPSO 算法所得結果比較

圖5 總任務航程代價曲線

通過圖表可以看出3 種算法均能完成預定任務的分配，每個目標都可以完成，但在任務的整體代價和執行時間上改進算法則明顯低于其余兩種算法，從圖5 中看出改進算法的收斂速度提高。通過仿真結果表明改進的算法在迭代過程中能夠幫助粒子跳出局部最優值，有效完成任務，驗證了算法的有效性。

4 結論

本文以為任務總飛行航程最小、任務完成時間最短、目標價值收益最大為目標構建了多UCAV 協同任務分配模型，在QPSO 算法的基礎上采用混沌機制和變異因子來提高種群的多樣性，改進的QPSO 算法能夠在保持快速性的同時有效的跳出局部最優解，克服了QPSO 易陷入局部最優的不足。最后仿真結果驗證該算法優于QPSO 算法，能夠有效的解決多UCAV 協同任務分配問題。

［1］Bryson M，Sukkarieh S.Decentralised Trajectory Control for Multi-UAV SLAM［C］//Proceeding of the 4th International Symposium on Mechatronics and it’sApplications.Sharjah，Uited Arab Emirates:IEEE，2007:1-6.

［2］寧濤. 混合量子算法在車輛路徑問題中應用的研究［D］.大連:大連海事大學，2013.

［3］霍霄華，陳巖，朱華勇，等.多UCAV 協同控制中的任務分配模型及算法［J］.國防科技大學學報，2006，28(3):83-88.

［4］龍國慶，祝小平，周洲.多無人機系統協同多任務分配模型與仿真［J］.飛行力學，2011，29(4):68-76.

［5］Kennedy J，Eberhart R.Particle swarm optimization［C］//Proceedings of IEEE International Conference on Neural Networks，1995:1942-1948.

［6］Eberhart R，Kennedy J. A new optimizer using particle swarm theory［C］//Proceeding of the 6th International Symposium on Micro Machine and Human Science.Nagoya，Japan:IEEE Service Center，1995:39-43.

［7］高海昌，馮博琴，朱利.智能優化算法求解TSP 問題［J］.控制與決策，2006，21(3):241-247.

［8］Sun Jun，Feng Bin，XuWenbo. Particle swarm optimization with particles having quantum behavior［C］//Proceedings of The IEEE Congress on Evolutionary Computation(CEC).USA，IEEE Presss，2004:325-331.

［9］Sun Jun，XuWenbo，Feng Bin. A global search strategy of quantum-beaved particle swarm optimization［C］//2004 IEEE Conference on Cybernetics and Intelligent Systems.USA，IEEEE Press，2004:111-116.

［10］李川.基于混合量子進化算法的隨機車輛路徑問題的研究［D］.浙江工業大學，2011.

［11］高尚，楊靜宇.群智能算法及其應用［M］.北京:中國水利水電出版社，2006.

［12］Chang Junlin，An Fengshuan，Su Pizhao. A quantum-PSO algorithm for no-wait flow shop scheeduing problem［C］//2010 Chinese Control and Decision Conference. Xuzhou，China:IEEE Press，2010:179-184.