基于改進量子粒子群算法的無人機路徑規劃

郭蘊華,王曉宗

(武漢理工大學a.船舶動力工程技術交通行業重點實驗室;b.能源與動力工程學院,武漢 430063)

?

基于改進量子粒子群算法的無人機路徑規劃

郭蘊華,王曉宗

(武漢理工大學a.船舶動力工程技術交通行業重點實驗室;b.能源與動力工程學院,武漢 430063)

針對無人機路徑規劃算法收斂速度慢、易陷入局部最優等問題，提出一種改進的量子粒子群算法。該算法根據粒子與局部吸引點和可行解邊界的距離動態的修正粒子更新位置，改善了算法的全局尋優能力和收斂性能。仿真實驗表明所提出的改進QPSO算法比其他已有算法可以得到更高質量的航跡，并且其收斂性較好。

無人機;改進量子粒子群算法;最小威脅面;航跡規劃

在船舶海洋事業快速發展的今天，利用船用無人機探測即時天氣變化將成為一種趨勢。由于無人機的續航能力有限，實際應用中往往需要合理的規劃其飛行軌跡以節約能耗，因此無人機路徑規劃也成為目前的研究熱點之一。所謂無人機路徑規劃，就是指綜合考慮無人機機動性能、突防概率、碰撞概率和飛行時間等約束條件，尋找從起點到目標點的最優或可行的飛行軌跡[1]。目前用于無人機路徑規劃的方法大致分為如下幾類：①路線圖方法，像隨機路線圖法等[2]；②啟發式算法，例如A*算法等[3]；③進化算法，如粒子群優化(particle swarm optimization, PSO)算法[4]、差分進化(Diffrential Evolution, DE)算法[5]、量子粒子群優化(quantum-behaved particle swarm optimization, QPSO)算法[6-7]和具有高斯分布局部吸引點的QPSO(QPSO with gaussian distributed local attractor point, GAQPSO)算法[8]等。相對于其他方法而言，進化算法以航跡代價模型為目標函數，在種群演化過程中逐步獲取更好的優化性能，因此可以得到更加合理的飛行路徑。不過，PSO、DE、QPSO等進化算法往往也有收斂速度慢、易陷入局部最優等缺點。為此，本文提出了一種基于改進QPSO算法的無人機路徑規劃方法。該算法根據粒子與局部吸引點和可行解邊界的距離動態的修正粒子更新位置，改善了算法的全局尋優能力和收斂性能。通過仿真實驗將這種改進QPSO算法與標準QPSO、GAQPSO、PSO和DE等算法進行了比較，實驗結果表明，這種新算法可以得到更高質量的航跡，且具有較好的收斂性。

1　航跡代價建模

種群中每一個粒子代表著一條航跡。種群可以用一個矩陣表示，即X= [X1，X2，…,Xm]。式中：m為種群的大小；Xi為第i條航跡。對于二維航跡規劃而言，設各航跡除起點和目標點外有n個航跡點，則航跡點位置信息可以表示為Xi=[xi,1,xi,2,…,xi,n,xi,n+1,…,xi,2n]。粒子的維數為2n。

在二維航跡規劃中，其代價函數只考慮航跡的長度代價、威脅代價以及水平轉角代價等。對于給定的航跡路徑Xi來說，其長度代價就可以用從起點到終點的所有路徑之和表示[6-7]

(1)

式中：di,0和di,n+1——分別為第i條航跡的起點到第1個節點的距離和最后一個節點到目標點的距離；

j——航跡節點。

航跡的威脅代價按式(2)計算[7]，即

(2)

式中：sk——威脅強度系數；

Jk,j——第k個威脅圈對第j段航跡段的威脅度，按式(3)計算，即

(3)

式中：dk, j——第k個威脅圈到第j段航跡段之間的垂線距離；

Rk——第k個威脅圈的半徑；

lk, j——第j段航跡段在第k個威脅圈內的弦長。

此外，航跡還必須滿足水平轉角約束條件[7]，即

(4)

式中：α——無人機當前的水平轉角；

αmax——無人機預設的最大轉角。無人機的當前轉角可以利用三角函數和向量來求解，記第i條航跡的航跡段j的水平投影為：

(5)

那么它當前的轉角α應如下所得[7]。

(6)

式中：‖ai,j‖——矢量ai,j的長度，j= 2,3,…,n-1。

綜上，無人機航跡規劃的適應度函數應為下式。

(7)

式中：w1、w2、w3——分別為權重系數，必須滿足w1+w2+w3=1。

2　改進量子群算法

2.1標準QPSO算法

經典PSO算法的主要缺點是容易陷入局部最優，為此孫俊等[9-10]提出了QPSO算法，以提高全局尋優能力。在QPSO算法中，粒子的狀態不再由粒子的位置和速度來描述，取而代之的則是粒子的波函數，通過求解薛定諤方程得到粒子在空間某一點出現的概率密度函數，再通過蒙特卡羅方法求解，可以得到第t次迭代時粒子i的第d維的位置更新方程[9-10]。

(8)

式中：pid(t)——局部吸引點，即

(9)

uid(t),φd(t)為[0,1]之間的隨機數；Pid(t)粒子i的第d維的個體最優位置；Gd(t)為種群第d維的全局最優位置。式(8)中的Lid(t)由下式確定。

(10)

式中：參數Cd(t)稱為平均最優位置，可由下式計算得到:

(11)

綜合可得到其更新方程

(12)

式中：參數α稱為壓縮-擴張因子，迭代過程中一般在1～0.5之間遞減[10]，rnd為[0, 1]上均勻分布的隨機數。

2.2改進QPSO算法

在標準QPSO算法中，壓縮-擴張因子α一般在1～0.5之間遞減(線性遞減最常見)，這相當于α只壓縮而不擴張。如此操作有其合理性，可以在迭代后期改善局部搜索的精度。不過，假如在迭代過程中發生早熟，則α的遞減策略會使粒子很難跳出局部最優點。為了進一步改善算法的全局搜索能力，設計了一種根據粒子與局部吸引點和可行解邊界的距離動態的修正粒子更新位置的自適應策略，具體描述如下。

1)如果D

(13)

2)如果D>1，也即粒子越界時，那么其進化方程如下：

(14)

式中：r1～r4——分別為4個在[1,m]上分布的隨機整數。

3)若均不屬于以上兩種情況，則其進化方程應為：

(15)

式中：D——檢測距離,

D=|p(t)-x(t)|/|Lupper-Llower|；

Lupper——第k維的上界；

Llower——第k維的下界；

Dmax——檢測距離上界；

β——記憶因子，這兩個參數與所選目標函數是否有為多峰值有關，具體映射關系如下。

1)如果目標函數可能有較多的峰值，那么則取Dmax=0.05，β=0.75～0.85。

2)如果目標函數為單峰值或較少峰值，則取Dmax=0.02，β=0.50～0.65。

3　仿真及實驗結果

在C#編程環境下進行了仿真實驗，假定無人機的飛行區域為一個700 m×700 m的正方形區域，包括6個威脅圈，其威脅分布見表1。

表1　威脅分布

起點坐標為(40, 500)，目標點為(600, 300)。種群大小/粒子維度/最大迭代次數依次設為50/10/100。w1～w3的取值分別為0.3、0.4、0.3。對改進QPSO、QPSO、GAQPSO、DE、PSO這5種算法進行了對比實驗，每種算法的蒙特卡洛仿真次數為100。

仿真實驗結果見圖1、圖2、表2。

圖1　各種算法生成的最優航跡圖

圖2　平均最優適應度的收斂曲線

算法改進QPSOGAQPSOQPSOPSODE平均最優解282.683350.778312.227389.796370.522

由圖1、圖2及表2可見，對無人機航跡規劃問題，本文提出的改進QPSO算法的收斂速度僅次于GAQPSO算法，但本文算法的全局尋優能力更強，最終其平均最優解要比GAQPSO算法好得多(即可以找到更短的路徑，且不會與威脅區有交集，換言之，航跡質量更高)。而對于QPSO、PSO、DE這3種算法，無論是收斂速度(其中以QPSO算法的收斂速度最差)還是全局尋優能力均遜于本文算法。

4　結束語

由于無人機續航能力有限，因此有必要合理地規劃無人機路徑以降低能耗。本文提出的一種基于改進QPSO的無人機路徑規劃算法，與標準QPSO算法明顯不同之處在于，它可以根據粒子與局部吸引點和可行解邊界的距離動態的修正粒子更新位置，增強粒子的擾動特性，提高粒子跳出局部最優的能力，進而提高了種群的全局尋優能力。仿真實驗的結果表明，相對于標準QPSO、GAQPSO、PSO、DE等其他幾種算法，本文算法能夠找到更高質量的最優航跡，且同時成功地避開了威脅區。不過，在幾種算法的比較中，本文算法的收斂速度并不是最快的。在下一步的研究工作中，將嘗試開發本文算法與其他算法的混合算法，以進一步提高其收斂速度，方便其更易應用于實時環境。

[1] 傅陽光,周成平,丁明躍.基于混合量子粒子群優化算法的三維航跡規劃[J].宇航學報,2010,31(12):2657-2664.

[2] 孫漢昌,朱華勇.基于概率地圖方法的無人機路徑規劃研究[J].系統仿真學報,2006,18(11):3050-3054.

[3] 張得舒,黃長強,丁達理,等.基于A*算法的無人機攻擊軌跡解算[J].電光與控制,2011,18(3):18-20.

[4] 陳琳,白振興.應用PSO算法的無人機三維航跡規劃[J].電光與控制,2008,15(4):50-53.

[5] 劉波,王凌,金以慧.差分進化算法研究進展[J].控制與決策,2007,22(7):721-729.

[6] FU Y, DING M, ZHOU C. Phase Angle-Encoded and Quantum-Behaved Particle Swarm Optimization Applied to Three-Dimensional Route Planning for UAV[J]. IEEE Transactions on Systems Man & Cybernetics Part A Systems & Human, 2012,42(2):511-526.

[7] FU Y, DING M, ZHOU C, et al. Route Planning for Unmanned Aerial Vehicle (UAV) on the Sea Using Hybrid Differential Evolution and Quantum-Behaved Particle Swarm Optimization[J]. IEEE Transactions on Systems Man & Cybernetics Systems, 2013,43(6):1451-1465.

[8] SUN Jun, FANG Wei, PALADE V, et al. Quantum-behaved Particle Swarm Optimization with Gaussian Distributed Local Attractor Point [J]. Applied Mathematics and Computation, 2011,218:3763-3775.

[9] SUN Jun, XU Wenbo, Feng Bin. A global search strategy of quantum-behaved particle swarm optimization [C]∥IEEE Conference on Cybernetics and Intelligent Systems, 2004(1):111-116.

[10] 方偉,孫俊,謝振平,等.量子粒子群優化算法的收斂性分析及控制參數研究[J].物理學報,2010,59(6):3686-3694.

UAV Path Planning Based on Improved Quantum-behaved Particle Swarm Optimization Algorithm

GUO Yun-hua, WANG Xiao-zong

(a. Key Lab. of Marine Power Engineering & Technology, Ministry of Communications; b. School of Energy and Power Engineering, Wuhan University of Technology, Wuhan 430063,China)

An improved algorithm based on the quantum-behaved particle swarm optimization is proposed for UAV path planning problem. The updated position of the particle is adaptively adjusted by the distance between the particle and the local attractor point and the distance between the particle and the boundary of the feasible region. Simulation results show that the improved QPSO algorithm can get the track with higher quality, and its convergence is better.

UAV; improved QPSO algorithm; minimum face threat; route planning

10.3963/j.issn.1671-7953.2016.01.019

2015-11-19

2015-12-02

國家自然科學基金(51579201)

郭蘊華(1975-)，男,博士，教授

TP24

A

1671-7953(2016)01-0099-04

研究方向:信息融合與工程優化

E-mail:wtugyh@163.com