雷 川 ,趙成萍 ,寧 芊
(1.四川大學(xué)電子信息學(xué)院,成都 610065;2.中國電子科技集團(tuán)公司第二十九研究所,成都 610036;3.電子信息控制重點(diǎn)實(shí)驗(yàn)室,成都 610065)
無人駕駛飛機(jī)(UAV)近年來在國內(nèi)得到了深入研究和較快發(fā)展,在各個領(lǐng)域的用途不斷擴(kuò)展。路徑規(guī)劃和優(yōu)化則是無人機(jī)領(lǐng)域中一個很重要的課題,要求無人機(jī)能夠基于任務(wù)、環(huán)境和無人機(jī)物理性能等因素自動地規(guī)劃出一條由起點(diǎn)至終點(diǎn)的最優(yōu)路徑。為了降低求解復(fù)雜度,不少學(xué)者提出了基于種群的算法以求解路徑規(guī)劃問題,包括遺傳算法(GA)、粒子群算法(PSO)[1],蟻群算法[2],人工蜂群算法(ABC),差分進(jìn)化算法等。
差分進(jìn)化算法(DE)作為遺傳算法最早于1995年由K.Price和R.Storn提出,用于求解切比雪夫多項(xiàng)式,具有收斂快,全局尋優(yōu)能力強(qiáng)、待定參數(shù)較少的特點(diǎn)[3]。在過去幾年中,不少基于DE的約束問題尋優(yōu)方法被提出,這些DE算法采取了各種約束處理策略,可以被分為如下類別:基于懲罰函數(shù);基于求解方案可行性;明確地區(qū)分可行方案和不可行方案;混合法。如今,差分進(jìn)化算法(DE)已經(jīng)被成功地應(yīng)用于諸多搜索領(lǐng)域。盡管DE算法本身簡練,但其在眾多種類問題中卻展現(xiàn)了出色的求解性能,諸如單峰、多峰、可分、不可分問題等,并且出現(xiàn)了一系列針對無約束、約束最優(yōu)問題的DE算法優(yōu)化版本。
無數(shù)學(xué)者提出過許多求解無人機(jī)路徑規(guī)劃問題的算法,諸如,基于柵格的數(shù)學(xué)規(guī)劃方法,A*搜索算法[4]和二階規(guī)劃方法[5];基于維諾圖[6](Voronoi diagram)的搜索方法;在啟發(fā)式搜索方法中,也有蟻群算法[7]、狼群算法等應(yīng)用于航路規(guī)劃。對于差分進(jìn)化算法在此方面的應(yīng)用,Brintaki等人提出,在靜態(tài)的沿海環(huán)境中,采取DE算法設(shè)計多無人機(jī)協(xié)同航行的二維在線路徑規(guī)劃器[8]。Yangguang Fu等人提出基于混合DE和量子行為粒子群優(yōu)化方法的海上無人機(jī)路徑規(guī)劃[9]。以上都取得了較好的實(shí)驗(yàn)結(jié)果。本文將提出將一種采取混合變異策略的DE算法用于在陸上作戰(zhàn)環(huán)境中無人機(jī)的路徑規(guī)劃。
在本文提到的無人機(jī)全局航路規(guī)劃問題中,假設(shè)其飛行場景固定,地形環(huán)境參數(shù)已知,所有雷達(dá)、武器參數(shù)部分已知。無人機(jī)的任務(wù)是在保證安全飛行的前提下盡可能多的歷經(jīng)任務(wù)點(diǎn)和盡可能少的飛行耗時。在場景中建立三維坐標(biāo)系S-OXYZ,起點(diǎn),終點(diǎn),實(shí)時路徑規(guī)劃就是在S和T之間形成一條滿足目標(biāo)函數(shù)的路徑。無人機(jī)路徑由N個介于S和T之間的離散路徑點(diǎn)組成,即,若采用貝塞爾曲線可使路徑曲線平滑。
實(shí)時在線單步搜索的空間如圖1,B為當(dāng)前路徑點(diǎn),A為上一個路徑點(diǎn),C為隨機(jī)初始化種群的一個個體(路徑點(diǎn)),θ為偏轉(zhuǎn)角,θmax為最大偏轉(zhuǎn)角,為搜索范圍最大長度,搜索空間限定在一個底面為半球的錐體中,從而滿足偏轉(zhuǎn)角約束。
圖1 搜索空間劃分示意圖
為簡化問題,單步搜索空間界定為以當(dāng)前位置和上一位置的方向向量為基準(zhǔn)的單個立方空間,逆時針旋轉(zhuǎn)坐標(biāo)系S-OXYZ,使得重合,且方向相同;旋轉(zhuǎn)后的坐標(biāo)系為旋轉(zhuǎn)角為θ,旋轉(zhuǎn)方程為:
對約束條件的描述就是構(gòu)建環(huán)境模型的過程,對于種群的個體需要驗(yàn)證是否滿足空間約束條件,由于路徑片段由選取的兩個路徑點(diǎn)連接的線段組成,為了使得結(jié)果更合理,需要將該線段離散成等距離的nu個點(diǎn),如圖2,以nu個點(diǎn)的評估結(jié)果作為線段的評估結(jié)果,任何一點(diǎn)不滿足任何一種約束條件,則該路徑片段被淘汰,即淘汰種群中對應(yīng)個體。
圖2 定量計算方法
空間約束求解式為式(3),組成空間約束的4個部分的數(shù)值求解方法為,若個體k滿足約束條件,則值為0,否則賦補(bǔ)償值,補(bǔ)償值的數(shù)值極大。因此,如果C(k)≥0個體k被淘汰。
其中,ω為權(quán)值,體現(xiàn)了不同部分相應(yīng)的權(quán)重;nu為離散點(diǎn)個數(shù),如圖2所示;R表示與參考路徑的距離;S表示航路的生存代價;L表示對任務(wù)完成度的評估,即與任務(wù)點(diǎn)的距離;J(k)為個體k的適應(yīng)度值,值越小意味著個體的適應(yīng)度越好,個體越優(yōu)。
2.2.1 生存代價
基于馬爾科夫鏈構(gòu)建無人機(jī)生存模型,作為評估其在武器、雷達(dá)區(qū)域中生存代價的方法。由轉(zhuǎn)移概率構(gòu)建轉(zhuǎn)移強(qiáng)度矩陣后,轉(zhuǎn)移概率的計算就是解微分方程,使用龍格-庫塔(Runge-Kutta)和基于歸一化方法的數(shù)值求解方法就是一種解法。本文用于構(gòu)建無人機(jī)生存模型的狀態(tài)僅有未被敵方雷達(dá)偵測、被雷達(dá)偵測、未被武器鎖定、被武器鎖定、被擊落5種狀態(tài),因?yàn)闋顟B(tài)個數(shù)有限,還可以使用求解。
pm為當(dāng)前狀態(tài)概率;pnm為狀態(tài)n到m的狀態(tài)轉(zhuǎn)移概率,cnm為單位代價。
其中,Q為狀態(tài)轉(zhuǎn)移矩陣;t為路徑運(yùn)行時間。其中,轉(zhuǎn)移強(qiáng)度隨著平臺與雷達(dá)(武器)中心距離的減小而增加,直到最大轉(zhuǎn)移強(qiáng)度(最大轉(zhuǎn)移強(qiáng)度數(shù)值根據(jù)經(jīng)驗(yàn)給出),具體計算公式如下:
其中,d為平臺距離雷達(dá)(武器)中心坐標(biāo)距離;r為雷達(dá)(武器)輻射半徑;i為相應(yīng)的最大轉(zhuǎn)移強(qiáng)度值。
2.2.2 參考路徑距離
路徑片段Lk到對應(yīng)參考路徑RRF的路徑片段的距離:
2.2.3 任務(wù)完成度
如果未經(jīng)歷任務(wù)點(diǎn),以局部搜索的個體離散的nu個點(diǎn)與任務(wù)點(diǎn)中心的距離的最小值lenmin作為任務(wù)完成度的度量,當(dāng)lenmin小于任務(wù)有效范圍時,任務(wù)完成;仍有待完成任務(wù)時:
任務(wù)全部完成或被舍棄時,該任務(wù)點(diǎn)不再參與評估。
DE算法是基于種群的隨機(jī)平行直接搜索方法,最初用于無約束問題,包括變異、交叉和選擇 3種操作步驟[3]。假設(shè)目標(biāo)函數(shù)最小值為,搜索空間界定于最小臨界值和最大臨界值之間,D表示問題的維度。在計算過程中,每個個體表示為,其中,表示種群個體數(shù);表示當(dāng)前進(jìn)化代數(shù),Gmax為最大迭代次數(shù)。
在第t=0代,采取最優(yōu)解搜索空間中的隨機(jī)分布數(shù)作為初始化的種群個體:
其中,rj滿足為區(qū)間[0,1]的均勻分布。
為了使得算法具有隨機(jī)性的本質(zhì),提高種群多樣性和個體遍歷性,因而采用混沌初始化產(chǎn)生更接近自然界隨機(jī)數(shù)特性的數(shù)值代替rj。Logistic方程是典型的混沌系統(tǒng)[10-11],方程如下:
1)DE/rand/2
2)DE/best/1
3)DE/best/2
4)DE/current-to-best/2
5)DE/rand-to-best/2
6)DE/current-to-rand/2
其中,xtbest是當(dāng)前種群中適應(yīng)度值最小的個體。為了避免單一策略帶來的不利影響,可以建立由多種策略組成的策略池,由個體選取變異策略[11-12]。
為了保持種群的多樣性,同一維度時,對個體xti與vti進(jìn)行交叉操作:
其中,rj為 [0,1]的隨機(jī)數(shù),CR為交叉因子,CR∈[0,1],rn 為從整數(shù)集合中隨機(jī)選取的數(shù)。
采取貪婪策略搜索結(jié)果,將變異個體與交叉后生成的實(shí)驗(yàn)個體競爭,選出適應(yīng)度值最佳的個體作為子代個體。
混合策略(mixed strategy)差分進(jìn)化算法(MSDE)的思想是通過劃分種群采取不同進(jìn)化策略來均衡全局搜索能力和收斂速度之間的矛盾,使得算法在合理計算復(fù)雜度下有較高的全局搜索效率。因?yàn)椴煌呗缘姆峙?,也為進(jìn)一步提升計算性能的并行計算提供了實(shí)現(xiàn)思路。
步驟1:按照混沌原理初始化種群,使得個體分布更接近與自然隨機(jī)。
步驟2:按照計算能力和實(shí)驗(yàn)需求,將初始化所得種群按照個體適應(yīng)度值大小,將種群分為3個等級的子種群。
步驟3:對于3個子種群,分別進(jìn)行相同迭代次數(shù)的變異、交叉、選擇操作。
圖3 MSDE算法流程圖
步驟4:將步驟3產(chǎn)生的新的子種群合并,并判斷是否滿足終止條件,若不滿足,則繼續(xù)進(jìn)行步驟2操作;若滿足,進(jìn)入步驟5。
步驟5:在步驟4中的種群中,選出適應(yīng)度值最佳的個體,作為搜尋結(jié)果。
算法流程如圖3所示,將初始化的種群個體按照適應(yīng)度值分為優(yōu)、良、差3個子種群,然后采取3種不同的變異和交叉策略進(jìn)行種群更新。子種群規(guī)模由評定因子 Δ(0<Δ<1)決定,當(dāng) Δ≤0.45時,劣等子種群個體數(shù)目應(yīng)該大一些,Δ≥0.7時,優(yōu)等子種群個體數(shù)目應(yīng)該大一些。評定因子求解式為:
其中,J為種群所有個體的適應(yīng)度值的集合。
當(dāng)問題越復(fù)雜,不恰當(dāng)?shù)牟呗耘c參數(shù)選取,會導(dǎo)致早熟收斂。早熟出現(xiàn)的根本原因是隨著進(jìn)化代數(shù)增加,種群多樣性下降,從而導(dǎo)致早熟[14]。Rand策略能夠體現(xiàn)出較強(qiáng)的全局尋優(yōu)性能,best策略局部搜索能力強(qiáng),能夠加快算法收斂速度,兩者結(jié)合無論單峰問題還是多峰問題都能夠相互彌補(bǔ)。對于適應(yīng)度值較好的子種群,應(yīng)該增強(qiáng)局部搜索能力,反之,應(yīng)該增加全局搜索能力[12-15]。
種群規(guī)模NP的選取,理論上,對于可分、單模態(tài)函數(shù)的求解只需要小規(guī)模種群以提升收斂速率,此時,NP取值參考式為NP=5D×CR,其中,D為待求解問題的維度。對于多模態(tài)問題,初始種群規(guī)模NP=10D是DE算法能尋求得全局最優(yōu)解的參考個體數(shù)。然而,實(shí)際應(yīng)用中還需要針對采取的變異策略為依據(jù),保證NP數(shù)值大于臨界值[13]。
交叉因子CR控制了在當(dāng)前種群中發(fā)生變異父代的個體與數(shù)量,CR較大時,能夠加快收斂速度,也有利于單峰問題的局部尋優(yōu);反之,當(dāng)CR較小時,有利于保持種群的多樣性和全局尋優(yōu)能力,有利于多峰問題的求解[14]。理論上,對于一般問題,CR在區(qū)間[0.3,0.9]取值。當(dāng)CR=1.0時,試解的結(jié)果數(shù)會急劇減少從而導(dǎo)致交叉過程停滯,因此,實(shí)際中用CR=0.9或者CR=0.99代替。
對于放縮因子F,其值通常介于[0.5,1],且F必須大于0。實(shí)際中,當(dāng)F>1時,由于攝動會超過兩個體間的距離,導(dǎo)致收斂速度急劇減少,從而難以匯聚。Zaharie提出,如果F能變成高斯隨機(jī)變量,DE算法能夠收斂到全局最優(yōu)[13]。當(dāng)F=1.0時,也會導(dǎo)致停滯。
在MATLAB 8.4環(huán)境下對算法MSDE進(jìn)行實(shí)驗(yàn),選用變異策略DE/rand/1、DE/best/1和DE/best/2來構(gòu)建策略池,用于3個子種群,并與單獨(dú)對整個種群使用DE/best/1做對比。實(shí)驗(yàn)參數(shù)設(shè)置如下:種群規(guī)模NP-60,對于3種策略,其子種群的放縮因子分別為 F- (0.3,0.47,0.78),交叉概率 CR-(0.45,0.64,0.9),迭代次數(shù)Gmax=8并且設(shè)置最大轉(zhuǎn)移強(qiáng)度、狀態(tài)代價與轉(zhuǎn)移代價等其他參數(shù)。
圖中藍(lán)色球體為雷達(dá)輻射區(qū)域;紅色球體為武器有效攻擊區(qū)域;綠色球體為任務(wù)區(qū)域,紅色路徑為搜索結(jié)果。
實(shí)驗(yàn)結(jié)果如圖7~圖9所示。
在實(shí)驗(yàn)環(huán)境、選取參數(shù)均相同的情況下,由轉(zhuǎn)移強(qiáng)度下頁圖6和圖9并結(jié)合三維效果圖5、圖8可得,采取混合變異策略的DE算法比僅使用單一策略的DE算法搜索出的路徑生存代價更低,且路徑更加平穩(wěn)。采取混合變異策略的DE算法所得路徑的平穩(wěn)性也由表1數(shù)據(jù)可再次證明。原因在于,混合策略使得全局和局部搜索能力均得到加強(qiáng),使得最終得到的路徑更加趨近于全局最優(yōu)。
圖4 X-Y平面上搜索結(jié)果圖
圖5 搜索結(jié)果三維效果圖
圖6 轉(zhuǎn)移強(qiáng)度圖
表1 性能指標(biāo)
圖7 X-Y平面上搜索結(jié)果圖
圖8 搜索結(jié)果三維效果圖
圖9 轉(zhuǎn)移強(qiáng)度圖
本文采取混合變異策略的DE算法用于求解實(shí)戰(zhàn)環(huán)境中無人機(jī)航路規(guī)劃問題,初始化種群注重模擬自然隨機(jī)數(shù),以及結(jié)合馬爾科夫鏈注重于對真實(shí)作戰(zhàn)環(huán)境相關(guān)因素的簡單模擬??傮w而言,混合變異策略的DE算法,在三維實(shí)戰(zhàn)環(huán)境的無人機(jī)航路規(guī)劃問題中,性能表現(xiàn)優(yōu)于單一策略,進(jìn)一步開發(fā)出差分進(jìn)化算法在實(shí)際應(yīng)用中的全局搜索能力。
然而,算法實(shí)驗(yàn)尚存在不足,即未對路徑做進(jìn)一步平滑處理;對基于馬爾科夫鏈的生存代價模型進(jìn)行了大幅簡化,初始值設(shè)置等還待進(jìn)一步研究;對于環(huán)境建模,沒考慮環(huán)境隨時可變的情況,如天氣變化。將差分進(jìn)化算法用于問題求解,若能根據(jù)積累龐大的實(shí)驗(yàn)數(shù)據(jù),結(jié)合大數(shù)據(jù)、機(jī)器學(xué)習(xí),選擇出最佳放縮因子、交叉概率等參數(shù),將產(chǎn)生更好的實(shí)驗(yàn)結(jié)果與應(yīng)用價值。