基于量子遺傳算法的無人機生命跡象探測研究

朱海斌 許峰

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

關鍵詞：無人機；路徑規劃；量子遺傳算法；收斂性

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 引言

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

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

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

1 無人機航跡規劃

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

1.1 無人機航跡規劃基本要求

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

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

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

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

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

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

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

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

2.1 生命跡象探測路徑優化數學模型

由于生命探測儀最大探測距離為1 000m，最大側視角為60°，根據簡單的三角函數關系可得探測帶寬為1 732m。

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

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

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

2.2 基于梯度的自適應量子遺傳算法

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

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

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

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

步驟1：生成初始種群，設定初始轉角步長與變異概率。

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

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

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

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

3 數值實驗結果

根據問題數據，利用基于梯度的自適應量子遺傳算法，得出2個區域內1～8號無人機的生命探測最優路徑（見圖1-圖8）。

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

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

4 結語

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

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

參考文獻：

[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] 孫陽光，丁明躍，周成平.基于量子遺傳算法的無人飛行器航跡規劃[J].宇航學報，2010，31（3）：648-654.

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

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

[10] 李士勇，李昐池.量子計算與量子優化算法[M].哈爾濱：哈爾濱工業大學出版社，2009.

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

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

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

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

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

（責任編輯：劉亭亭）