唐匯禹，彭世蕤，孫經(jīng)蛟，劉香嵐

(空軍預警學院，武漢 430019)

【信息科學與控制工程】

基于混沌DESAPSO算法的無人機三維航跡規(guī)劃

唐匯禹，彭世蕤，孫經(jīng)蛟，劉香嵐

(空軍預警學院，武漢 430019)

粒子群(PSO)算法易陷入局部最優(yōu)，將其運用于無人機三維航跡規(guī)劃會導致航跡品質(zhì)不高，針對這一問題，提出了將差分進化(DE)算法、模擬退火(SA)算法嵌入PSO算法中，構成混沌差分進化模擬退火粒子群(DESAPSO)算法，從三個方面提高了航跡品質(zhì)：一是利用DE算法的變異、交叉及競爭選擇增加種群多樣性；二是利用SA算法概率突跳能力跳出局部最優(yōu)解；三是對PSO算法參數(shù)進行混沌優(yōu)化，進一步增強種群多樣性。仿真結(jié)果表明：混沌DESAPSO算法改進航跡品質(zhì)效果明顯，獲得了滿意的無人機三維航跡。

混沌粒子群；差分進化；模擬退火；無人機；航跡規(guī)劃

無人機航跡規(guī)劃就是在滿足威脅回避、機動性能限制等約束條件下，求得一條從起始點到目標點的最優(yōu)或次優(yōu)航跡，其實質(zhì)為多目標優(yōu)化問題[1]。而三維航跡規(guī)劃搜索空間巨大，傳統(tǒng)的經(jīng)典算法諸如牛頓法、梯度法等已不適用，取而代之的是現(xiàn)代智能算法，其中具有代表性的包括粒子群算法(PSO)、遺傳算法、蟻群算法和模擬退火算法等[2]。

PSO算法[3]具有實現(xiàn)容易、計算精度高、收斂速度快的特點，且其易與其他算法相結(jié)合，衍生出許多性能優(yōu)良的算法。目前，已有許多學者將標準PSO算法及其改進算法運用于無人機航跡規(guī)劃中，取得了許多成果[4-6]。但標準PSO算法后期易陷入局部最優(yōu)，其根本原因是迭代后期粒子間相似度很高，種群多樣性缺失。為了解決這一問題，提高航跡規(guī)劃品質(zhì)，在此從以下三方面來增加粒子種群多樣性：一是利用差分進化算法的變異、交叉及競爭選擇操作來增加種群多樣性，其中變異和交叉算子采用非線性算子保證后期粒子若未能搜尋到全局最優(yōu)解時，仍具有較高的全局搜索能力；二是利用模擬退火算法的突跳能力增加種群多樣性，跳出局部最優(yōu)找到全局最優(yōu)；三是對PSO算法的參數(shù)采用混沌序列保證不重復遍歷整個空間，進一步增強種群多樣性。

將改進后的混沌DESAPSO算法運用于無人機三維航跡規(guī)劃，通過與其他算法對比表明該算法性能優(yōu)良。

1 無人機三維航跡規(guī)劃建模

1.1 航跡編碼

無人機航跡是由離散的導航節(jié)點直線相連而成的線路，算法中每個粒子的信息代表一條航跡。因此，可假設粒子數(shù)目為N，每條航跡除起始點和目標點外共有m個導航節(jié)點，整個種群可表示為：X=[X1,X2,…,XN]T，其中Xi為第i個粒子的位置。令Xi=[x0,xi1,…，xim,xt,y0,yi1，…，yim,yt,z0,zi1，…，zim,zt]，其中(x0,y0,z0)、(xt,yt,zt)為航跡起始點和目標點，(xim,yim,zim)為第i個粒子中第m個導航節(jié)點的三維坐標。

另外，考慮粒子位置雖可進行限制，但粒子運動是不定方向的、隨機的，為確保粒子能從起始點朝著目標點方向運動，可采取對粒子x軸坐標進行固定均分，即將[x0,xt]均分成(m+1)段，y軸和z軸只做限制，不做均分。粒子在進行位置更新和限制時，只對y軸和z軸中除起始點和目標點外的m個導航節(jié)點進行操作。

1.2 航跡適應度函數(shù)

智能優(yōu)化算法運用于航跡規(guī)劃，需建立合適的適應度函數(shù)，適應度函數(shù)值即無人機飛行代價，該值是評價航跡優(yōu)劣的唯一指標。無人機的適應度函數(shù)包括兩大方面，分別為機動性能約束和威脅約束。其中，機動性能約束主要包括最大爬升角/下滑角、最大水平轉(zhuǎn)彎角、最大航程、最小步長、最小轉(zhuǎn)彎半徑；威脅約束主要包括火力威脅、地形威脅和高度威脅。

對于機動性能約束代價，可參考文獻[5]。其中最大爬升角/下滑角和最大水平轉(zhuǎn)彎角代價函數(shù)表達式相同，最大航程代價和步長程度代價改進后分別如式(1)、式(2)所示。

(1)

其中，ltotal為總路程，L為起始點到目標點的直線距離，Lmax為無人機的最大航程。

(2)

其中，Lstep為步長程度標準值，Li為相鄰節(jié)點的航跡長度。

而最小轉(zhuǎn)彎半徑約束，可通過爬升下滑角/水平轉(zhuǎn)彎角、步長程度以及高度變化來合理控制，因此不對其另行約束，高度變化代價如式(3)所示：

(3)

其中，Δhi為相鄰節(jié)點的高度變化值，CΔh為安全閾值。

威脅代價中的雷達威脅，可參考文獻[7],導彈威脅和高炮威脅可參考文獻[8]，對三種威脅進入禁飛區(qū)的情況，對式(1)施加懲罰K；地形威脅代價參考文獻[8]，對進入禁飛區(qū)的情況同樣施加懲罰K，另外將山峰地形等效成圓錐體存在一定誤差，因此設置無人機飛行高度比當前地形高度高某一數(shù)值Clim，以此保證安全飛行，如式(4)所示：

(4)

其中，z(x,y)為無人機當前坐標的地形高度，z為無人機當前高度。

高度威脅可設置如式(5)所示的代價函數(shù)。

(5)

其中：z為當前飛行高度，Hmin為最小離地高度，Hmax為無人機以概率1被發(fā)現(xiàn)的高度。

綜上，對任意航跡Xi，其航跡總代價如式(6)所示，通過設置不同的權值可以合理評價各代價對航跡的影響。

(6)

其中，N為粒子數(shù)；fk為各代價函數(shù)；M為代價種類數(shù)，ω1～ωM為相應的權值，其和值為1。

2 混沌DESAPSO算法

2.1DE算法

DE算法[9]包括變異、交叉以及競爭選擇3步：首先，對第t代第i個粒子中的除開起始點和目標點外的y坐標和z坐標進行差分變異得到變異個體Ui(t+1)：

Ui(t+1)=Xr1,j(t)+F(Xr2,j(t)+Xr3,j(t))

(7)

其中，r1、r2、r3為[1,N]的隨機整數(shù)，且滿足r1≠r2≠r3≠i，j為除開起始點和目標點外的y坐標和z坐標，F(xiàn)為非線性變異算子，如式(8)所示：

(8)

其中，F(xiàn)max、Fmin分別為變異算子的最大值和最小值，T為最大迭代次數(shù)。

然后，對產(chǎn)生的變異個體進行交叉操作得到實驗個體Vi, j(t+1)：

(9)

其中，CR為交叉率，采用如式(10)的非線性變異算子，randni為[m+3,2m+3]和[2m+6,3m+5]間的隨機整數(shù)，m為前述導航節(jié)點數(shù)，這樣做是保證實驗個體Vi, j(t+1)至少有一位是由變異個體Ui, j(t+1)貢獻。

(10)

最后，對實驗個體Vi(t+1)和種群個體Xi(t)進行競爭選擇得到新一代種群個體Xi(t+1)：

(11)

2.2 混沌PSO算法

PSO算法起源于群鳥覓食，對于前述編碼方式，可假設每個粒子速度為Vi=(vi1,vi2,…,viN)，粒子個體的最好位置為Pi=(pi1,pi2,…,piN)，其適應值稱為個體極值，粒子群的最好位置為Pg=(pg1,pg2,…,pgN)，其適應值稱為全局極值，粒子依據(jù)下式進行速度和位置更新：

(12)

(13)

其中，ω為[0,1]內(nèi)的慣性因子，c1、c2稱為學習因子，一般取2；r1、r2為[0,1]內(nèi)變化的隨機數(shù)，為確保不重復遍歷整個搜索空間，可對參數(shù)r1、r2采取的混沌操作，混沌序列為logistic模型如式(14)。

(14)

2.3SA算法

SA算法[10]起源于固體退火過程，在采用了如式(15)所示的Metropolis準則后，算法具有以概率1收斂到全局極值的能力。

(15)

其中，Δf為后一代粒子適應值和前一代粒子適應值的差值，exp(-Δf/T(t))>rand項是為了保證前期溫度較高時，即使后一代粒子適應值較差，仍具有以較高概率exp(-Δf/T(t))接受裂解的可能，從而跳出局部最優(yōu)。后期隨著溫度降低，粒子接受裂解的可能變得極小，從而逐漸收斂到全局最優(yōu)。要注意的是，后期雖然接受裂解概率極小，但不能排除有接受裂解的可能，因此應該實時保存迭代過程中找尋到的歷史最優(yōu)解。T(t)為當前迭代溫度，溫度衰減一般采用如式(16)的線性衰減，α為溫度衰減系數(shù)，取值范圍在[0.5,0.99]。

T(t)=α*T(t-1)

(16)

2.4 混沌DESAPSO算法流程

混沌DESAPSO算法是以PSO算法為主流程，主要過程包括三步：一是利用改進的DE算法對種群進行變異、交叉和競爭選擇；二是利用混沌參數(shù)r1、r2對PSO種群進行再次遍歷尋優(yōu)；三是利用SA算法的Metropolis準則促使粒子群跳出局部最優(yōu)，最終收斂到全局最優(yōu)。

混沌DESAPSO算法具體步驟如下：

步驟1:初始化算法所有參數(shù)，包括粒子數(shù)N、最大迭代次數(shù)T、變異因子F、交叉因子CR、慣性權重ω、學習因子c1、c2、r1、r2、以及退火初始溫度T0和溫度衰減系數(shù)α，初始化種群位置和速度，且t=1；

步驟2:計算每個粒子的適應值，初始化個體極值pbest和全局極值gbest；

步驟3:迭代開始，按式(7)、式(9)和式(11)對初始化的粒子種群進行變異、交叉和競爭選擇，更新個體極值pbest和全局極值gbest；

步驟4:按式(12)、式(13)對粒子進行速度和位置更新，進行速度和位置限制使其不超過邊界，計算每個粒子適應值，進行個體極值和全局極值更新；

步驟5:計算前后代粒子的適應值差值Δf，按式(15)進行模擬退火操作，按式(16)進行降溫操作；

步驟6:判斷t是否小于等于最大迭代次數(shù)T，若是，轉(zhuǎn)到步驟3；若否，算法結(jié)束，輸出最優(yōu)航跡。

3 仿真驗證

本文特征地形模型參考文獻[11]，模擬5座山峰，山峰中心坐標分別為(40,40)、(50,160)、(100,100)、(140,50)、(160,170)，山高Hi=[2.5,2.8,3.2,2.8,2.5]，無人機起點和終點分別為(10,10,2)、(130,110,3)，上述單位均為km。雷達威脅、導彈威脅以及高拋威脅參數(shù)如表1所示。

表1 威脅信息

分別用PSO算法、SAPSO算法以及混沌DESAPSO算法進行無人機三維航跡規(guī)劃，各算法獨立連續(xù)獨立運行30次進行分析對比，混合算法參數(shù)同單一算法參數(shù)全部取相同，算法參數(shù)設置如下：PSO算法參數(shù)，粒子數(shù)目N=30，最大迭代次數(shù)T=500，慣性權重ω從0.9線性遞減至0.2，學習因子c1=c2=2；SA算法參數(shù)，初始溫度T0=4 000，溫度衰減系數(shù)α=0.98；DE算法參數(shù)，變異因子F從0.7非線性遞減至0.4，交叉因子從0.3非線性遞增至0.8。各算法運行結(jié)果如表2所示。

表2 三種算法測試結(jié)果

從測試結(jié)果可以看出：PSO算法、SAPSO算法以及混沌DESAPSO三種算法收斂精度和穩(wěn)定性依次不斷提高，表明航跡規(guī)劃品質(zhì)不斷提高；從數(shù)值變化來看，由于導航節(jié)點少、概率代價模型數(shù)值小以及對代價進行了1/13的加權平均，因此航跡品質(zhì)改善明顯；從平均時間來看，前兩種算法復雜度相近，由于SAPSO算法收斂精度較PSO更高，因此平均耗時更短，而混沌DESAPSO復雜度明顯高于前兩種算法，以犧牲時間為代價獲得了精度的提升。各算法迭代收斂曲線如圖1(a)所示，局部放大如圖1(b)所示。

由圖1可知，混沌DESAPSO算法收斂速度最快，大約到10代就接近收斂到全局極值，PSO算法次之，SAPSO算法最慢。本文給出PSO算法和混沌DESAPSO算法二維及三維航跡對比圖，分別如圖2(a)、(b)和圖3(a)、(b)。

由圖2和圖3可知：從二維航跡看，兩種算法都能找到滿足威脅回避、地形回避的可行航跡，且混沌DESAPSO算法能找到更加利用山峰遮蔽的二維航跡；從三維航跡看，混沌DESAPSO算法能找尋到高度更低、更靠近山峰飛行的三維航跡，也因此航跡品質(zhì)更高，驗證了航跡改善的有效性。

圖1 三種算法迭代收斂曲線

圖2 PSO和混沌DESAPSO算法二維航跡

圖3 PSO和混沌DESAPSO算法三維航跡

4 結(jié)論

本文針對將PSO算法運用于無人機三維航跡規(guī)劃時易陷入局部最優(yōu)，導致航跡規(guī)劃品質(zhì)不高的問題，提出將DE算法、SA算法嵌入到PSO算法中，并對PSO算法參數(shù)進行混沌優(yōu)化以增加后期種群多樣性，從而利用三種算法各自優(yōu)點提高航跡規(guī)劃品質(zhì)。仿真結(jié)果表明：混沌DESAPSO算法對航跡品質(zhì)改進效果明顯，獲得了滿意的無人機三維航跡。

[1] 于成龍，劉莉，王祝,等.基于物理規(guī)劃的無人機多目標航跡規(guī)劃[J].電光與控制,2015,21(5):1-5.

[2] 王俊，周樹道，朱國濤,等.無人機航跡規(guī)劃常用算法[J].火力與指揮控制,2012,37(8):5-8.

[3] KENNEDY J，EBERHART R C.Particle Swarm Optimization[C]//Proceedings of the 1995 IEEE International Conference on Neural Networks,1995:1942-1948.

[4] 方勝良，余莉，汪亞夫.基于粒子群算法的無人機航跡規(guī)劃[J].計算機仿真,2010,27(8):41-43.

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

[6] 丁偉峰，汲萬峰，嚴建鋼，等.基于種群多樣性測度的PSO算法及其應用研究[J].現(xiàn)代防御技術,2012,40(4):143-149.

[7] 王緒芝.不確定環(huán)境下無人機航跡動態(tài)規(guī)劃及仿真研究[D].南京:南京航空航天大學,2013.

[8] 胡中華.基于智能優(yōu)化算法的無人機航跡規(guī)劃若干關鍵技術研究[D].南京:南京航空航天大學,2011.

[9] 劉建平.基于混沌和差分進化的混合粒子群優(yōu)化算法[J].計算機仿真,2012,29(2):208-211.

[10]楊曉龍，曲東才.一種基于遺傳模擬退火算法的航跡優(yōu)化方法[J].四川兵工學報,2013,34(12):66-70.

[11]彭志紅，孫琳，陳杰.基于改進差分進化算法的無人機在線低空突防航跡規(guī)劃[J].北京科技大學學報,2012,34(1):96-101.

(責任編輯 楊繼森)

3-D Route Planning of UAV Based on Chaotic DESAPSO Algorithm

TANG Hui-yu, PENG Shi-rui, SUN Jing-jiao, LIU Xiang-lan

(Air Force Early Warning Academy, Wuhan 430019，China)

Particle Swarm Optimization (PSO) algorithm is easy to fall into local optimum, and being applied to 3-D route planning of UAV will result in poor quality. To solve this problem, the chaotic DESAPSO algorithm was put forward by embedding the differential evolution (DE) algorithm and the simulated annealing (SA) algorithm in the chaotic PSO algorithm. The quality of the route was improved from three aspects, the first is to increase diversity of the population by using variation, crossover and competitive selection of DE algorithm; and the second is to jump local optimum by using the probabilistic jumping ability of SA algorithm; and the third is to increase diversity of the population further by chaotic optimization in the parameters of PSO algorithm. The results of simulation show that the quality of route was obvious improved by the chaotic DESAPSO algorithm, and the 3-D route was satisfied.

chaotic particle swarm optimization；differential evolution; simulated annealing; UAV； route planning

2016-08-14；

2016-09-20

唐匯禹(1991—)，男，碩士研究生，主要從事信息與通信工程研究。

10.11809/scbgxb2017.02.021

唐匯禹，彭世蕤，孫經(jīng)蛟，等.基于混沌DESAPSO算法的無人機三維航跡規(guī)劃[J].兵器裝備工程學報，2017(2):92-96.

format:TANG Hui-yu, PENG Shi-rui, SUN Jing-jiao, et al.3-D Route Planning of UAV Based on Chaotic DESAPSO Algorithm[J].Journal of Ordnance Equipment Engineering,2017(2):92-96.

TP301.6

A

2096-2304(2017)02-0092-05