朱海斌 許峰

摘 要：針對基本遺傳算法易早熟與局部搜索能力欠佳的缺陷，將一種改進的量子遺傳算法應(yīng)用于無人機生命跡象探測路徑優(yōu)化。在基本量子遺傳算法的基礎(chǔ)上，根據(jù)目標函數(shù)梯度自適應(yīng)地確定量子旋轉(zhuǎn)門轉(zhuǎn)角。數(shù)值實驗表明，該改進算法比基本量子遺傳算法有更好的局部收斂性與更快的收斂速度，可獲得比基本量子遺傳算法更優(yōu)的生命跡象探測路徑。

關(guān)鍵詞：無人機；路徑規(guī)劃；量子遺傳算法；收斂性

DOI：10.11907/rjdk.173052

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2018）006-0160-03

Abstract：An improved quantum genetic algorithm is applied to optimize the life sign detection path of UAV. On the basis of the basic quantum genetic algorithm， the rotation angle of the quantum rotation gate is adaptively determined according to the gradient of the objective function. Numerical experiments show that the improved algorithm has better local convergence and faster convergence speed than the basic quantum genetic algorithm， and obtains better life sign detection path than the basic quantum genetic algorithm.

Key Words：UAV； path planning； quantum genetic algorithm； convergence

0 引言

目前，無人機已廣泛應(yīng)用于軍事偵察、軍事打擊、城市規(guī)劃、資源調(diào)查、災(zāi)情巡查、生命救援等領(lǐng)域。無人機任務(wù)規(guī)劃中最重要的部分是航跡規(guī)劃，即在一定的約束條件下，尋找從起始點到目標點的最優(yōu)路徑。合理的航跡規(guī)劃不僅可以節(jié)省資源，提高飛行效率，還可以有效地規(guī)避災(zāi)害，提高生存概率。

無人機航跡規(guī)劃常用方法有隨機搜索法、Voronoi圖法與優(yōu)化方法[1]。無人機航跡規(guī)劃是包含復(fù)雜約束的大規(guī)模優(yōu)化問題，啟發(fā)式智能優(yōu)化算法目前已成為求解航跡規(guī)劃問題的主要方法，如蟻群算法、粒子群算法、模擬退火算法、遺傳算法等。早在1998年，Patcher[2]就討論了路徑規(guī)劃問題中的關(guān)鍵優(yōu)化技術(shù)及其復(fù)雜性；Dong， Zheng和Nikolos等[3-5]研究了路徑規(guī)劃中進化算法的優(yōu)化原理；Wu[6]最早將遺傳算法應(yīng)用于航行器路徑規(guī)劃問題；孫陽光等[7]最早將量子遺傳算法應(yīng)用于無人飛行器航跡規(guī)劃；魚佳欣等[8]將改進的量子遺傳算法應(yīng)用于無人機航跡規(guī)劃，獲得了較光滑的低代價航跡。

基本遺傳算法（SGA）對搜索空間與目標函數(shù)要求不高，適用面廣，魯棒性強，具有隱并行性，且全局搜索能力較強。但在求解復(fù)雜優(yōu)化問題時，基本遺傳算法經(jīng)常表現(xiàn)出易陷于局部最優(yōu)解與局部尋優(yōu)精度不高的缺陷。因此，本文將一種改進的量子算法（QGA）應(yīng)用于無人機生命跡象探測規(guī)劃問題，并根據(jù)數(shù)值實驗對該算法進行性能測試。

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

無人機航跡規(guī)劃是指在綜合考慮無人機的機動性能、碰地概率、突防概率、油耗、威脅與飛行時間約束等各種因素下，找到一條從起始點到目標點的最優(yōu)可行飛行軌跡。

1.1 無人機航跡規(guī)劃基本要求

無人機航跡規(guī)劃核心是從眾多飛行航跡中選擇滿足一系列約束條件的最優(yōu)航跡，既要減少被敵方摧毀的概率，又要降低自身可能撞地的概率，同時還要滿足無人機各種性能的約束條件。一般來說，無人機航跡規(guī)劃需要考慮下列因素：

（1）突防要求。無人機航跡規(guī)劃的首要因素是規(guī)劃航跡的隱蔽性，要使敵方雷達捕獲不到無人機，或者雖捕獲卻不能有效攔截，達到了突防目的。達到突防要求通常采用2種方式：一是使航跡遠離威脅源；二是利用地形遮擋降低被敵方探測到的概率。

（2）性能要求。航跡規(guī)劃必須考慮無人機的性能約束。無人機的性能限制對航跡的約束主要有：①最大轉(zhuǎn)彎角。此參數(shù)限制航跡只能在小于或等于該角度范圍內(nèi)轉(zhuǎn)彎；②最大爬升/俯沖角。此參數(shù)限制了航跡在垂直平面內(nèi)上升和下滑的最大角度；③最小航跡段長度。此參數(shù)限制了無人機在開始改變飛行姿態(tài)之前必須直飛的最短距離；④最低飛行高度。雖然低空飛行可以減少被敵方探測到的概率，但會增加與地面相撞的概率，所以航跡應(yīng)滿足最小飛行高度限制。此外，無人機航跡規(guī)劃還需考慮燃油限制與通信限制等。

（3）實時性要求。如果預(yù)先已掌握了規(guī)劃區(qū)域的完整信息，就可規(guī)劃出一條從起點到終點的最優(yōu)航跡。但現(xiàn)代戰(zhàn)場環(huán)境瞬息萬變，不能保證事先所獲信息不再發(fā)生變化。由于任務(wù)的不確定性，無人機有時臨時改變飛行任務(wù)，而預(yù)先規(guī)劃的航跡則不能滿足要求，這將要求無人機航跡規(guī)劃必須具有實時在線規(guī)劃功能。

1.2 無人機生命跡象探測問題

本文研究無人機生命跡象探測問題是根據(jù)2017年全國研究生數(shù)學(xué)建模競賽A題中問題二[9]改編。具體如下：

地震發(fā)生后，需使用無人機攜帶視頻采集裝置搜索生命跡象，給災(zāi)后救援提供準確的目標定位。擬從基地H（110，0），J（110，55）（單位：km）處總共派出8架無人機（各4架），任務(wù)完成后回到各自出發(fā)地。探測儀有效探測距離不超過1 000m，且最大側(cè)視角（探測儀到可探測處的連線與鉛垂線之間的夾角）為60°。規(guī)劃它們的飛行路線，使附件1所給出的全區(qū)域內(nèi)海拔3 000m以下部分能被探測到的面積盡可能大，從第一架無人機飛出到最后一架完成任務(wù)的無人機回到基地的時間間隔盡量縮短。

2 無人機生命跡象探測路徑優(yōu)化問題的改進量子遺傳算法

2.1 生命跡象探測路徑優(yōu)化數(shù)學(xué)模型

由于生命探測儀最大探測距離為1 000m，最大側(cè)視角為60°，根據(jù)簡單的三角函數(shù)關(guān)系可得探測帶寬為1 732m。

將區(qū)域內(nèi)的結(jié)點劃分為低于3 000m與高于3 000m兩部分。區(qū)域最高高度為4 867m，無人機限高5 000m，不存在需要繞飛的區(qū)域。對整個區(qū)域根據(jù)探測帶寬提取結(jié)點，連同基地H和J共有118個節(jié)點。

首先，需要將全部結(jié)點分成2部分，使這2部分最優(yōu)探測路徑長度之差盡量縮小，其次將這2部分路徑分配給8架無人機進行探測。分配方案滿足下列目標與約束條件：

式（1）～（3）中，T-i表示負責(zé)探測第i個地區(qū)的無人機飛行的總時間，表示無人機探測一個點消耗的平均時間，N-i表示第i個地區(qū)內(nèi)待探測的結(jié)點數(shù)，s-i表示區(qū)域i距離基地的距離，v是無人機的飛行速度。

2.2 基于梯度的自適應(yīng)量子遺傳算法

量子遺傳算法是將量子算法引入遺傳算法而得到的一種新型智能優(yōu)化算法，具有高并行性和指數(shù)級存儲的優(yōu)點，在計算復(fù)雜度與收斂速度方面明顯超過其它智能優(yōu)化算法，用對經(jīng)典啟發(fā)式算法進行加速[10]。

在常規(guī)量子遺傳算法中，編碼方式為量子位概率副編碼，個體交叉通過量子門的量子比特相位旋轉(zhuǎn)實現(xiàn)，而個體變異則用量子非門代替，所以量子遺傳算法的一個主要研究方面是進化策略的構(gòu)造與編碼方式[11]。目前，對基本量子遺傳算法的各種改進策略不斷涌現(xiàn)，并在許多領(lǐng)域得到了較好的應(yīng)用[12-14]。

權(quán)芳芳等[15]提出了一種基于梯度的自適應(yīng)量子遺傳算法，改進了確定量子旋轉(zhuǎn)門轉(zhuǎn)角大小的方法，其基本思想是：根據(jù)目標函數(shù)梯度的大小自適應(yīng)地確定轉(zhuǎn)角步長。當目標函數(shù)的梯度較小時，適當增加轉(zhuǎn)角步長，否則適當減小轉(zhuǎn)角步長。這樣既可以確保收斂速度，又兼顧了全局收斂性。

基于梯度的自適應(yīng)量子遺傳算法步驟如下[15]：

步驟1：生成初始種群，設(shè)定初始轉(zhuǎn)角步長與變異概率。

步驟2：對解空間進行變換，計算出每個染色體的適應(yīng)度。

步驟3：根據(jù)基于梯度的計算方法計算轉(zhuǎn)角大小及方向，從而確定新的量子位。

步驟4：對每個個體，根據(jù)變異概率用量子非門進行變異。

步驟5：若達到最大進化代數(shù)或滿足收斂條件，則停機，否則轉(zhuǎn)步驟2。

3 數(shù)值實驗結(jié)果

根據(jù)問題數(shù)據(jù)，利用基于梯度的自適應(yīng)量子遺傳算法，得出2個區(qū)域內(nèi)1～8號無人機的生命探測最優(yōu)路徑（見圖1-圖8）。

為評測基于梯度的量子遺傳算法在避免過早收斂方面的效果，圖9與圖10分別給出了基本遺傳算法（SGA）與基于梯度的量子遺傳算法（GQGA）的進化曲線。圖9與圖10表明：①GQGA無論在全局收斂性與局部收斂性均全面優(yōu)于SGA；②SGA至少在2個階段出現(xiàn)了過早收斂于局部最優(yōu)解的現(xiàn)象，而GQGA則完全避免了早熟現(xiàn)象。

綜上所述，在無人機航跡規(guī)劃中若采用基于梯度的量子遺傳算法，將獲得比基本遺傳算法更優(yōu)的航跡規(guī)劃。

4 結(jié)語

本文針對基本遺傳算法易過早局部收斂與局部搜索能力較弱的缺陷，在無人機航跡規(guī)劃問題中引入基于梯度的量子遺傳算法。數(shù)值實驗表明，這種算法在很大程度上克服了基本遺傳算法的早熟現(xiàn)象，較好地解決了無人機航跡優(yōu)化問題。

必須指出的是，基于梯度的量子遺傳算法的突出優(yōu)點是較基本遺傳算法有較高的收斂速度。但由于本文所討論的問題較為簡單，這一優(yōu)點并未充分體現(xiàn)出來。另外，由于遺傳算法的理論遠未成熟，除了基本遺傳算法外，其收斂性無法得以證明，對算法的改進還只能依賴對比實驗，這無疑限制和阻礙了遺傳算法的進一步研究。

參考文獻：

[1] DOBROKHODOV V. Cooperative path planning of unmanned aerial vehicles[J]. Journal of Guidance Control & Dynamics，2014，34（5）：1601-1602.

[2] PATCHER M， CHANDLER P R. Challenges of autonomous control[J]. Control Systems IEEE，1998，18（4）：92-97.

[3] JIA D， VAGNERS J. Parallel evolutionary algorithms for uav path planning[C].Aiaa Intelligent Systems Technical Conference.2013.

[4] ZHENG C， LI L， XU F， et al. Evolutionary route planner for unmanned air vehicles[J]. IEEE Transactions on Robotics，2005，21（4）：609-620.

[5] NIKOLOS I K， VALAVANIS K P， TSOURVELOUDIS N C， et al. Evolutionary algorithm based offline/online path planner for UAV navigation[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society，2003，33（6）：898-912.

[6] WU X， FENG Z， ZHU J， et al. Ga-based path planning for multiple UAVs[J]. International Journal of Control，2007，80（7）：1180-1185.

[7] 孫陽光，丁明躍，周成平.基于量子遺傳算法的無人飛行器航跡規(guī)劃[J].宇航學(xué)報，2010，31（3）：648-654.

[8] 魚佳欣，李剛，李東濤.改進量子遺傳算法在無人機航路規(guī)劃中的應(yīng)用[J].計算機仿真，2015，32（5）：106-110.

[9] 2017全國研究生數(shù)學(xué)建模競賽試題http：//gmcm.seu.edu.cn/01/49/c12a329/page.htm.

[10] 李士勇，李昐池.量子計算與量子優(yōu)化算法[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2009.

[11] 梁昌勇，柏樺，蔡美菊.量子遺傳算法研究進展[J].計算機研究進展，2012，29（7）：2401-2405.

[12] 孫海超.改進的量子遺傳算法及其在圖像匹配中的應(yīng)用[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2012.

[13] 符麗錦.量子遺傳算法的改進及在貨物裝配問題中的應(yīng)用[D].南寧：廣西大學(xué)，2015.

[14] 趙海洋.基于改進量子遺傳算法的認知無線電頻譜分配研究[D].秦皇島：燕山大學(xué)，2015.

[15] 權(quán)芳芳，許峰.基于梯度的改進量子遺傳算法[J].軟件導(dǎo)刊，2012，11（8）：31-33.

（責(zé)任編輯：劉亭亭）