基于混合變異策略差分進(jìn)化算法的無人機(jī)航路規(guī)劃*

雷 川 ，趙成萍 ，寧 芊

（1.四川大學(xué)電子信息學(xué)院，成都 610065；2.中國電子科技集團(tuán)公司第二十九研究所，成都 610036；3.電子信息控制重點實驗室，成都 610065）

0 引言

無人駕駛飛機(jī)（UAV）近年來在國內(nèi)得到了深入研究和較快發(fā)展，在各個領(lǐng)域的用途不斷擴(kuò)展。路徑規(guī)劃和優(yōu)化則是無人機(jī)領(lǐng)域中一個很重要的課題，要求無人機(jī)能夠基于任務(wù)、環(huán)境和無人機(jī)物理性能等因素自動地規(guī)劃出一條由起點至終點的最優(yōu)路徑。為了降低求解復(fù)雜度，不少學(xué)者提出了基于種群的算法以求解路徑規(guī)劃問題，包括遺傳算法（GA）、粒子群算法（PSO）［1］，蟻群算法［2］，人工蜂群算法（ABC），差分進(jìn)化算法等。

差分進(jìn)化算法（DE）作為遺傳算法最早于1995年由K.Price和R.Storn提出，用于求解切比雪夫多項式，具有收斂快，全局尋優(yōu)能力強(qiáng)、待定參數(shù)較少的特點［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］。以上都取得了較好的實驗結(jié)果。本文將提出將一種采取混合變異策略的DE算法用于在陸上作戰(zhàn)環(huán)境中無人機(jī)的路徑規(guī)劃。

1 問題描述

在本文提到的無人機(jī)全局航路規(guī)劃問題中，假設(shè)其飛行場景固定，地形環(huán)境參數(shù)已知，所有雷達(dá)、武器參數(shù)部分已知。無人機(jī)的任務(wù)是在保證安全飛行的前提下盡可能多的歷經(jīng)任務(wù)點和盡可能少的飛行耗時。在場景中建立三維坐標(biāo)系S-OXYZ，起點，終點，實時路徑規(guī)劃就是在S和T之間形成一條滿足目標(biāo)函數(shù)的路徑。無人機(jī)路徑由N個介于S和T之間的離散路徑點組成，即，若采用貝塞爾曲線可使路徑曲線平滑。

實時在線單步搜索的空間如圖1，B為當(dāng)前路徑點，A為上一個路徑點，C為隨機(jī)初始化種群的一個個體（路徑點），θ為偏轉(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)方程為：

2 約束條件和適應(yīng)度函數(shù)

對約束條件的描述就是構(gòu)建環(huán)境模型的過程，對于種群的個體需要驗證是否滿足空間約束條件，由于路徑片段由選取的兩個路徑點連接的線段組成，為了使得結(jié)果更合理，需要將該線段離散成等距離的nu個點，如圖2，以nu個點的評估結(jié)果作為線段的評估結(jié)果，任何一點不滿足任何一種約束條件，則該路徑片段被淘汰，即淘汰種群中對應(yīng)個體。

2.1 空間約束

圖2 定量計算方法

空間約束求解式為式（3），組成空間約束的4個部分的數(shù)值求解方法為，若個體k滿足約束條件，則值為0，否則賦補(bǔ)償值，補(bǔ)償值的數(shù)值極大。因此，如果C（k）≥0個體k被淘汰。

2.2 適應(yīng)度函數(shù)

其中，ω為權(quán)值，體現(xiàn)了不同部分相應(yīng)的權(quán)重；nu為離散點個數(shù)，如圖2所示；R表示與參考路徑的距離；S表示航路的生存代價；L表示對任務(wù)完成度的評估，即與任務(wù)點的距離；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)，因為狀態(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)驗給出），具體計算公式如下：

其中，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ù)點，以局部搜索的個體離散的nu個點與任務(wù)點中心的距離的最小值lenmin作為任務(wù)完成度的度量，當(dāng)lenmin小于任務(wù)有效范圍時，任務(wù)完成；仍有待完成任務(wù)時：

任務(wù)全部完成或被舍棄時，該任務(wù)點不再參與評估。

3 標(biāo)準(zhǔn)差分進(jì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］，方程如下：

3.1 變異操作（Mutation operator）

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］。

3.2 交叉操作（Crossover operator）

為了保持種群的多樣性，同一維度時，對個體xti與vti進(jìn)行交叉操作：

其中，rj為 [0，1]的隨機(jī)數(shù)，CR為交叉因子，CR∈[0，1]，rn 為從整數(shù)集合中隨機(jī)選取的數(shù)。

3.3 選擇操作（Selection operator）

采取貪婪策略搜索結(jié)果，將變異個體與交叉后生成的實驗個體競爭，選出適應(yīng)度值最佳的個體作為子代個體。

4 混合策略差分進(jìn)化算法

4.1 算法原理

混合策略（mixed strategy）差分進(jìn)化算法（MSDE）的思想是通過劃分種群采取不同進(jìn)化策略來均衡全局搜索能力和收斂速度之間的矛盾，使得算法在合理計算復(fù)雜度下有較高的全局搜索效率。因為不同策略的分配，也為進(jìn)一步提升計算性能的并行計算提供了實現(xiàn)思路。

4.2 混合策略MSDE算法流程

步驟1：按照混沌原理初始化種群，使得個體分布更接近與自然隨機(jī)。

步驟2：按照計算能力和實驗需求，將初始化所得種群按照個體適應(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)度值的集合。

4.3 策略池構(gòu)建與參數(shù)選擇

當(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ù)。然而，實際應(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)致交叉過程停滯，因此，實際中用CR=0.9或者CR=0.99代替。

對于放縮因子F，其值通常介于[0.5，1]，且F必須大于0。實際中，當(dāng)F＞1時，由于攝動會超過兩個體間的距離，導(dǎo)致收斂速度急劇減少，從而難以匯聚。Zaharie提出，如果F能變成高斯隨機(jī)變量，DE算法能夠收斂到全局最優(yōu)［13］。當(dāng)F=1.0時，也會導(dǎo)致停滯。

5 數(shù)值實驗

在MATLAB 8.4環(huán)境下對算法MSDE進(jìn)行實驗，選用變異策略DE/rand/1、DE/best/1和DE/best/2來構(gòu)建策略池，用于3個子種群，并與單獨對整個種群使用DE/best/1做對比。實驗參數(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ù)。

5.1 采用單一策略差分進(jìn)化算法實驗結(jié)果

圖中藍(lán)色球體為雷達(dá)輻射區(qū)域；紅色球體為武器有效攻擊區(qū)域；綠色球體為任務(wù)區(qū)域，紅色路徑為搜索結(jié)果。

5.2 采用混合策略的差分進(jìn)化算法實驗結(jié)果

實驗結(jié)果如圖7～圖9所示。

5.3 實驗結(jié)果分析

在實驗環(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)

6 結(jié)論

圖7 X-Y平面上搜索結(jié)果圖

圖8 搜索結(jié)果三維效果圖

圖9 轉(zhuǎn)移強(qiáng)度圖

本文采取混合變異策略的DE算法用于求解實戰(zhàn)環(huán)境中無人機(jī)航路規(guī)劃問題，初始化種群注重模擬自然隨機(jī)數(shù)，以及結(jié)合馬爾科夫鏈注重于對真實作戰(zhàn)環(huán)境相關(guān)因素的簡單模擬。總體而言，混合變異策略的DE算法，在三維實戰(zhàn)環(huán)境的無人機(jī)航路規(guī)劃問題中，性能表現(xiàn)優(yōu)于單一策略，進(jìn)一步開發(fā)出差分進(jìn)化算法在實際應(yīng)用中的全局搜索能力。

然而，算法實驗尚存在不足，即未對路徑做進(jìn)一步平滑處理；對基于馬爾科夫鏈的生存代價模型進(jìn)行了大幅簡化，初始值設(shè)置等還待進(jìn)一步研究；對于環(huán)境建模，沒考慮環(huán)境隨時可變的情況，如天氣變化。將差分進(jìn)化算法用于問題求解，若能根據(jù)積累龐大的實驗數(shù)據(jù)，結(jié)合大數(shù)據(jù)、機(jī)器學(xué)習(xí)，選擇出最佳放縮因子、交叉概率等參數(shù)，將產(chǎn)生更好的實驗結(jié)果與應(yīng)用價值。