基于混沌遺傳算法的航跡優(yōu)化研究*

葉家君， 劉學文， 蔣 莎

(重慶師范大學 數(shù)學科學學院 重慶 401331)

近年來，由于地震、洪水等的頻繁發(fā)生使得無人機的研究成為國內(nèi)外的一種新潮。如何規(guī)劃無人機的路線，快速探測生命跡象以及對災(zāi)區(qū)的信號傳輸是無人機的一個重要使命。目前國內(nèi)外學者對無人機的航跡規(guī)劃進行了大量的研究。孫小雷等[1]研究了多無人機交會過程的協(xié)同航跡規(guī)劃，提出了沿Dubins路徑飛行，建立了以最小化執(zhí)行時間降低風險的雙目標規(guī)劃方法，實現(xiàn)了無人機可攻擊范圍的交會。李牧等[2]提出了基于3層決策模型的平滑航跡規(guī)劃方法，在不同場景地形的仿真，得到了較高的可執(zhí)行性、安全、平滑的飛行路徑。Wen等[3]建立了規(guī)劃成本最低、路徑搜索最快和路徑威脅最小的多目標優(yōu)化模型，引入RH方法解決了動態(tài)未知局部環(huán)境下的航跡規(guī)劃，用蒙特卡洛進行結(jié)果仿真，證明了該算法在實際路徑規(guī)劃中具有突防可能性。Chen等[4]提出了改進的狼群搜索算法，計算了三維真實空間和虛擬空間中無人機的最優(yōu)航跡，構(gòu)建了多目標成本優(yōu)化模型，仿真結(jié)果證明，改進后的WPS算法生成軌跡優(yōu)于原算法和隨機搜索方式。周青等[5]分析了無人機航跡規(guī)劃的路徑有效性和到達時間約束，并將遺傳算法應(yīng)用到動態(tài)環(huán)境中，通過編碼，明確適應(yīng)度函數(shù)和進化操作，實現(xiàn)了針對移動目標的規(guī)劃和突然出現(xiàn)威脅的局部重規(guī)劃。傅陽光等[6]在分析時間誤差分配基礎(chǔ)上，研究了起飛時間誤差、速度調(diào)節(jié)能力以及飛行速度誤差3個因素對目標點時間誤差的不同影響。張延松[7]指出了無人機航跡規(guī)劃的定義，根據(jù)威脅及障礙分布情況，構(gòu)造了無人機可能飛行的航路集voronoi圖，采用Dijkstra算法搜索威脅及障礙分布圖，最后通過遺傳算法優(yōu)化初始路徑，并進行仿真實驗。馬華偉等[8]建立了UAV流模型，提出了一種兩階段啟發(fā)式算法。第一階段提出了一種基于“最遲完成服務(wù)優(yōu)先”規(guī)劃的航跡，第二階段利用模擬退火算法對初始值進行改進，表明了該算法能有效求解帶有時間窗的UAV航跡問題。

本文以總路程最少和時間均衡度最小為目標，在無人機飛行約束條件下，建立了雙目標優(yōu)化模型。在模型求解時，通過引入混沌序列遺傳算法對模型進行求解，充分對雙目標進行平衡，得到更合適的航跡優(yōu)化路線。

1 多目標優(yōu)化模型

1.1 問題描述與假設(shè)

無人機航跡優(yōu)化路線是一個動態(tài)的過程，航跡過程中最顯著的特點表現(xiàn)在路線的最短化。以往的無人機航跡優(yōu)化路線局限于把“路線最短”作為優(yōu)化目標，容易導(dǎo)致不同無人機航跡時間間隔較大。因此，考慮“路線最短”和“時間均衡度最小”，在巡查有效區(qū)域內(nèi)，構(gòu)建綜合可靠性高的優(yōu)化路線。為了更好地分析問題，設(shè)立6個假設(shè)如下。

假設(shè)1 無人機在執(zhí)行任務(wù)時不存在強風、暴雨等天氣問題影響。

假設(shè)2 無人機在拐點處均以其最小轉(zhuǎn)彎半徑進行方向轉(zhuǎn)變，且行駛距離不變。

假設(shè)3 不同無人機飛行狀態(tài)不影響飛行速度。

假設(shè)4 無人機的位置始終處于最大有效探測距離內(nèi)。

假設(shè)5 無人機看成質(zhì)點，忽視無人機大小、質(zhì)量。

假設(shè)6 所有無人機同時起飛。

1.2 多目標優(yōu)化模型

由以上問題和分析可知，在無人機飛行高度及巡查范圍受到限制的情況下，構(gòu)建的目標優(yōu)化模型如下。

(1) 目標函數(shù)。首先考慮無人機航跡路線最短化，即無人機從各基地出發(fā)到最后返回各基地距離的加權(quán)值最小。子目標如下：

考慮到無人機航跡時間間隔最小化，即第一架無人機飛出時間與最后一架無人機返回時間的間隔最小。子目標如下：

保證同一架無人飛機pk受到燃油消耗的限制，其航行時間不超過8小時，即

根據(jù)上述分析，構(gòu)建多目標優(yōu)化模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

在本文中，將采用參數(shù)規(guī)劃方法中的加權(quán)法來求解上述兩個目標的航跡規(guī)劃模型。通過調(diào)節(jié)兩個目標賦值的權(quán)數(shù)，可以得出較為理想的結(jié)果。例如若α=1時，不再考慮均衡度，則所得結(jié)果將會出現(xiàn)第一架飛機飛出到最后一架飛機完成任務(wù)飛回到基地的時間間隔較長。若β=1，將不再考慮無人機飛行的總路程，則無人機可能在規(guī)定的時間無法完成任務(wù)。所以通過調(diào)整α和β的不同取值，將獲得一組權(quán)衡節(jié)解。

2 遺傳算法

顯然，無人機航跡規(guī)劃問題是一個NP問題，由于其解空間不連續(xù)，解空間表達困難，所以運用傳統(tǒng)的運籌學優(yōu)化方法不能滿足其需求[9]。那么，結(jié)合模型特點及實際應(yīng)用，將采用收斂性強，收斂速度快的遺傳算法。

(1) 染色體編碼。無人機航跡優(yōu)化模型轉(zhuǎn)換為遺傳算法問題，在編碼過程中將采用二進制串。根據(jù)無人機的架數(shù)將整個解空間分解為N個子種群，設(shè)每架無人機的航跡優(yōu)化路線是一條染色體，將染色體分為I段，I表示無人機飛過的有效區(qū)域點的位置。

(2) 初始種群的產(chǎn)生。遺傳算法盡可能獲取全局最優(yōu)解，與初始種群的選取有很大的聯(lián)系，子種群生成n條染色體作為無人機航跡路線。

(4) 染色體輪盤選擇。根據(jù)染色體的適應(yīng)度，計算出每條染色體的選擇概率以及累計概率pi，生成[0,1]間的隨機數(shù)ri，若ri≥pi，則選擇該染色體，重復(fù)這樣n次操作，將得到n條染色體。

(5) 改進的交叉操作。傳統(tǒng)的遺傳算法交叉操作通常采用斷點交叉法、多點交叉法和均勻交叉。根據(jù)本文的數(shù)學模型將采用改進型交叉。首先以“門當戶對”為原則，對父代的適應(yīng)度函數(shù)值進行排序，然后將父代目標函數(shù)值小的與小的配對，大的與大的配對。將采用Logistic混沌序列xn+1=4xn(1-xn)，隨機產(chǎn)生一個數(shù)Q，從而確定交叉點的位置，最后對確定的交叉項進行交叉。

(6) 改進的變異操作。同樣采用Logistic混沌序列xn+1=4xn(1-xn)，隨機產(chǎn)生一個數(shù)Q，對選定的染色體Q處選擇變異點進行變異。

(7) 終止。若滿足則算法終止，計算結(jié)束，輸出最佳適應(yīng)值和染色體編碼。根據(jù)染色體編碼繪制出相應(yīng)的無人機航跡路線。

3 實例分析

3.1 實例描述

為驗證上述改進算法的有效性，以2017年全國研究生數(shù)學建模競賽A題“無人機在搶險救災(zāi)中的優(yōu)化應(yīng)用”實例來驗證。為了及時探測生命跡象，提供準確的目標定位，欲使無人機攜帶生命探測儀從基地H(110，0)和J(110，55)(單位：km)處總共派出30架無人機(各15架)對生命跡象進行探測。其中無人機探測儀的有效探測距離不超過1 000 m，最大側(cè)視角為60°，最大續(xù)航時間為8 h，飛行時的轉(zhuǎn)彎半徑不小于100 m。在滿足無人機的飛行條件和生命探測儀的工作條件下，規(guī)劃合理路線，使得全區(qū)域內(nèi)海拔3 000 m以下部分能被探測到的面積盡可能大，且使從第一架無人機飛出到最后一架完成任務(wù)的無人機回到基地的時間間隔盡量短。

3.2 柵格分區(qū)

通過無人機探測儀的有效探測距離以及最大側(cè)視角，可知無人機可探測的最大面積以及無人機與地面的最大飛行高度。其次，分析哪些區(qū)域需要被巡查，可以利用“網(wǎng)絡(luò)取點”的方法確定有效的巡查點。由于有效巡查點是由兩個不同基地的無人機分別巡查。所以，將所有有效巡查點分成兩個區(qū)域，分別由兩個基地的無人機進行巡查，分區(qū)原則是兩個基地分別到區(qū)域各點并且最后返回各基地的用時基本相等，并且最長航跡與最短航跡路線距離相差較短。通過分區(qū)將兩個基地問題轉(zhuǎn)化成了單個基地問題，分別對兩個基地的無人機進行航跡規(guī)劃，如圖1所示。

圖1 H，J基地航跡有效區(qū)域

3.3 路線優(yōu)化

根據(jù)以上的有效巡查的分區(qū)，基于混沌遺傳算法和構(gòu)建的雙目標模型，用MATLAB進行編程，得到無人機從H,J基地出發(fā)的航跡路線(圖2)以及每架無人機的航跡路程和時間(表1)。

圖2 H，J基地航跡路線

在仿真實驗中，無人機航跡優(yōu)化問題分別利用了單點交叉和換位變異結(jié)合的遺傳算法，多點交叉和均勻變異結(jié)合的遺傳算法以及本文中的混沌序列遺傳算法進行求解比較(表2)，且都是以種群規(guī)模60，交配概率0.85，變異概率0.1和迭代次數(shù)500求解的無人航跡優(yōu)化路程。

表1 H，J基地的無人機航跡路程及時間Table.1 Flight path and time of H，J base UAV

表2 遺傳算法路程優(yōu)化比較Table.2 Distance optimization comparison of genetic algorithms

〗 最后，通過對H基地和J基地計算時間對比，來說明改進遺傳算法的時間性能(表3)。

表3 遺傳算法時間性能比較Table.3 Time performance comparison of genetic algorithms

利用改進后強度最弱的單點交叉，保證了算法的收斂精度，削弱了算法因交叉強度大而產(chǎn)生的尋優(yōu)抖振問題，而且文中采用了強度較大的多個基因變異解決了早熟問題。從表2可以看出改進后的算法效果更明顯，減少了無人機航跡路程。通過以上的圖和表格，可以得出以下的結(jié)論：

(1) 目標最小化模型可以有效處理無人機航跡問題，對于時間的均衡性可以有效調(diào)節(jié)無人機之間的時間間隔，能盡快完成全部任務(wù)。

(2) 從圖1和圖2可以看出，柵格分割以及將不同基地出發(fā)的無人機進行分區(qū)，更能避免無人機在執(zhí)行任務(wù)時發(fā)生碰撞。

(3) 由表1數(shù)據(jù)可知，無人機最少花費時間2.456h，最多花費時間3.950h，則時間間隔為1.494h。所以本文所給的航跡優(yōu)化模型以及混沌遺傳算法是具有一定的可行性。

(4) 根據(jù)表2和表3可知，混沌遺傳算法在求解無人機航跡優(yōu)化模型時有較好的性能。

4 結(jié) 論

針對無人機探測生命跡象這一難題，構(gòu)建了路程最短和時間均衡度最少的數(shù)學模型，設(shè)計了一種基于混沌遺傳算法的求解。但是，本文僅對無人機探測生命跡象做了一個初步探索，旨在能探測到更多的有效區(qū)域。因此，今后的研究工作將進一步推廣數(shù)學模型，希望無人機更廣泛地應(yīng)用在災(zāi)情巡查、災(zāi)區(qū)通信終端以及對地的數(shù)據(jù)傳輸。

參考文獻(References)：

[1] 孫小雷，孟宇麟，齊乃明，等. 多無人機交會過程的協(xié)同航跡規(guī)劃方法[J]. 機器人，2015，37(5)：621-627

SUN X L，MENG Y L，QI N M，et al. Cooperative Path Planning for Rendezvous of Unmanned Aerial Vehicles[J]. Robot,2015，37(5)：621-627

[2] 李牧東，趙輝，黃漢橋，等. 基于TLD模型的UAV三維實時平滑航跡規(guī)劃[J]. 系統(tǒng)工程與電子技術(shù)，2017，39(1)：93-100

LI M D，ZHAO H，HUANG H Q，et al.3-D Real-Time Smooth Path Planning for UAV Based on TLD Model[J]. Systems Engineering and Electronics,2017，39(1)：93-100

[3] WEN N,ZHAO L L,SU X H,et al. UAV Online Path Planning Algorithm in a Low Altitude Dangerous Environment[J]. IEEE/CAA Journal of Automatica Sinica,2015，2(2)：173-185

[4] CHEN Y B,MEI Y S,YU J Q,et al. Three Dimensional Unmanned Aerial Vehicle Path Planning Using Modified Pack Search Algorithm[J]. Neurocomputing, 2017，266(29)：445-457

[5] 周青，張銳，索曉潔，等. 具有時間約束的無人機遺傳算法航跡規(guī)劃[J]. 航空計算技術(shù)，2016，46(2)：93-96，101

ZHOU Q，ZHANG R，SUO X J，et al. Genetic Algorithm for UAV Trajectory Planning with Timing Constraints[J]. Aeronautical Computing Technique,2016，46(2)：93-96，101

[6] 傅陽光，周成平，王長青，等. 考慮時間約束的無人機飛行器航跡規(guī)劃[J]. 宇航學報，2011，32(4)：749-755

FU Y G，ZHOU C P，WANG C Q，et al. Path Planning for UAV Considering Time Constraint[J]. Journal of Astronautics,2011，32(4)：749-755

[7] 張延松.基于遺傳算法的無人機航跡規(guī)劃研究[J]. 中國西部科技，2010，9(11)：44-45

ZHANG Y S. Study on a Path Planning for UAV with Genetic Algorithm[J]. Science and Technology of West China,2010，9(11)：44-45

[8] 馬華偉，王天曉，胡笑旋. 帶有時間窗的無人機航跡規(guī)劃兩階段啟發(fā)式算法[J]. 火力與指揮控制，2014，39(8)：12-16，21

MA H W，WANG T X，HU X X. A Two-Stage Heuristic Method for UAV Path Planning with Time Windows[J]. Fire Control & Command Control,2014，39(8)：12-16，21

[9] 司守奎，孫璽菁. 數(shù)學建模算法與應(yīng)用[M].北京：國防工業(yè)出版社，2011

SI S K，SUN X J. Mathematical Modeling and Application[M]. Beijing：National Defense Industry Press,2011