多策略改進(jìn)蜉蝣算法的無人機(jī)航跡規(guī)劃

席萬強(qiáng), 常保帥, 林思偉, 林俊志, 李 鵬,

(1.無錫學(xué)院,江蘇 無錫 214000; 2.南京信息工程大學(xué),南京 210000)

0 引言

近年來無人機(jī)行業(yè)發(fā)展迅速,其因代價低、操作方便等特點廣泛應(yīng)用于軍事及民用領(lǐng)域。但無人機(jī)在低空飛行的安全性方面仍面臨著巨大的挑戰(zhàn)[1],而航跡規(guī)劃是無人機(jī)能夠平穩(wěn)飛行、安全完成作業(yè)的基本保障,現(xiàn)已成為無人機(jī)研究的熱門話題。

無人機(jī)航跡規(guī)劃是指明確起點和終點,規(guī)劃出一條無碰撞的、代價最優(yōu)的無人機(jī)飛行路徑。無人機(jī)航跡規(guī)劃技術(shù)分為采樣法、數(shù)學(xué)模型法、啟發(fā)式函數(shù)法、深度學(xué)習(xí)法[2]。文獻(xiàn)[3]提出了一種A*算法和DWA結(jié)合的方法,將弧形障礙物和凹形障礙物分別進(jìn)行網(wǎng)格化預(yù)處理和凸形預(yù)處理后,改進(jìn)A*算法的啟發(fā)式函數(shù),選取全局路徑的關(guān)鍵點作為局部路徑規(guī)劃的子目標(biāo)點,該算法縮短了航跡長度,提高了路徑平滑度和安全性;文獻(xiàn)[4]將調(diào)控力和檢測因子引入人工勢場法,解決了陷于局部最優(yōu)和目標(biāo)不可達(dá)的問題。上述兩種方案在解決航跡規(guī)劃時,計算復(fù)雜性高、收斂速度慢并且難以處理高維問題[5],而元啟發(fā)算法可以產(chǎn)生更高質(zhì)量的解,且易于實現(xiàn)?；趩l(fā)式搜索的路徑規(guī)劃包括粒子群算法、人工蜂群算法和布谷鳥算法等智能算法,是模擬自然界各種現(xiàn)象并求解最優(yōu)化問題的算法。相較于其他策略的算法,群智能算法收斂穩(wěn)定,能夠找到滿足要求的最優(yōu)路徑。文獻(xiàn)[6]提出了一種新的球形向量粒子群優(yōu)化算法,將搜索空間從笛卡爾空間切換到配置空間,在配置空間中獲得高質(zhì)量的解,提高了算法的效率和性能;文獻(xiàn)[7]利用估計分布法提出了一種具有緊致格式的布谷鳥算法,并在此基礎(chǔ)上采取并行通信策略,能有效地保存無人機(jī)的存儲空間,提高執(zhí)行效率。

蜉蝣算法(MA)[8]是基于雌性和雄性蜉蝣的飛行和交配繁殖等行為提出的一種新型智能算法,具有較強(qiáng)的局部收斂和全局開發(fā)的能力。文獻(xiàn)[9]采用指數(shù)遞減慣性權(quán)重(EDIW)策略、自適應(yīng)柯西變異和改進(jìn)的交叉算子對蜉蝣算法進(jìn)行改進(jìn),高效地搜索無人機(jī)配置空間,發(fā)現(xiàn)總代價最低的路徑。雖然上述改進(jìn)算法被證明是有效的,但是仍存在執(zhí)行效率低和解的質(zhì)量不高等問題,且無法平衡全局搜索和局部開發(fā)之間的關(guān)系。

針對上述研究不足,本文采用萊維(Lévy)飛行對蜉蝣算法進(jìn)行初始化,提高物種的多樣性,充分搜索解空間。為解決陷入局部最優(yōu)的問題,采用自適應(yīng)t分布方法,并提出一種基于Pareto原理[10]的精英保留策略,以此增加系統(tǒng)的穩(wěn)定性。最后,使用三次B樣條曲線對路徑進(jìn)行擬合,生成平滑且穩(wěn)定的軌跡。

1 數(shù)學(xué)模型建立

1.1 環(huán)境模型

使用仿生算法進(jìn)行無人機(jī)三維路徑規(guī)劃,首先要對環(huán)境和障礙物進(jìn)行建模,建立適應(yīng)度函數(shù),進(jìn)而規(guī)劃出最優(yōu)路徑;其次使用三次B樣條曲線生成平滑的路徑,在三維空間中一個蜉蝣粒子代表一條路徑。假設(shè)一條路徑包含n個航跡點,粒子的位置Xi=(xi1,xi2,…,xin)?；鶞?zhǔn)地形和障礙物地形[11]分別為

(1)

(2)

式中:Z1是平面點對應(yīng)的高程值[12];x和y為模型在平面上的點坐標(biāo);A,B,C,D,E,F,G為常系數(shù),對高程地圖中的山峰特征進(jìn)行控制;(xi,yi)和hi分別為第i座山峰中心坐標(biāo)值和山峰的高度;xsi和ysi控制第i座山峰的坡度。圖1所示為環(huán)境三維圖。

圖1 環(huán)境三維圖Fig.1 Three-dimensional map of the environment

1.2 代價函數(shù)

在航跡規(guī)劃中,路徑的長度、高度和偏轉(zhuǎn)角都是衡量路徑質(zhì)量的重要因素,代價函數(shù)與兩個相鄰航跡點之間的距離、高度和偏轉(zhuǎn)角有關(guān),其綜合代價為

F=min(D′+H+θ)

(3)

式中:F為適應(yīng)度函數(shù);D′為路徑的總長度;H為路徑的平均高度;θ為偏轉(zhuǎn)角。算式分別為

(4)

(5)

(6)

其中,pi=(xi+1-xi,yi+1-yi,zi+1-zi)。

2 蜉蝣算法

蜉蝣算法初始化隨機(jī)生成兩組蜉蝣,分別代表雌性和雄性種群。

2.1 雄性蜉蝣飛行

雄性蜉蝣會聚集在一起,根據(jù)個體和群體經(jīng)驗來調(diào)整飛行方向。第i只雄性蜉蝣在d維空間的位置和速度分別可以表示為xi=(xi1,xi2,…,xid)T,vi=(vi1,vi2,…,vid)T。其位置更新可表示為

(7)

式中,k為迭代次數(shù)。

在實際生活中,雄性蜉蝣會在水面上幾米的地方表演婚禮舞蹈。假設(shè)它們保持低速運動,則雄性蜉蝣i的速度為

(8)

(9)

gbest=min{f(pbest1),f(pbest2),…,f(pbestN)}

(10)

其中:N為群中雄性蜉蝣總數(shù)。式(8)中rp是xi和pbesti之間的笛卡爾距離;rg是xi和gbest之間的笛卡爾距離。這些距離為

(11)

最好的雄性蜉蝣會進(jìn)行獨特的婚約舞步,以不同的速度進(jìn)行上下運動。這些雄性蜉蝣的速度為

(12)

式中:d′為婚禮舞蹈系數(shù);r表示0～1的隨機(jī)值。

2.2 雌性蜉蝣飛行

與雄性蜉蝣不同,雌性蜉蝣不會成群聚集在一起,但是會向雄性蜉蝣移動。第i只雌性蜉蝣位置更新為

(13)

雌性蜉蝣飛向雄性蜉蝣繁殖后代,并根據(jù)和雄性蜉蝣的位置更新自己的飛行方向。雌性蜉蝣和雄性蜉蝣在互相吸引的過程中按照個體適應(yīng)度排名相同的原則,雌性蜉蝣的位置會隨著具有相同排名的雄性蜉蝣的位置而改變,即

(14)

式中:rmf是第i只雌性蜉蝣和第i只雄性蜉蝣之間的歐氏距離;ffl是一個隨機(jī)游走系數(shù),當(dāng)雌性蜉蝣沒有被雄性蜉蝣吸引時使用。

2.3 蜉蝣交配

根據(jù)雌性蜉蝣和雄性蜉蝣的排名,具有相同排名的雌性和雄性進(jìn)行交配繁殖,并產(chǎn)生兩個后代,后代的位置為

(15)

式中:L表示0～1范圍的隨機(jī)值;子代的最初速度設(shè)為零;mmale和ffemale分別表示雄性和雌性的位置矩陣。

2.4 婚約舞步和隨機(jī)游走

婚約舞步和隨機(jī)游走使算法進(jìn)一步地局部搜索,但是固定的系數(shù)在迭代后期可能使蜉蝣迭代到更糟糕的位置。故使舞步系數(shù)和隨機(jī)游走系數(shù)隨著迭代次數(shù)減少,更新算式為

(16)

式中,δ是隨機(jī)因子。

2.5 后代變異

為了處理過早收斂的情況,使算法搜索到空間之前從未訪問的新區(qū)域,隨機(jī)挑選子代進(jìn)行正態(tài)分布的擾動變異,即

(17)

式中:σ為正態(tài)分布的標(biāo)準(zhǔn)差;Nn(0,1)為標(biāo)準(zhǔn)正態(tài)分布。

3 改進(jìn)的蜉蝣算法(CMA)

3.1 萊維(Lévy)飛行策略

蜉蝣算法在初始化階段隨機(jī)生成蜉蝣位置,喪失了種群的多樣性,而更新機(jī)制使蜉蝣朝向最優(yōu)個體迭代發(fā)展,因此容易陷于局部最優(yōu),過早收斂。故提出一種Lévy飛行策略,對隨機(jī)初始化后的種群進(jìn)行擾動。Lévy飛行是一個經(jīng)典的隨機(jī)過程,具有大概率進(jìn)行大步長的飛行,容易跳出局部最優(yōu)[13]。Lévy飛行可以更全面地對解空間進(jìn)行搜索,故使用Lévy飛行對初始化后的位置擾動,其位置更新算式為

(18)

(19)

式中:β的范圍是1≤β≤3,本文取1.5;u～N(0,σ2)σ和v～N(0,1)服從正態(tài)分布。σ的取值為

(20)

式中,Γ(·)是標(biāo)準(zhǔn)的伽馬函數(shù)。

3.2 t分布策略

t分布又稱學(xué)生分布,含有自由參數(shù)n,當(dāng)t(n→∞)→N(0,1),當(dāng)t(n→1)→C(0,1),其中,N(0,1)為高斯分布,C(0,1)為柯西分布,即標(biāo)準(zhǔn)高斯分布和柯西分布是兩個邊界特例分布[14]。t分布變異結(jié)合了柯西變異和高斯變異的特點,隨著自由參數(shù)n的變化,算法可以進(jìn)行不同程度的變異。

在蜉蝣種群中,雄性蜉蝣成群結(jié)對地進(jìn)行游動更新,降低了整個蜉蝣種群的多樣性,使用自適應(yīng)t分布變異對雄性蜉蝣游動后的位置進(jìn)行擾動,即在式(7)的基礎(chǔ)上進(jìn)行變異改進(jìn),更新位置為

(21)

3.3 基于Pareto原理的精英保留策略

傳統(tǒng)蜉蝣算法隨機(jī)挑選子代進(jìn)行變異,雖然增強(qiáng)了算法的隨機(jī)性,但是大概率使蜉蝣后代陷入更糟的位置,導(dǎo)致算法優(yōu)化結(jié)果較差,影響收斂速度。為了增強(qiáng)后代質(zhì)量,提出一種精英保留策略,對子代的適應(yīng)度按升序進(jìn)行排名。使用優(yōu)勝劣汰法則,對代價函數(shù)較低的子代進(jìn)行變異,較高的保留,最后合并成新的子代,以保持種群的穩(wěn)定性。在進(jìn)化過程中要保證種群中解的精度和收斂效率之間的平衡[15],故提出一種基于Pareto原理(80/20法則)的精英保留策略,適應(yīng)度排名的前20%保留,后80%變異。既有效地保持了種群的活力,又減少了數(shù)據(jù)冗余,提高了算法的運行效率。減少式(17)中子代變異的隨機(jī)性。更新后的種群為

(22)

式中:m為子代種群數(shù)量;i為對子代按適應(yīng)度排名后的第i只蜉蝣。式(22)的引入使子代不再進(jìn)行隨機(jī)變異,使算法跳出局部最優(yōu),增加物種多樣性。圖2為改進(jìn)蜉蝣算法的流程圖。

圖2 改進(jìn)蜉蝣算法流程圖Fig.2 Flow chart of modified mayfly algorithm

4 仿真

本次仿真的地圖搜索范圍為100 m×100 m×100 m,使用式(1)、式(2)生成環(huán)境和障礙物模型。設(shè)置起始點為(1 m,1 m,1 m),目標(biāo)點為(100 m,100 m,80 m),山峰數(shù)取6。算法中具體參數(shù)設(shè)置如下:重力系數(shù)取0.8 N/kg,游走系數(shù)ffl取1,舞蹈系數(shù)取5,游走迭代速率取0.8,舞蹈迭代速率取0.99。

表1顯示了不同迭代次數(shù)對算法的影響,表中加粗?jǐn)?shù)值表示3種算法中的最優(yōu)值。在種群數(shù)量固定為50,迭代次數(shù)分別取100,200,500,獨立運行算法30次的情況下,列出了3種算法的平均值(Mean)、最差值(Worst)、最優(yōu)值(Optimal)以及標(biāo)準(zhǔn)差(Std)。從表1中數(shù)據(jù)可知,改進(jìn)的蜉蝣算法(CMA)在迭代100次后就能找到較好的解,而傳統(tǒng)的蜉蝣算法(MA)和粒子群算法(PSO)表現(xiàn)一般,且在后期容易陷入局部最優(yōu)。雖然MA算法在30次運行中,適應(yīng)度的最優(yōu)值最小,但是標(biāo)準(zhǔn)差不如CMA,PSO的適應(yīng)度平均值最差,在運行中容易產(chǎn)生震蕩,故CMA算法在運行中更穩(wěn)定?？傊瓹MA在收斂速度與穩(wěn)定性方面有顯著優(yōu)勢。

表1 算法性能測試比較

本文將改進(jìn)蜉蝣算法(CMA)和傳統(tǒng)蜉蝣算法(MA)放在同一復(fù)雜環(huán)境下進(jìn)行比較。圖3為航跡點n=5時3種算法在三維環(huán)境中的路徑規(guī)劃圖。由圖3可知,3種算法均能規(guī)劃出安全無碰撞的路徑,但是在路徑的長度和平滑性方面有所不同,CMA規(guī)劃的路徑比MA和PSO路徑更短、更穩(wěn)定,MA會產(chǎn)生不必要的軌跡,導(dǎo)致距離變長,造成無人機(jī)電量的浪費。雖然PSO規(guī)劃的路徑長度比MA短,但是相較于CMA路徑會產(chǎn)生冗余路徑。在飛行過程中,CMA規(guī)劃的軌跡,能在躲避障礙物的前提下勻速飛行,飛行高度逐漸上升,而MA和PSO規(guī)劃的軌跡多處產(chǎn)生震蕩,在軌跡初期飛行高度快速提升,接近終點時,降低高度,這種情況在實際應(yīng)用中不可取,容易造成安全隱患,增大油耗。

圖3 3種算法的軌跡規(guī)劃圖Fig.3 Trajectory planning diagram of three algorithms

圖4為3種算法的迭代收斂圖,可以看出:在200次的迭代中,CMA更容易跳出局部最優(yōu),規(guī)劃的路徑更穩(wěn)定且收斂速度快,前期就能找到比較優(yōu)的路徑,后期更容易找到全局最優(yōu);CMA在迭代200次后,其適應(yīng)度優(yōu)于MA和PSO,而CMA前期適應(yīng)度高,路徑多處震蕩。PSO雖然前期就能找到適應(yīng)度較好的位置,但是后期陷入局部最優(yōu)。故CMA收斂速度更快,精度更高。

圖4 3種算法的迭代收斂圖Fig.4 Iterative convergence graph of the three algorithms

綜上所述,CMA在進(jìn)行航跡規(guī)劃時,相較于MA和PSO,有收斂更加穩(wěn)定、路徑最短等優(yōu)點,所以該算法可以作為一種有效的替代手段解決無人機(jī)路徑規(guī)劃問題。

5 總結(jié)

針對傳統(tǒng)蜉蝣算法在進(jìn)行無人機(jī)三維航跡規(guī)劃中存在易陷于局部最優(yōu)、不穩(wěn)定和收斂速度慢等問題。本文提出一種基于多策略改進(jìn)蜉蝣算法的無人機(jī)航跡規(guī)劃,使用Lévy飛行、自適應(yīng)t分布和基于Pareto原理的精英保留策略對其進(jìn)行混合改進(jìn)。通過三次B樣條曲線對路徑進(jìn)行擬合,建立以路徑長度、轉(zhuǎn)彎角以及高度作為標(biāo)準(zhǔn)的代價函數(shù)來評價路徑的優(yōu)劣。為證明改進(jìn)算法的有效性,在迭代次數(shù)不同的情況下將改進(jìn)的蜉蝣算法、傳統(tǒng)的蜉蝣算法和粒子群算法進(jìn)行測試比較,并將其應(yīng)用于無人機(jī)三維航跡規(guī)劃,結(jié)果顯示,改進(jìn)的蜉蝣算法在收斂速度和精度等方面均優(yōu)于傳統(tǒng)蜉蝣算法和粒子群算法,規(guī)劃出的航跡比較穩(wěn)定且質(zhì)量較高。