基于改進(jìn)量子粒子群算法的無(wú)人機(jī)路徑規(guī)劃

郭蘊(yùn)華,王曉宗

(武漢理工大學(xué)a.船舶動(dòng)力工程技術(shù)交通行業(yè)重點(diǎn)實(shí)驗(yàn)室;b.能源與動(dòng)力工程學(xué)院,武漢 430063)

?

基于改進(jìn)量子粒子群算法的無(wú)人機(jī)路徑規(guī)劃

郭蘊(yùn)華,王曉宗

(武漢理工大學(xué)a.船舶動(dòng)力工程技術(shù)交通行業(yè)重點(diǎn)實(shí)驗(yàn)室;b.能源與動(dòng)力工程學(xué)院,武漢 430063)

針對(duì)無(wú)人機(jī)路徑規(guī)劃算法收斂速度慢、易陷入局部最優(yōu)等問(wèn)題，提出一種改進(jìn)的量子粒子群算法。該算法根據(jù)粒子與局部吸引點(diǎn)和可行解邊界的距離動(dòng)態(tài)的修正粒子更新位置，改善了算法的全局尋優(yōu)能力和收斂性能。仿真實(shí)驗(yàn)表明所提出的改進(jìn)QPSO算法比其他已有算法可以得到更高質(zhì)量的航跡，并且其收斂性較好。

無(wú)人機(jī);改進(jìn)量子粒子群算法;最小威脅面;航跡規(guī)劃

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

1　航跡代價(jià)建模

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

在二維航跡規(guī)劃中，其代價(jià)函數(shù)只考慮航跡的長(zhǎng)度代價(jià)、威脅代價(jià)以及水平轉(zhuǎn)角代價(jià)等。對(duì)于給定的航跡路徑Xi來(lái)說(shuō)，其長(zhǎng)度代價(jià)就可以用從起點(diǎn)到終點(diǎn)的所有路徑之和表示[6-7]

(1)

式中：di,0和di,n+1——分別為第i條航跡的起點(diǎn)到第1個(gè)節(jié)點(diǎn)的距離和最后一個(gè)節(jié)點(diǎn)到目標(biāo)點(diǎn)的距離；

j——航跡節(jié)點(diǎn)。

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

(2)

式中：sk——威脅強(qiáng)度系數(shù)；

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

(3)

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

Rk——第k個(gè)威脅圈的半徑；

lk, j——第j段航跡段在第k個(gè)威脅圈內(nèi)的弦長(zhǎng)。

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

(4)

式中：α——無(wú)人機(jī)當(dāng)前的水平轉(zhuǎn)角；

αmax——無(wú)人機(jī)預(yù)設(shè)的最大轉(zhuǎn)角。無(wú)人機(jī)的當(dāng)前轉(zhuǎn)角可以利用三角函數(shù)和向量來(lái)求解，記第i條航跡的航跡段j的水平投影為：

(5)

那么它當(dāng)前的轉(zhuǎn)角α應(yīng)如下所得[7]。

(6)

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

綜上，無(wú)人機(jī)航跡規(guī)劃的適應(yīng)度函數(shù)應(yīng)為下式。

(7)

式中：w1、w2、w3——分別為權(quán)重系數(shù)，必須滿足w1+w2+w3=1。

2　改進(jìn)量子群算法

2.1標(biāo)準(zhǔn)QPSO算法

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

(8)

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

(9)

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

(10)

式中：參數(shù)Cd(t)稱為平均最優(yōu)位置，可由下式計(jì)算得到:

(11)

綜合可得到其更新方程

(12)

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

2.2改進(jìn)QPSO算法

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

1)如果D

(13)

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

(14)

式中：r1～r4——分別為4個(gè)在[1,m]上分布的隨機(jī)整數(shù)。

3)若均不屬于以上兩種情況，則其進(jìn)化方程應(yīng)為：

(15)

式中：D——檢測(cè)距離,

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

Lupper——第k維的上界；

Llower——第k維的下界；

Dmax——檢測(cè)距離上界；

β——記憶因子，這兩個(gè)參數(shù)與所選目標(biāo)函數(shù)是否有為多峰值有關(guān)，具體映射關(guān)系如下。

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

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

3　仿真及實(shí)驗(yàn)結(jié)果

在C#編程環(huán)境下進(jìn)行了仿真實(shí)驗(yàn)，假定無(wú)人機(jī)的飛行區(qū)域?yàn)橐粋€(gè)700 m×700 m的正方形區(qū)域，包括6個(gè)威脅圈，其威脅分布見(jiàn)表1。

表1　威脅分布

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

仿真實(shí)驗(yàn)結(jié)果見(jiàn)圖1、圖2、表2。

圖1　各種算法生成的最優(yōu)航跡圖

圖2　平均最優(yōu)適應(yīng)度的收斂曲線

算法改進(jìn)QPSOGAQPSOQPSOPSODE平均最優(yōu)解282.683350.778312.227389.796370.522

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

4　結(jié)束語(yǔ)

由于無(wú)人機(jī)續(xù)航能力有限，因此有必要合理地規(guī)劃無(wú)人機(jī)路徑以降低能耗。本文提出的一種基于改進(jìn)QPSO的無(wú)人機(jī)路徑規(guī)劃算法，與標(biāo)準(zhǔn)QPSO算法明顯不同之處在于，它可以根據(jù)粒子與局部吸引點(diǎn)和可行解邊界的距離動(dòng)態(tài)的修正粒子更新位置，增強(qiáng)粒子的擾動(dòng)特性，提高粒子跳出局部最優(yōu)的能力，進(jìn)而提高了種群的全局尋優(yōu)能力。仿真實(shí)驗(yàn)的結(jié)果表明，相對(duì)于標(biāo)準(zhǔn)QPSO、GAQPSO、PSO、DE等其他幾種算法，本文算法能夠找到更高質(zhì)量的最優(yōu)航跡，且同時(shí)成功地避開(kāi)了威脅區(qū)。不過(guò)，在幾種算法的比較中，本文算法的收斂速度并不是最快的。在下一步的研究工作中，將嘗試開(kāi)發(fā)本文算法與其他算法的混合算法，以進(jìn)一步提高其收斂速度，方便其更易應(yīng)用于實(shí)時(shí)環(huán)境。

[1] 傅陽(yáng)光,周成平,丁明躍.基于混合量子粒子群優(yōu)化算法的三維航跡規(guī)劃[J].宇航學(xué)報(bào),2010,31(12):2657-2664.

[2] 孫漢昌,朱華勇.基于概率地圖方法的無(wú)人機(jī)路徑規(guī)劃研究[J].系統(tǒng)仿真學(xué)報(bào),2006,18(11):3050-3054.

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

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

[5] 劉波,王凌,金以慧.差分進(jìn)化算法研究進(jìn)展[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] 方偉,孫俊,謝振平,等.量子粒子群優(yōu)化算法的收斂性分析及控制參數(shù)研究[J].物理學(xué)報(bào),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

國(guó)家自然科學(xué)基金(51579201)

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

TP24

A

1671-7953(2016)01-0099-04

研究方向:信息融合與工程優(yōu)化

E-mail:wtugyh@163.com