張建南， 劉以安， 王 剛

(1.江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

基于優(yōu)化粒子群算法的無人機航路規(guī)劃*

張建南1， 劉以安1， 王 剛2

(1.江南大學 物聯(lián)網(wǎng)工程學院，江蘇 無錫 214122； 2.中國艦船研究院，北京 100192)

針對粒子群優(yōu)化(PSO)算法的無人機(UAV)航路規(guī)劃問題，引入慣性權重和自然選擇對粒子群算法進行優(yōu)化，以提高基本粒子群算法收斂速度，防止陷入局部最優(yōu)。算法分析慣性權重對粒子群算法的影響，進而調(diào)整慣性因子，提高算法的搜索能力；利用自然選擇的便利性和規(guī)律性等特點,更新粒子群算法的粒子；同時通過對無人機的可行航向進行限定，縮小搜索范圍。仿真實驗表明:基于粒子群優(yōu)化算法的無人機航路規(guī)劃不僅縮短了最優(yōu)航路，而且提高了搜索速度。

無人機航路規(guī)劃； 粒子群優(yōu)化算法； 慣性權重； 自然選擇

0 引 言

近年來，隨著科學技術的不斷發(fā)展，無人機(unmanned aerial vehicle，UAV)作為控制偵察和作戰(zhàn)的重要手段，正逐漸受到世界各國軍方的關注，這促使科研人員對無人機的各個方面展開更深入的研究。無人機的航路規(guī)劃是無人機任務規(guī)劃的重要內(nèi)容之一，目的是在滿足燃料消耗、威脅以及飛行區(qū)域等約束條件下，為無人機規(guī)劃出一條從初始點到目標點航路評價達到最優(yōu)的飛行路線，以保證飛行任務的圓滿完成[1]。

航路規(guī)劃是一個空間搜索問題，受到國內(nèi)外大量學者的研究，它主要分為兩類：啟發(fā)式算法和進化算法。啟發(fā)式算法作為逐點搜索算法，其搜索空間龐大，計算量大，并且規(guī)劃效果對啟發(fā)函數(shù)的依賴性較強；進化算法是一種基于種群的優(yōu)化算法，常用的進化算法有A*算法[2]、蟻群算-法[3]和遺傳算法[4]等。這些算法自身都存在一定的缺陷，使得路徑搜索存在搜索量大，效率不高等問題，不能保證航路規(guī)劃設計的效率和要求。粒子群算法是智能算法的代表方法之一，是一種以隨機搜索為特征的智能算法，通過群體粒子之間的合作與競爭產(chǎn)生的群體智能指導優(yōu)化搜索，具有實現(xiàn)容易、精度高、方便調(diào)整參數(shù)等優(yōu)點，因而在航路規(guī)劃問題中得到了廣泛的應用[5]。

粒子群算法思路清晰、運算簡單、易于實現(xiàn)，廣泛用于解決各種優(yōu)化問題，但是也存在著早熟現(xiàn)象、收斂速度慢，過早陷入局部最優(yōu)等缺點[6]。針對粒子群算法存在的問題，對粒子群算法進行了優(yōu)化，使之適用于無人機航路規(guī)劃。

1 無人機航路規(guī)劃

1.1 飛行環(huán)境和任務規(guī)劃

無人機航路規(guī)劃問題實質(zhì)屬于最優(yōu)化問題，它的數(shù)學描述由航路優(yōu)化指標和航路約束條件兩部分組成。求解航路規(guī)劃問題，就是在滿足約束條件的前提下，求出航路優(yōu)化指標函數(shù)的全局最優(yōu)解。航路規(guī)劃的目的是要根據(jù)任務要求，威脅分布，燃料限制以及無人機自身的機動性能選擇一條使無人機回避威脅，安全完成預定任務的飛行路徑[7]，無人機在空中飛行區(qū)域如圖1所示，其飛行任務是從O點飛行到A點，O點和A點之間存在威脅區(qū)，這些威脅可能是島嶼、陸地或者雷達，飛行航路就是搜索出一條從O點到A點的既短又安全的航路。

圖1 無人機任務規(guī)劃

1.2 編碼方式

假設無人機在某一巡航高度勻速飛行，則航路規(guī)劃可以簡化為建立在二維平面環(huán)境的基礎上[8]。先建立飛行高度相應的威脅平面分布，然后進行航路規(guī)劃。建立笛卡爾坐標系，定義航路初始點和目標點，將起始點到目標點進行n+1等分，令航路點在各個邊界上，這樣每一維的次序表示了粒子在x方向上的位置，每一維的數(shù)據(jù)表示粒子在y方向上的位置。通過這樣的方式，使每個粒子與起始點和目標點結(jié)合，這樣就構(gòu)成了無人機的一條航路[9]。

1.3 無人機航路規(guī)劃代價模型

無人機的航路規(guī)劃不僅要使無人機避開可能影響飛行的地形和威脅區(qū)域等不利因素，且要求規(guī)劃出的航路優(yōu)化指標最優(yōu)，通常根據(jù)優(yōu)化指標不同，航路優(yōu)化分為不同的類型，包括以燃料消耗為指標的最大航程規(guī)劃、以無人機飛行距離為指標的最短航程規(guī)劃和以戰(zhàn)術效果為指標的最優(yōu)戰(zhàn)術效果規(guī)劃。本文主要考慮無人機的航程代價和威脅代價，其描述為

(1)

航路代價為各個航路段代價之和，設整個航路有n個航路段組成，j為威脅源的數(shù)量，li表示第i個航路段的長度，航程代價的作用是使飛機在降低油耗和縮短飛行時間的同時保證航路最短。在雷達參數(shù)保持一致的情況下，無人機在任務區(qū)域內(nèi)的x處受到的第j個威脅源的威脅代價為[10]

(2)

在飛機飛行高度的水平截面上，雷達及區(qū)域威脅范圍可近似看作一個圓，Rj表示無人機到區(qū)域中心的距離，Kj為第j個威脅的強度參數(shù)。采用如下方法處理：在每個航路段上取其兩端點和中點三個點，分別求此三點受到的威脅體的威脅概率，則此航路段受到的威脅概率用這兩點受到的威脅概率之和來表示。航路的威脅代價為各航路段威脅代價之和。式(1)中的w1，w2為權重系數(shù)，用以調(diào)整不同代價在航路代價中的權重。

2 基于粒子群算法的無人機航路規(guī)劃

2.1 標準粒子群算法

粒子群算法是模擬鳥群隨機搜尋食物的捕食行為，用于解決優(yōu)化問題。在粒子群算法中每個優(yōu)化問題的潛在解都可以想象成搜索空間的一只鳥，稱之為“粒子”。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應度值，每個粒子還有一個速度決定它們的飛行的方向和距離。然后粒子就追隨當前的最優(yōu)粒子在解空間中搜索[11]。

粒子群算法初始化一群隨機粒子，然后通過迭代找到最優(yōu)解[12]。在每一次迭代過程中，粒子通過跟蹤兩個極值來跟新自己：第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。假設在一個d維的目標搜索空間中，有n個粒子組成一個群落，其中，第i個粒子為一個d維向量

Xi=(xi1,xi2,…,xid),i=1,2,…,n

第i個粒子的飛行速度也是一個d維向量，記為

Vi=(vi1,vi2,…,vid),i=1,2,…,n

第i個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為

Pbest=(pi1,pi2,…,pid),i=1,2,…,n

整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為

gbest=(pg1,pg2,…,pgd)

在找到這兩個最優(yōu)值時，粒子根據(jù)式(3)、式(4)來更新自己的速度和位置

vid=w·vid+c1r1(pid-xid)+c2r2(pgd-xid)

(3)

xid=xid+vid

(4)

式中w為慣性權重，c1，c2為加速度因子，r1，r2為[0,1]中的均勻隨機數(shù)[13]。

2.2 粒子群算法的改進

2.2.1 線性遞減權重法

針對基本粒子群算法容易早熟及容易在全局最優(yōu)解附近產(chǎn)生振蕩現(xiàn)象，本文提出線性遞減權重法，使慣性權重依照從大到小遞減[14]，其變化公式為

(5)

式中wi為慣性權重最大值，wf為慣性權重最小值，t為當前迭代步數(shù)，tmax為最大迭代次數(shù)。

2.2.2 自然選擇法

基于自然選擇法是借鑒自然選擇的原理，以提高粒子群算法的收斂速度，防止陷入局部最優(yōu)，在每次迭代中，根據(jù)粒子群適應值將粒子排序，用群體中最好的一半粒子替換最差的一半粒子，同時保留每個個體所記憶的歷史最優(yōu)值。

2.3 路徑優(yōu)化

由于自身性能限制及使用條件，要求無人機在飛行過程中滿足相應的約束，進行路徑優(yōu)化[15]?；韭窂絻?yōu)化流程：限制航路長度必須小于預設的最大距離，減小搜索范圍，規(guī)劃不能超出搜索空間的范圍，提高粒子群算法收斂速度；當無人機從某一個航路段向下一個航路段飛行時，受到無人機機動能力的限制，給無人機設置最大的拐彎角，規(guī)定其航向角不能超過45°，直到找到適合的航路[16]。

2.4 算法流程

1)任務區(qū)初始化，建立地形信息，初始化粒子群算法參數(shù)，包括群體規(guī)模n、每個粒子的位置Xi和速度vi，以及各項參數(shù)。

2)計算粒子適應度值，求全局最優(yōu)粒子gbest，并將Pbest設置為每個粒子的當前位置。

3)根據(jù)速度和位置更新公式，更新每個粒子的速度和位置。

4)將每個粒子的適應值與粒子的最好位置比較，如果相近，則將當前值作為粒子最好的位置。比較當前所有的Pbest和gbest，更新gbest。

5)根據(jù)適應值對粒子群排序，用群體中最好的一半粒子替換最差的一半粒子，同時保留原來每個個體所記憶的歷史最優(yōu)值。

6)當算法達到其停止條件，則停止搜索并輸出結(jié)果，否則,返回到步驟(3)繼續(xù)搜索。

3 仿真驗證

本文在Matlab 7.6環(huán)境下對無人機航路規(guī)劃進行仿真，驗證所提出的方法的有效性。任務區(qū)如圖2,無人機起始位置(0,0)，目標點位置(500,0)，任務區(qū)有4處威脅區(qū)，如圖中圓形區(qū)域所示。令終止迭代次數(shù)為1 000，粒子個數(shù)為200，粒子維數(shù)為10，加速度因子r1=r2=0.8，w=0.8，航程和威脅代價權重系數(shù)w1=w2=0.5，如圖2所示,無人機需要從起始點繞過威脅區(qū)飛行到目標點。

圖2 無人機航路規(guī)劃任務區(qū)

圖3和圖4為基本粒子群算法航路規(guī)劃圖，如圖所示，仿真結(jié)果最后收斂為286.92。圖5和圖6為優(yōu)化粒子群算法航路規(guī)劃圖，根據(jù)式(5)更新慣性權重因子,設置w1=0.9，wj=0.4，在每次迭代結(jié)束時采用自然選擇更新粒子，按照適應度值對所有粒子進行排序，用群體較好的50 %粒子代替較差的50 %粒子，更新粒子速度和位置，優(yōu)化算法使得航路規(guī)劃路線長度變短，路線趨向于平和，優(yōu)化后的算法收斂到273.86，可以看出當改變慣性權重和采用自然選擇優(yōu)化粒子群算法時，收斂速度明顯加快，同時相應地縮小了航路長度。所以改進方法得到了驗證。

圖3 基本粒子群算法航路規(guī)劃結(jié)果

圖4 基本粒子群算法適應值收斂圖

圖5 優(yōu)化粒子群算法航路規(guī)化結(jié)果

圖6 優(yōu)化粒子群算法適應值收斂圖

4 結(jié)束語

本文將優(yōu)化粒子群算法應用于無人機的航路規(guī)劃，利用改變慣性權重，調(diào)整慣性因子的方法，提高算法搜索能力，減小搜索空間，通過自然選擇優(yōu)化粒子群算法，提高算法收斂速度，防止陷入局部最優(yōu)，避免了早熟收斂問題，縮短了航路長度。實驗表明：基于優(yōu)化粒子群算法的航路規(guī)劃是一種相對有效和相對優(yōu)越的方法。

[1] 田 偉.無人作戰(zhàn)飛機航路規(guī)劃研究[D].西安：西北工業(yè)大學,2007.

[2] 穆中林,魯 藝,任 波,等.基于改進A*算法的無人機航路規(guī)劃方法研究[J].彈箭與制導學報,2007,27(1):297-300.

[3] 姚永杰,席慶彪,劉慧霞.基于改進遺傳蟻群算法的無人機航路規(guī)劃[J].計算機仿真,2011,28(6):44-47.

[4] Fei S U,Hui P,Shen L C.Research on multi-UCAV cooperative route planning based on coevolutionary multi-ant-colony algorith-m[J].Binggong Xuebao/Acta Armamentarii,2009,30(11):1562-1568.

[5] 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 & Humans,2012,42(2):511-526.

[6] 王 波,王燦林,梁國強.基于粒子群尋優(yōu)的D-S算法[J].傳感器與微系統(tǒng),2007,26(1):84-86.

[7] 胡中華,趙 敏,姚 敏.無人機三維航路規(guī)劃技術研究及發(fā)展趨勢[J].計測技術,2009,29(6):6-9.

[8] 翟彥蓉,黃 歡,張 申,等.改進粒子群優(yōu)化算法在TDOA定位中的應用[J].傳感器與微系統(tǒng),2013,32(4):145-148.

[9] 張仁鵬,楊金孝,潘佳華,等.基于改進粒子群算法的無人機三維航跡規(guī)劃[J].計算機仿真,2014,31(3):65-69.

[10] 李 猛,王道波,柏婷婷,等.采用威脅啟發(fā)粒子群算法的無人機航路規(guī)劃[J].電光與控制,2011,18(12):1-4.

[11] 胡中華,趙 敏.基于人工蜂群算法的無人機航跡規(guī)劃研究[J].傳感器與微系統(tǒng),2010,29(3):35-38.

[12] Wang G,Li Q,Guo L.Multiple UAVs routes planning based on particle swarm optimization algorithm[C]∥2010 the 2nd International Symposium on Information Engineering and Electronic Commerce(IEEC),IEEE,2010:1-5.

[13] 楊 遵,雷虎民.采用粒子群優(yōu)化算法規(guī)劃無人機偵察航路[J].電光與控制,2007,14(2):4-7.

[14] 孫 湘,周大為,張希望.慣性權重粒子群算法模型收斂性分析及參數(shù)選擇[J].計算機工程與設計,2010,31(18):4068-4071.

[15] 馬傳焱.多無人機飛行路徑自動規(guī)劃算法研究[J].無線電工程，2015，45(2)：5-7.

[16] 潘 杰.基于改進蟻群算法的移動機器人路徑規(guī)劃[J].中國礦業(yè)大學學報,2012,34(1):473-475.

UAV route planning based on PSO algorithm*

ZHANG Jian-nan1， LIU Yi-an1， WANG Gang2

(1.College of IOT Engineering,Jiangnan University,Wuxi 214122,China;2.China Ship Research and Development Academe,Beijing 100192,China)

Aiming at unmanned aerial vehicle(UAV)route planning problem of particle swarm optimization(PSO)algorithm,introduce inertia weight and natural selection to optimize PSO,in order to improve convergence speed of basic PSO,prevent fall into part optimum.Algorithm analyze on influence of inertia weight on PSO algorithm,and then adjust inertial factor,improve search ability of algorithm;Using characteristics of convenience and regularity of natural selection update particle of PSO;At the same time through limiting practical course of UAV,narrow search range.Simulation results show that,UAV route planning based on optimized PSO algorithm not only reduces the optimal route,but also improve search speed.

unmanned aerial vehicle(UAV); route planning; particle swarm optimization(PSO)algorithm; inertia weight; natural selection

10.13873/J.1000—9787(2017)03—0058—04

2016—04—25

國家自然科學基金資助項目(61170120)

TP 391

A

1000—9787(2017)03—0058—04

張建南(1991-)，男，碩士研究生，主要研究方向為信息對抗與系統(tǒng)仿真。