朱海斌 許峰

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

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

DOI：10.11907/rjdk.173052

中圖分類(lèi)號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

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

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

1.2 無(wú)人機(jī)生命跡象探測(cè)問(wèn)題

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

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

2 無(wú)人機(jī)生命跡象探測(cè)路徑優(yōu)化問(wèn)題的改進(jìn)量子遺傳算法

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4：對(duì)每個(gè)個(gè)體，根據(jù)變異概率用量子非門(mén)進(jìn)行變異。

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

3 數(shù)值實(shí)驗(yàn)結(jié)果

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

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

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

4 結(jié)語(yǔ)

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

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

參考文獻(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] 孫陽(yáng)光，丁明躍，周成平.基于量子遺傳算法的無(wú)人飛行器航跡規(guī)劃[J].宇航學(xué)報(bào)，2010，31（3）：648-654.

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

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

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

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

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

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

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

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

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