基于改進遺傳算法的多無人機搜索航路規劃

鄧 灝, 唐希浪, 蔡忠義, 于 沖

(空軍工程大學裝備管理與無人機工程學院,西安 710000)

0 引言

近年來,無人機在軍事領域的地位日益凸顯。在任務偵察與敵情搜索方面,無人機具有機動性強、定位精度高等優勢,可有效彌補航天偵察過境時間受限和技術偵察難以定位電磁靜默目標的不足。相較于單架無人機,采用多架無人機與多種型號無人機對目標進行協同搜索可從不同方位對目標區域進行觀測,減小因單架無人機性能有限產生的搜索限制,從而提高無人機在復雜戰場環境下的整體作戰能力,具有很大應用價值。

無人機對特定區域內的目標搜索本質上屬于無人機路徑規劃問題。對于多無人機搜索而言,搜索過程中不僅要分析區域內目標活動熱值分布特點,還需考慮各架無人機的性能約束與彼此間的信息共享,并依據協同搜索概率動態調整航行計劃,進而規劃出各架無人機的搜索路徑。

在無人機路徑規劃方面,國內外學者從不同角度開展了大量研究。常用的無人機路徑規劃算法有粒子群算法[1]、A*算法[2]、遺傳算法[3-4]等。林陽芷等[5]基于模擬退火算法與改進遺傳算法建立了無人機對特定目標檢測的航路規劃模型,并引入修補算子來修復變化算子所產生的非法路徑,但未考慮無人機機動性能與機載雷達探測頻率等因素,影響了模型真實性;李楠等[6]對遺傳算法的選擇算子和變異算子進行改進,提高了算法收斂到最優解的速率和算法穩定性,但在一定程度上會導致種群多樣性降低,進而誘發算法過早收斂;王啟明等[7]提出一種改進遺傳算法,利用貪心算子優化初始種群路線,進而提高算法挖掘能力,但隨著種群適應度的提高,貪心算子會增加算法陷入局部最優解的風險,降低全局搜索能力; 文獻[8]基于深度強化學習進行機器人網格路徑規劃,利用深度網絡將觀測信息應用于動作選擇,并在簡單的方格迷宮中得到實現和驗證,但對于解決目標信息不確定的環境探測問題算法效益有待提高。

根據上述文獻中算法策略的優缺點,本文結合貪婪算法思想,對變異操作進行了改進并提出貪婪變異策略與隨機變異策略,有效解決了無人機在搜索后期對高熱值地區重復搜索問題;同時設置策略選擇閾值,做到依據種群適應度變化自適應選擇變異策略,保證算法前期的全局搜索能力并提高后期的局部搜索能力;偵察搜索模型實現了無人機機動性能與機載雷達探測屬性間的均衡考慮,增強了模型的泛化能力。

1 環境模型

環境模型起著將區域環境信息抽象轉化成利于計算機處理的數據信息的作用[9],是無人機實現航路規劃的前提和基礎。基于無人機機載雷達探測半徑與目標活動半徑之間的關系,本文對目標區域采取柵格化建模方法以考慮二維情形下的無人機協同搜索任務。

根據目標活動的歷史數據與各方情報綜合制成了偵察區域目標活動熱圖,從藍色到黃色表示目標活動頻率遞增。將偵察區域內的目標活動熱圖進行柵格化,如圖1所示。考慮到無人機出發區域的大小對航路規劃無明顯影響,因此忽略出發區域大小。圖1中點A(xA,yA)表示無人機出發處。

圖1 偵察區域目標活動熱圖柵格化

柵格的尺寸大小由目標活動半徑r0決定,可認為目標在半徑為r0的圓內進行機動,所以正方形柵格邊長為2r0,并依據先驗情報計算出每個柵格所包括的2r0×2r0面積區域內目標活動概率之和作為柵格熱度值q。而后對柵格進行編號,(λ,ε)表示第λ行、第ε列的柵格,并求出每個柵格的中心點坐標(xλ,yε),作為該柵格在偵察區域內的地理坐標,即

(1)

式中,L1,L2分別為無人機雷達偵察區域的長度和寬度。

2 協同搜索模型

根據典型無人機區域偵察的場景態勢,無人機機動性能、機載雷達探測屬性、區域重復探測率等均會對目標的探測概率和無人機航路的生成產生影響,進而影響最終的搜索效能。因此,本文以搜索概率為評價指標,建立無人機運動模型、狀態更新模型和搜索效益模型進行分析。

2.1 無人機運動模型

為了簡化分析,假設無人機都在同一高度上以固定的巡航速度飛行,通過調整航向角來改變自身航跡。將無人機運動過程進行離散化處理[9],并規定無人機任意時刻的航向為當前位置相鄰8個航向中的一個,即無人機的航向決策集為H={0,1,2,3,4,5,6,7}。由于轉彎角度的限制,并考慮到小轉彎角度的偏航會節省無人機的能耗,無人機在下一時刻內只有3個可能航向,規定控制參量u∈{-1,0,1},-1,0,1分別表示在原航向基礎上向左偏轉45°、不偏轉、向右偏轉45°,航向變換與當前航向關系如圖2所示。

圖2 無人機航向變換示意圖

無人機受控制參量作用,航向狀態變化算式為

(2)

式中:hk為第k個狀態更新周期的無人機航向狀態;uk為第k個狀態更新周期的控制參量。

2.2 狀態更新周期模型

考慮到無人機實際航向的多樣性以及掃描成像原理要求,定義狀態更新周期,每經歷一個狀態更新周期無人機航向會進行一次調整。為使無人機沿任意航向均能在該周期內掃描覆蓋整個柵格單位,當飛行距離包絡單位柵格最寬處時可滿足要求。狀態更新周期算式為

(3)

式中:v為無人機巡航速度;t0為無人機機載雷達成像周期。

由幾何關系分析可得,柵格中心點與無人機在第k個狀態更新周期開始時的投影點(xk,yk)間距離的算式為

(4)

由于柵格熱度值代表目標活動概率,因此將柵格中心坐標視為目標在該柵格中的坐標,即目標與無人機投影坐標的距離等價于柵格中心與無人機投影坐標的距離。

2.3 搜索效益模型

多無人機協同搜索的目的是在約束條件下盡可能大地提高搜索概率,搜索概率是無人機利用機載ISAR雷達沿航路對偵察區域成像檢測得到的,無人機離目標越近,拍攝次數越多,則發現目標的概率越大。

定義從無人機的ISAR影像中發現目標的概率為

(5)

式中:d為無人機投影坐標與目標的距離;R為無人機的最大探測距離;α為無人機機載雷達的檢測指數。

偵察過程中,多架無人機會存在對某一偵察區域多次成像的情況,假設無人機對偵察區域總計成像N次,成像距離分別是d1,d2,…,dN,其中只要有1幅ISAR圖像檢測出目標,則表示已發現目標。此時無人機基于這N幅影像發現目標的概率為

(6)

在編號為(λ,ε)的柵格中搜索到目標的充要條件是發現目標且目標位于該柵格內,定義在柵格(λ,ε)內搜索到目標的概率為

(7)

進一步可得到偵察區域內多架無人機協同搜索概率為

(8)

最終的搜索效益模型為

arg maxP

(9)

式中,Tlimit為無人機續航時間,約束條件分別表示無人機偵察搜索時間不能超過其續航時間以及無人機不能飛離偵察區域。

3 改進自適應遺傳算法

遺傳算法(Genetic Algorithm,GA)是根據生物種群優勝劣汰、適者生存的進化特點,模擬出的隨機化搜索算法[10],交叉和變異操作是遺傳算法中群體進化的主要操作。

自適應遺傳算法(Adaptive GA,AGA)能夠自發地根據適應度的變化對交叉概率和變異概率做出相應調整。即隨著進化的進行,交叉和變異概率會隨著種群適應度的增大而減小,以避免破壞當前種群的最優解,從而防止在進化后期出現退化現象。與傳統遺傳算法相比,其尋優精度大大提高,收斂速度明顯加快。

本文提出加入貪婪算子的貪婪變異策略,并引入策略選擇閾值sthreshold實現依據搜索概率變化對變異策略(貪婪變異與隨機變異)的動態調整,使算法兼具優秀的前期全局搜索能力和后期局部搜索能力。

3.1 編碼方式

傳統的遺傳算法編碼方式有二進制編碼、實數編碼、自然數編碼等。本文結合無人機航向與投影坐標之間的關系,采用類0-1編碼,將控制參量-1、0、1作為基因,狀態更新周期的個數k作為染色體的長度,即一條染色體是由k個控制參量組成的基因鏈。

3.2 解碼方式

定義無人機的初始航行方向h0,初始投影坐標(x0,y0),每經過1個控制參量無人機航向變換1次,在此過程中無人機沿初始方向航行距離為T×v,到達下一個投影坐標(x1,y1),反復進行k次,共計得到k+1個無人機投影坐標。由此完成了控制參量-航行方向-投影坐標之間的轉換,即由基因型到表現型的轉換,如圖3所示。

圖3 編碼及解碼示意圖

3.3 適應度計算

將多架無人機協同搜索概率作為種群適應度,搜索概率越大,表示種群優化結果越好,由前文知適應度函數為

(10)

對于不滿足航行時間與偵察區域限制的個體,令其適應度為0,以滿足搜索效益模型中的約束條件。

3.4 自適應過程

根據適應度和進化代數調節交叉概率和變異概率[11]分別表示為

(11)

(12)

式中:fmax為種群最大的適應度值;favg為當代種群平均適應度值;f為交叉雙方中較大的適應度值;f′為發生變異個體的適應度值。k1、k2、k3、k4為常數,且滿足k1

3.5 交叉操作

交叉是選中種群內兩個個體作為父本,依據交叉概率pc判斷是否發生染色體的部分交換從而產生新個體的過程。常見的交叉操作有單點交叉、多點交叉、均勻交叉[12]等。本文采用多點交叉,在交叉的染色體中隨機設置多個交叉點,在交叉點處將兩個父代基因進行交換并重新組合形成兩個新的基因鏈。

3.6 基于貪婪算法改進的變異操作

變異是選中種群內某一個體作為父本,依據變異概率pm判斷是否發生染色體上的某個或某些基因的突變從而產生新個體的過程。常見的變異操作有邊界變異、基本位變異、非均勻變異等。其中,基本位變異是指在染色體基因鏈上隨機指定的某一位或某幾位基因做變異運算。本文采用基本位變異,并加入貪婪算法進行改進,同時依據類0-1編碼特點,制定出貪婪變異策略與隨機變異策略,如圖4所示。

圖4 變異策略示意圖

引入變異概率閾值pm,threshold與策略選擇閾值sthreshold,改進后的變異操作如圖5所示。

圖5 基于貪婪算法改進的變異操作

圖5中,s1、s2、pm,threshold為常數且s2

由此,實現了以變異概率為橋梁,由協同搜索概率間接控制算法變異策略的效果,使算法能夠依據協同搜索概率實時調整自身的全局搜索與局部搜索能力。

4 仿真驗證

4.1 參數設置

本文仿真設置偵察區域大小為500 km×500 km,無人機種類為U1、U2型。出發地A配備U1型無人機,出發地B配備U2型無人機,無人機與機載雷達相關性能參數如表1所示。

表1 無人機與機載雷達性能參數

為檢驗本文所提算法的普適性,以出發地坐標和無人機數量為變量設置3種情形并進行仿真驗證。不同情形下參數設置如表2所示。

表2 不同情形下的參數設置

分別采用文獻[5]算法、文獻[6]算法和本文改進遺傳算法對模型進行求解。其中,模擬退火初始溫度為100,退火參數為0.99,馬爾可夫鏈長度為100,溫度下限為0.001;遺傳算法初始種群大小為800,迭代次數為150,本文算法選擇策略為輪盤賭。

對于適應度高于種群平均適應度的個體,應賦以較低的交叉概率k1和變異概率k3以確保其能存優,本文中k1、k3分別取0.7、0.15;對于適應度低于種群平均適應度的個體,應以較高的交叉概率k2和變異概率k4誘導其發生交叉和變異,從而盡可能得到較優后代,本文中k2、k4分別取0.8、0.25。

策略選擇參量s1、s2分別取0.7、0.5,以滿足算法后期當種群自適應變異概率較小時,策略選擇閾值sthreshold=s1較大,誘導算法以較大概率選擇貪婪變異策略;反之,當種群自適應變異概率較大時,策略選擇閾值sthreshold=s2較小,誘導算法以較大概率選擇隨機變異策略。

4.2 仿真結果

以情形2為例,多無人機搜索航跡如圖6所示,其中,4條折線代表4架無人機的搜索路徑,節點表示無人機在該點處航向發生變化。

圖6 多無人機搜索航跡圖

由圖6可得,本文算法求解的航跡基本覆蓋了熱力圖全局,同時也對中部高熱值區域進行了多輪重復搜索;文獻[5]算法雖然具有較優的局部搜索能力,但存在部分高熱值區域未探測的情況,全局搜索能力欠佳;文獻[6]算法具備較強的全局搜索能力,但對于部分高熱值區域的重復搜索能力不及本文算法。

協同搜索概率迭代圖見圖7。

圖7 協同搜索概率迭代圖

采用本文算法時,多無人機對目標的協同搜索概率為85.1%,相較文獻[5]算法和文獻[6]算法的最終協同搜索概率78.7%和79.8%,分別提高了6.4個百分點和5.3個百分點。文獻[6]算法雖然加速了算法收斂速率,但由于其改進選擇操作中對優秀個體的復制行為以及改進變異操作所具備的特點,種群多樣性不如本文算法,后期難以具備較優的局部搜索能力。

為避免一次實驗帶來的偶然性,針對3種情形采用3種算法分別進行20輪仿真實驗,每種情形取協同搜索概率的平均值作為仿真結果,如表3所示。

表3 協同搜索概率值仿真對比

由表3可知,對于在已知目標活動先驗信息情況下的多機協同搜索問題,本文所提出的改進遺傳算法在3種算法中表現最優,所得的協同搜索概率值最大,具有更強的搜索能力。

5 結論

針對多無人機搜索路徑規劃問題,提出了一種基于貪婪算法改進的自適應遺傳算法。引入帶貪婪算子的貪婪變異策略,通過設置策略選擇閾值實現依據搜索概率對變異策略的動態調整,使算法具備較優的前期全局搜索能力和后期局部搜索能力。仿真結果表明,相較文獻[5]算法和文獻[6]算法,本文所提算法具備更強的搜索能力。