應用改進差分進化算法的三維路徑規(guī)劃

張宗豪， 徐 斌， 胡 錚

(上海工程技術大學機械與汽車工程學院，上海 201000)

0 引言

路徑規(guī)劃是無人機進行任務規(guī)劃的基本問題。無人機路徑規(guī)劃是在考慮無人機周圍的地貌環(huán)境約束、自身性能約束、威脅物等條件下，為無人機規(guī)劃出一條從起點到目標點的最優(yōu)安全路徑。無人機路徑規(guī)劃算法主要分為兩類:一是傳統(tǒng)方法，如人工勢場法、A*算法、動態(tài)規(guī)劃法等；二是智能優(yōu)化算法，如蟻群算法、粒子群算法、遺傳算法、差分進化算法等[1]。差分進化(Differential Evolution,DE)算法[2]是由STORN和PRICE提出的一種機制簡單的群體智能優(yōu)化算法，核心機制是通過變異、交叉操作并在貪婪選擇策略下實現(xiàn)種群空間的迭代更新，逐步靠向最優(yōu)解，具有高效尋優(yōu)的特點。近年來，差分進化算法在路徑規(guī)劃方面得到了廣泛的應用，眾多學者對其進行了大量研究。文獻[3]引入廣義反向學習機制初始化種群，以適應度值從原種群和反向種群中綜合選取較優(yōu)個體，提高算法搜索精度和收斂速度，并且得到了更短的路徑；文獻[4]提出混入分布估計算法對種群以隨機的概率進行更新，擴大搜索范圍并且縮短路徑長度、減小威脅代價；文獻[5]提出的差分進化算法將種群分為兩部分，并為不同種群提供不同的變異策略，進行多無人機路徑規(guī)劃，成功縮減了路徑的長度；文獻[6]提出一種基于自適應變異算子的約束差分進化算法處理無人機路徑規(guī)劃問題。本文從差分策略和參數(shù)控制兩個方面對算法進行改進，并通過測試函數(shù)核驗改進算法的性能，應用于三維路徑規(guī)劃驗證改進算法的可行性。

1 改進差分進化算法

本文提出的改進算法MSCADE借鑒正弦余弦算法局部搜索的優(yōu)勢，在DE算法基礎上融入種群重心概念，基于正弦余弦算法搜索機制對變異策略進行改進，并設計新的自適應縮放因子，以增強種群多樣性、提高搜索能力；引入擾動策略到交叉策略，利用優(yōu)秀個體信息引導搜索方向，提高收斂速度。

1.1 基于正弦余弦的變異策略

差分進化算法隨著迭代進行逐步向最優(yōu)解靠近。

在算法的前期應該增強算法的全局搜索性能；在后期提高局部開采能力，加快收斂速度。DE/rand/1算法因良好的空間搜索能力得到廣泛應用，但后期局部開發(fā)能力不足。因此，本文基于改進正弦余弦算法[7]的搜索機制構建一種新的變異策略，并加入種群空間重心調節(jié)搜索方向。表達式為

(1)

(2)

其中:xcenter為每代種群空間的重心;P*為前一代最優(yōu)個體；NP為種群數(shù)量。式(1)前半部分利用正弦函數(shù)的性質可實現(xiàn)平衡全局探索和局部開發(fā)的能力，后半部分利用種群重心可以加快算法收斂速度。

1.2 引入擾動策略的交叉策略

差分進化算法一旦發(fā)生早熟現(xiàn)象，變異操作的搜索能力就會削弱。此時，基于目標個體和對應變異個體的交叉操作，不能使算法有效地跳出局部最優(yōu)解。擾動策略作為一種有效的跳出局部最優(yōu)解的方式而得到廣泛應用。本文在每一代種群中的目標個體和與之對應的加入基于t分布概率密度函數(shù)擾動的變異個體間，構建新的交叉策略，具體表述如下

(3)

式中:t分布概率密度函數(shù)tpdf(G,γ)中自變量G是當前迭代數(shù)，γ是自由度參數(shù);pt是[0,1]間的隨機數(shù)。參數(shù)γ可調整t分布概率密度函數(shù)曲線的曲率，γ越大曲線下降越快，γ越小曲線下降越平緩。這里γ取1，可保證曲線平緩下降，后期保持較大擾動值，有利于跳出局部最優(yōu)解。

在改進的交叉策略中，加入擾動策略增強了個體多樣性，防止陷入局部最優(yōu)；并且還使用了前一代最優(yōu)個體的信息，根據(jù)生物界優(yōu)勝劣汰的原則，最優(yōu)個體的信息對于種群進化必然是有利的，可以提高算法局部開采能力，加快算法的收斂速度。

1.3 自適應縮放因子

在變異策略中，縮放因子F的取值對算法至關重要。取值較大易得到最優(yōu)解,但是算法收斂速度會下降，取值較小可以加快收斂速度,但算法易出現(xiàn)停滯現(xiàn)象。綜合考慮這種情況，縮放因子F在開始前期應該保持較大值，后期改為較小值。因此，縮放因子F的變化規(guī)律符合Logistic函數(shù)模型，考慮以上所述，本文基于Logistic函數(shù)設計了一種自適應縮放因子，具體算式為

(4)

式中:t′=G/Gmax;u可以控制縮放因子F曲線的曲率。如圖1所示，u取值越小，F(xiàn)的曲線下降越緩慢，越有利于增強個體的多樣性，避免停滯；u取值越大，下降越快,有利于加快收斂速度。綜合考慮，此處u取為1。

圖1 F變化曲線

MSCADE算法流程如圖2所示。

圖2 MSCADE算法流程圖

2 仿真測試

為了核驗MSCADE算法的性能，選取了16個典型的測試函數(shù)進行實驗。所選測試函數(shù)的參數(shù)描述如表1所示，具體公式見文獻[8-9]。其中，f1～f7屬于單峰函數(shù)，其他函數(shù)均為多峰函數(shù)。

表1 測試函數(shù)

選擇了4種較先進的DE，jDE[10]，JADE[11]和SCA[7]算法與MSCADE算法進行比較。MSCADE算法中，F(xiàn)max=0.9，F(xiàn)min=0.1，NP=50；DE算法中，F(xiàn)=0.5，交叉算子均為CR=0.9。測試函數(shù)維度均為30。為了保證比較公正性，jDE,JADE和SCA算法的參數(shù)設置與對應文獻一致。最大函數(shù)評估次數(shù)為50 000。每個測試函數(shù)獨立重復運行30次，選取平均值、標準差作為最終評價標準，結果見表2。其中，加粗的數(shù)據(jù)為最優(yōu)數(shù)據(jù)，部分數(shù)據(jù)經(jīng)過保留3位有效數(shù)字得到。

表2 5種算法仿真數(shù)據(jù)比較

從表2中可以看出，MSCADE算法在f1,f2,f3和f4等11個測試函數(shù)(加粗表示)上得到的結果要優(yōu)于其他算法，并且在f4,f6,f8和f164個測試函數(shù)上能得到理論最優(yōu)解。jDE在f9,f10,f12和f134個函數(shù)上表現(xiàn)要優(yōu)于其他算法；JADE在f15上優(yōu)于其余算法。從單峰函數(shù)上看，MSCADE算法明顯可以獲得精度更高的解，說明該改進算法具有較好的全局探測能力和局部開發(fā)能力；從多峰函數(shù)上看，MSCADE算法在f8和f16函數(shù)上可以獲得全局最優(yōu)解，在其余大部分多峰函數(shù)上表現(xiàn)要優(yōu)于或近似于DE算法，說明本文改進的算法能在一定程度上跳出局部最優(yōu)解，增強搜索能力。由于在變異操作中加入的正弦余弦算法搜索機制會使用到最優(yōu)個體的信息，并且該算法主要進行局部搜索，因此會導致改進算法向最優(yōu)個體靠攏，而多峰函數(shù)存在多個局部最優(yōu)個體，所以算法在單峰函數(shù)問題方面的求解性能要優(yōu)于多峰函數(shù)。

為了更直觀地體現(xiàn)MSCADE算法的收斂性能，選取單峰函數(shù)f1和f7，多峰函數(shù)f11,f13,f15和f16等6個測試函數(shù)的收斂曲線圖進行對比。如圖3所示，圖中數(shù)據(jù)是30次獨立運行的平均值，其參數(shù)設置同上保持一致。

圖3 5種算法平均收斂曲線

由圖3可見，MSCADE算法與其余4種算法相比，不論是單峰函數(shù)f1，f7，還是多峰函數(shù)f11，f16，都是收斂速度最快、搜索精度最高，說明MSCADE算法可以有效地跳出局部最優(yōu)解。而在多峰函數(shù)f13和f15上，雖然搜索精度不是最高的，但在算法前期其收斂速度比其他算法明顯更快。由上可得，本文提出的MSCADE算法在收斂速度和精度方面均有較大提高。

3 建立數(shù)學模型

3.1 地形環(huán)境模型

在本文中，用數(shù)學函數(shù)模型模擬地貌環(huán)境并用圓柱體模擬威脅物[12-13]。其中，地貌函數(shù)模型為

(5)

式中，m=10,b=0.2,c=0.1,d=0.6,e=1,f=0.1,g=0.1，都是常數(shù)，可以控制地貌特征。

自然山峰用指數(shù)函數(shù)來表示，具體數(shù)學表達式為

(6)

式中：hj為第j座山峰的位置高度；(xj,yj)為第j座山峰的中心位置；(xsj，ysj)為第j座山峰的山體坡度參數(shù)。

3.2 適應度函數(shù)

為了確保規(guī)劃出的無人機路徑是最優(yōu)且安全的，本文以路徑長度代價、威脅代價、飛行高度代價等作為評價指標來構造適應度函數(shù)。

3.2.1 路徑長度代價

路徑長度是路徑規(guī)劃的關鍵指標，路徑長度越短，耗能耗時越少。飛行距離用從起點到終點，各相鄰點間的歐氏距離之和表示，路徑長度代價為

(7)

式中,(xi,yi,zi)是各點坐標。

3.2.2 威脅代價

(8)

(9)

式中:K表示威脅物個數(shù)；R(k)表示第k個威脅物的半徑；C是威脅懲罰因子，取值107。

3.2.3 飛行高度代價

無人機路徑規(guī)劃過程中應盡量控制高度不發(fā)生較大變化[15]，平穩(wěn)高度飛行有利于減少耗能，降低飛行成本，高度代價為

(10)

式中：n為路徑上導航點數(shù)；havg表示各點高度的平均值。

因此，無人機路徑規(guī)劃適應度函數(shù)為

f=λ1·Jl+λ2·Jd+λ3·Jh

(11)

式中，λ1，λ2，λ3為權重系數(shù)，需滿足λ1+λ2+λ3=1。

無人機路徑規(guī)劃的最佳狀況為在確保飛行安全的前提下路徑最短，故λ2的取值應大于λ1，也大于λ3。綜合考慮，在此次實驗中，權重系數(shù)λ1，λ2，λ3分別取值為0.3，0.5，0.2。

由于每次生成的點是離散的，所以生成的路徑是折線形式，為了保證路線適合實際飛行，還需對路徑進行平滑處理[16]。本文采用引入三次方樣條數(shù)據(jù)插值的策略，以保證生成的路徑是適合飛行的光滑路徑。

3.3 實驗仿真與分析

開始起點設置為(15，85，1.248 5)，目標終點為(150，40，1.467)；圓柱體威脅物的中心坐標分別設置為(10，60)，(128，60)，(100，40)，半徑分別為8，10，15。以上參數(shù)單位均為km。DE和MSCADE算法種群均為50，維度為15，其余參數(shù)設置同前一致，終止最大迭代次數(shù)為200。

三維路徑規(guī)劃圖見圖4。

圖4 三維路徑規(guī)劃圖

路徑規(guī)劃俯視圖見圖5。

圖5 路徑規(guī)劃俯視圖

從圖4和圖5中可看到，MSCADE算法可以生成一條可行的安全路徑，而DE算法規(guī)劃出的路徑更長，而且并不是每次都可以避開山峰和威脅區(qū)域;同時，可以看出MSCADE算法規(guī)劃出的路徑長度和平滑度都要優(yōu)于DE算法。

圖6是兩種算法路徑規(guī)劃的適應度值收斂曲線。從圖6中可以看出，DE算法規(guī)劃出路徑的適應度值為46.34，而MSCADE算法適應度值為42.35，具有更好的適應度值，收斂性也更好。

圖6 適應度收斂曲線

綜上所述，與DE算法相比，使用MSCADE算法規(guī)劃出的路徑不僅滿足最短路徑需求，而且還能有效地避開地形障礙物和威脅區(qū)域，從而驗證了改進算法的有效性與實用性。

4 結束語

本文基于正弦余弦算法提出一種改進差分進化算法，用來解決無人機的三維路徑規(guī)劃問題?；静罘诌M化算法因為存在早熟現(xiàn)象問題，致使三維路徑規(guī)劃效果不佳。本文在基本差分進化算法的基礎上融入正弦余弦算法搜索機制和擾動策略，可以防止陷入局部最優(yōu)解，提升算法搜索和收斂性能。仿真結果表明，改進算法規(guī)劃出的無人機路徑更短且更安全。