基于混合策略改進蜣螂優化算法的無人機三維路徑規劃

摘" 要： 針對傳統蜣螂優化（DBO）算法存在的容易陷入局部最優、搜索效率低、規劃路徑不穩定等問題，提出混合策略改進蜣螂優化（IDBO）算法的無人機三維路徑規劃方法。首先對地形、障礙物環境進行空間建模，按照約束條件制定無人機飛行總成本函數，將路徑規劃問題轉換為多約束條件下的優化問題；其次使用Circle混沌映射策略增加蜣螂種群的多樣性，建立反余弦函數公式改進邊界收斂因子，提高算法的尋優精度和平衡算法局部和全局尋優能力；最后引入人工水母搜索算法的時間控制機制和主動運動策略，實現種群個體間信息交流，提升搜索效率、多樣性，避免算法陷入局部最優，并通過動態選擇策略與自適應t分布擾動進一步提高算法的收斂速度、尋優能力。仿真結果表明，無論是在簡單還是復雜的三維環境中，IDBO算法都能表現出搜索效率高、規劃路徑短、探索節點有效性高、飛行高度穩定的優點。

關鍵詞： 無人機； 路徑規劃； 蜣螂優化算法； 混沌映射； 人工水母搜索算法； 最優路徑尋找

中圖分類號： TN919?34； TP391.9" " " " " " " " " " 文獻標識碼： A" " " " " " " " " "文章編號： 1004?373X（2024）13?0144?09

UAV 3D path planning based on hybrid strategy improved dung beetle optimizer

JING Huicheng， CAO Yuming， GE Chao， GAO Yuxing

（College of Electrical Engineering， North China University of Science and Technology， Tangshan 063210， China）

Abstract： In view of the problems existing in the traditional dung beetle optimizer （DBO）， such as being prone to falling into local optimum， low search efficiency and unstable path planning， a UAV （unmanned aerial vehicle） 3D path planning method based on hybrid strategy improved dung beetle optimizer （IDBO） is proposed. The space modeling of terrain and obstacle environment is carried out， and the total cost function of UAV flight is established according to the constraint conditions， and the path planning problem is transformed into an optimization problem with multi?constraint conditions. The Circle chaotic mapping strategy is used to increase the diversity of dung beetle population. The inverse cosine function formula is established to improve the boundary convergence factor， so as to improve the optimizing accuracy of the algorithm and balance its local and global optimizing ability. The time control mechanism and active motion strategy of the artificial jellyfish search （JS） optimizer are introduced to realize information exchange among population individuals and improve search efficiency and diversity， so as to avoid the algorithm from falling into local optimal. The convergence speed and optimizing ability of the algorithm are further improved by dynamic selection strategy and adaptive t?distribution disturbance. The simulation results show that the IDBO has the advantages of high search efficiency， short planning path， high validity of searching nodes and stability of flight height， whether in simple or complex 3D environment.

Keywords： UAV; path planning; DBO; chaotic mapping; artificial JS optimizer; path optimizing

0" 引" 言

無人機路徑規劃是無人機任務規劃系統中的一項關鍵任務，需要在特定約束條件下獲得從起始位置到預期目的地的安全高效的路徑。一般來說，無人機路徑規劃被認為是一個復雜的優化問題，因此需要一種有效的算法來解決這一問題。

傳統路徑規劃算法如A*算法[1?2]、Dijkstra算法[3]、深度優先搜索算法[4]等被廣泛應用于無人機路徑規劃中，但這些圖搜索算法往往只對路徑最短化進行了研究，在實際路徑規劃中需要考慮到實際成本以及眾多約束條件對路徑規劃的影響，專家學者們發現啟發式算法更適合求解此類具有多個約束條件的問題，于是對啟發式算法展開了豐富研究。文獻[5]利用遺傳算法對粒子群算法進行改進，有效提高了新一代粒子群的質量，減少了算法迭代次數，優化了算法尋優路徑。文獻[6]結合自適應權重方式和閾值思想對袋獾優化算法進行改進，提高了算法收斂速度、收斂精度和對三維路徑規劃問題的求解能力。文獻[7]成功融合甲蟲搜索算法和退火算法，規劃出了多障礙物情況下的最優路徑。文獻[8]使用人工勢場法對蟻群算法進行改進，改進信息素更新規則和啟發函數，提高了算法搜索路徑的效率和能力。

上述方法在一定程度上改善了各算法存在的缺點并提升了其進行路徑規劃的性能，但是在面對復雜多變的環境時，現有方案仍存在路徑搜索算法效率低、尋優性能不穩定、易陷入局部最優的問題。因此，本文提出了一種混合策略改進的蜣螂優化（IDBO）算法，并將其應用于無人機三維路徑規劃中。算法前期使用Circle混沌映射策略優化初始種群在解空間中的分布，對蜣螂種群的多樣性進行改善；通過反余弦函數公式對影響蜣螂最佳產卵、覓食區域的邊界收斂因子[R]進行改進，平衡算法局部和全局尋優能力；引入時間控制機制和主動運動策略，提升算法尋優效率和多樣性，避免算法陷入局部最優；使用自適應t分布算子擾動和動態選擇策略，提高算法收斂速度和局部最優解精度。在考慮與路徑相關的最優性、安全性和可行性約束成本后，制定總飛行成本函數，利用改進算法解決優化問題，獲得高質量路徑。

1" 無人機飛行路徑規劃問題及建模

本文使用的路徑規劃數學模型主要模擬無人機在簡單和復雜危險環境下完成飛行任務，為此考慮了多個約束成本。

1.1" 路徑長度成本

[Xi]表示無人機需要飛行通過的[n]個路徑點的列表，每個路徑點都對應于搜索地圖中的一個帶有坐標的路徑節點[Pij=xij，yij，zij]。兩節點之間的歐氏距離表示為[PijPi，j+1]，路徑長度成本表示為[F1]。

[F1Xi=j=1n-1PijPi，j+1] （1）

1.2" 威脅成本

除了長度最優性外，規劃的路徑還需要考慮其安全性和可行性，通過引導無人機對路徑空間中出現的障礙威脅進行避障來確保無人機的安全運行。設[K]為所有威脅的集合，規定每個威脅都在一個圓柱體中，圓柱投影為中心坐標是[Ck]、半徑為[Rk]的圓，如圖1所示。在給定的路徑段[PijPi，j+1]的威脅成本與距離[dk]成正比。

[S]為危險區域到碰撞區域的距離，直徑[D]由無人機尺寸決定，通過障礙物集合[K]的路徑點[Pij]計算威脅成本[F2]，如下所示：

[F2Xi=j=1n-1k=1KTkPijPi，j+1，" " " "TkPijPi，j+1=0，" " dkgt;S+D+Rk（S+D+Rk）-dk，" " " " " " " " " "D+Rklt;dk≤S+D+Rk∞，" " dk≤D+Rk] （2）

1.3" 飛行高度成本

在路徑規劃過程中，無人機飛行高度被限制在兩個給定的極值，即最小高度[hmin]和最大高度[hmax]之間，當飛行高度未處于閾值范圍內或者處于閾值邊界時會遭受懲罰機制：

[Hij=（hij-hmax+hmin）hij，" " （hmax+hmin）2≤hij≤hmax（hmax-hmin）hij，" " " hmin≤hij≤（hmax+hmin）2∞，" " " "otherwise] （3）

式中：[hij]為相對于地面的飛行高度；[Hij]為懲罰因子用于確保無人機處于安全飛行高度。由所有路徑點的[Hij]相加得出高度成本：

[F3Xi=j=1nHij] （4）

1.4" 轉向角/爬升角成本（平滑成本）

無人機的轉向角和爬升角對路徑規劃至關重要，以此構建路徑平滑成本函數。其中，轉向角[?ij]是在水平面[Oxy]上投影的兩個連續路徑段[P'ijP'i，j+1]和[P'i，j+1P'i，j+2]之間的夾角。設[k]為[z]軸方向上的單位向量，投影向量計算公式見式（5），轉向角計算公式見式（6）。

[P'ijP'i，j+1=k×PijPi，j+1×k] （5）

[?ij=arctanP'ijP'i，j+1×P'i，j+1P'i，j+2P'ijP'i，j+1?P'i，j+1P'i，j+2] （6）

爬升角[ψij]是[PijPi，j+1]與其投影[P'ijP'i，j+1]在水平面上的夾角，其計算公式為：

[ψij=arctanzi，j+1-zijP'ijP'i，j+1] （7）

最后得到路徑平滑成本為：

[F4Xi=a1j=1n-2?ij+a2j=1n-1ψij-ψi，j-1] （8）

式中：[a1]和[a2]分別為轉向角和爬升角的懲罰系數。

1.5" 總成本函數

通過考慮上述各項與路徑相關的成本約束，可定義總成本函數為：

[FXi=k=14bkFkXi] （9）

式中：[bk]為權重系數；[F1]～[F4]分別為路徑長度成本、威脅成本、飛行高度成本和平滑成本。將總成本函數作為無人機路徑規劃的適應度函數。

2" 混合策略改進蜣螂優化算法

2.1" Circle混沌映射策略

初始化策略的選擇決定了初始種群在解空間中的分布。在原始DBO算法[9]中，種群使用隨機生成方法進行初始化，盡管這種方法簡單易行，但是隨機生成的分布具有不確定性，會導致算法的性能受到影響。在原算法的種群初始化中引入Circle混沌映射策略，增大對解空間的搜索范圍，使用混沌變量取代隨機變量，使種群在搜索空間分布更加均勻，以此增加種群多樣性和提高算法收斂速度。Circle混沌映射策略描述如下：

[xn+1=modxn+a-b2πsin（2π×xn），1] （10）

[xn+1=lb+（ub-lb）*xn+1] （11）

式中：[t]為迭代次數；[xi]代表第[i]個蜣螂的位置信息。式（10）表示進行Circle運算，以維度30為例，[a]取0.2，[b]取0.5。式（11）表示將得到的映射結果進行種群初始化，lb為區域下限，ub為區域上限。

由圖2可看出，經過Circle混沌映射后種群蜣螂個體分布更均勻，種群多樣性更加豐富。

2.2" 反余弦函數策略

原DBO算法中的邊界收斂因子公式是[R=1-ttM]，[tM]為最大迭代次數，其變化規律是一條斜率不變的直線。從該公式中可以看出原DBO算法通過[R]的大小變化來改變蜣螂產卵區域和最佳覓食區域的范圍，前期較大的[R]值對應較大最佳產卵和覓食區域范圍，后期較小的[R]值對應較小的最佳產卵和覓食區域范圍。原算法中的這種變化規律是為了保證算法較好的全局搜索能力和較好的跳出局部最優能力，但邊界收斂因子[R]在迭代后期下降過快會導致算法在迭代后期搜索效率變差、精度變低，使算法局部尋優性能下降。為了改善原DBO算法存在的這種全局尋優能力與局部尋優能力的不平衡關系，本文提出一種反余弦函數公式對原算法中的收斂因子進行改進。改進后的收斂因子[R]如式（12）所示：

[R=arccos2ttM-1π] （12）

圖3中[R1]為原收斂因子隨迭代次數增加的變化曲線，[R2]為改進后的收斂因子曲線。在改進后，邊界收斂因子在迭代前期相對于原文中的收斂因子下降得更快，最佳產卵覓食區域在前期迭代過程中的變化范圍相對較大，這樣可以加快算法的整體收斂速度。在迭代后期，改進后的邊界收斂因子相對于原收斂因子下降速度更慢，最佳產卵覓食區域范圍變換幅度較緩，算法擁有更穩定的空間去進行局部尋優，從而有效提高算法的尋優精度和平衡算法局部和全局尋優能力。

2.3" 主動運動策略與時間控制機制

原DBO算法中小蜣螂覓食過程位置更新公式采用的是根據最佳覓食區域的動態上下界范圍進行隨機搜索的策略，小蜣螂種群內個體未產生信息交互，個體之間無法互相學習和借鑒，搜索方式隨機導致效率不高、易陷入局部最優，并且在對邊界收斂因子公式進行改進后，算法的局部尋優能力得到增強的同時也增加了算法后期易陷入局部最優的風險，這些條件都會影響到DBO算法最終的尋優精度和收斂速度。

為改進這些缺陷，受人工水母搜索算法（JS）[10]啟發，對原算法中的覓食蜣螂位置更新公式進行改進。引入JS算法中的主動運動策略，在算法迭代后期讓其余蜣螂以覓食蜣螂群體中擁有最多食物的蜣螂為導向，借助其位置進行覓食行為，這樣覓食群體中的個體產生了信息交流，每只覓食蜣螂都能朝著最優方向運動，從而能更好地尋找食物，增強算法尋優效率，如圖4所示。

覓食蜣螂運動方向為[Direction]，[Step]為位置更新的步長，公式如式（13）、式（14）所示：

[Direction=Xj（t）-Xi（t），" " fXi≥fXjXi（t）-Xj（t），" " fXilt;fXj] （13）

[Step=rand（0，1）×Direction] （14）

式中[Xj（t）]為隨機選擇的不同于[Xi（t）]的小蜣螂[j]的位置。當蜣螂[j]所在地點的食物數量超過[i]類蜣螂所在地點的食物數量，也就是[Xj（t）]優于[Xi（t）]時，[Xi（t+1）]向[Xj（t）]靠攏；反之，[Xi（t+1）]遠離[Xj（t）]。

加入時間控制機制函數[c（t）]以更好地調節覓食蜣螂在主動運動策略位置更新方式與原位置更新方式之間的關系。時間控制機制包括一個時間控制函數[c（t）]和一個常數[C0]。[c（t）]是一個隨時間在0～1之間波動的隨機值，如式（15）所示：

[c（t）=1-ttM×2×rand（0，1）-1] （15）

本文想讓算法在前期搜索空間較大時以原隨機策略進行更新，在中后期階段以主動運動策略位置更新方式進行更新，常數[C0]起初未確定實際值，通過觀察[c（t）]在0～1之間隨機變化曲線（見圖5），將常數[C0]設為0.5，即0和1的平均值。也就是說，當[c（t）]值超過[C0]=0.5時，蜣螂會按照原位置更新公式進行覓食行為，當[c（t）]的值小于[C0]=0.5時，蜣螂會采取主動策略進行位置更新。至此形成新蜣螂覓食位置更新公式（16）：

[xi（t+1）=Step?（xi（t）+C1×（xi（t）-lbb）+" " " " "C2×（xi（t）-ubb）），" " " C（t）lt;C0xi（t）+C1×（xi（t）-lbb）+" " " " " C2×（xi（t）-ubb），" " " "C（t）≥C0] （16）

這種主動運動策略的位置更新方式使覓食蜣螂群體中個體與個體之間擁有信息交互的能力，讓算法在迭代后期實現有目的性的搜索，改善小蜣螂位置更新公式過于隨機的缺陷，提升覓食蜣螂群體的搜索效率、多樣性，避免算法陷入局部最優。

2.4" 動態選擇策略與自適應t分布

使用t分布變異算子對蜣螂位置進行擾動，這種t擾動的方式在很多算法中都被證明是極為有效的，它可以加深算法前期對解空間的探索程度、提高搜索局部最優解的精準度，從而提高算法的收斂速度、收斂精度。t擾動位置更新如式（17）所示：

[xit+1=xi（t）+xi（t）×titer] （17）

但由于所有個體均引入了變異算子，會掩蓋算法原有優勢，增加迭代時間，因此需要采用動態選擇策略，通過概率[p]調節變異算子的使用頻率，計算公式如式（18）所示，本文設置[w1]=0.5，[w2]=0.1。

[p=w1-w2（tM-t）tM] （18）

2.5" IDBO算法流程

IDBO算法流程圖如圖6所示。

3" 算法仿真與結果分析

3.1" 標準測試函數實驗

仿真實驗平臺為Matlab 2021a，為了測試IDBO算法的性能，選用4個單峰基準函數和3個多峰基準函數進行算法性能的測試。單峰基準函數用于測試算法的局部開發性能，多峰基準函數用于測試算法在局部開發和全局探索中的自適應轉換能力，測試函數信息如表1所示。

選取8個近年來提出的優秀算法作為對比算法，分別為引入了引力加速度思想的PSO算法（TACPSO）[11]、GWO算法[12]、ALO算法[13]、WOA算法[14]、SSA算法[15]、ChOA算法[16]、JS算法以及傳統的DBO算法。為了公平比較，所有算法在測試函數解維度設置相同，種群規模均設置為30，搜索空間設置相同范圍，所有算法分別在每個測試函數上進行30次獨立運算，每次運行的最大迭代次數為500，通過比較30次運行結果中的最佳值（Best）、平均值（Average）和標準差（STD）來驗證算法性能。表2為對比實驗結果，圖7為算法迭代收斂曲線對比圖。

結合表2中結果和圖7來看，IDBO算法在[F1]、[F2]、[F3]函數上都能以最快的收斂速度鎖定全局最優解，說明了本文引入的主動運動策略和時間控制機制有效地避免了算法陷入局部最優并提高了收斂速度。在[F4]函數上，雖然IDBO并未搜索到最小值，但其得到的最佳值和平均值要高于其余對比算法。在多峰函數測試中，IDBO算法搜索精度高并且得到的平均值和標準差優于對比算法，雖然也存在其他算法能搜索到最小值的情況，但是從適應度函數收斂曲線上可以看出，IDBO算法的收斂速度最快，所消耗迭代次數最少，這說明了引入的混沌映射策略、邊界收斂因子改進、自適應t擾動策略的有效性。

無論是面對單峰還是多峰測試函數，IDBO算法都能在保證收斂精度的同時表現出很快的收斂速度。將不同算法在7個測試函數上的平均值結果與各算法的收斂速度相結合進行排名，排名規則為：按算法平均尋優精度排名，若精度相同則按達到最優結果時的收斂速度排名。最后得到的尋優性能排名由高到低排序為：IDBO、DBO、JS、SSA、WOA、GWO、TACPSO、ChOA、ALO。

3.2" 無人機三維路徑規劃仿真

地形建模數據來自數字高程模型（Digital Elevation Model， DEM）地圖中真實的地形數據，仿真地圖大小設置為810 m×810 m×400 m，無人機初始點坐標設置為（200，100，150）m，目標點為（800，800，150）m。采用圓柱體對障礙物進行建模，選取在3.1節測試函數實驗中排名前四位的另外三種算法作為對比算法，在相同條件下進行三維路徑規劃仿真，驗證IDBO算法在不同環境下路徑規劃的有效性。四種算法種群規模設置為50，最大迭代次數設置為100。

場景一為無人機在障礙數[n]=5的簡單環境下進行路徑規劃，圖8給出了不同算法在該環境下運行50次得到的最優路徑規劃三維視圖、俯視圖、飛行高度圖，圖9為適應度迭代曲線圖。

從圖8中可以看出：四種算法都能有效規避障礙物到達目標點，SSA算法容易陷入局部最優且路徑最長，原DBO算法在遭遇第一個障礙物時未能選擇合適的方向進行后續路徑規劃導致路徑規劃質量也不理想；相比之下，JS算法和IDBO算法得到的路徑曲線更優，結合圖9進一步分析，IDBO算法僅需32次迭代就能得到最優路徑，JS算法在第90次迭代時才得到最優路徑，并且IDBO算法的飛行總成本更低。從不同角度的路徑對比圖還可以明顯看出，IDBO算法規劃的路徑曲線相較于其他三種算法拐點更少，整體路徑更加平滑，飛行高度曲線也更平穩。

表3給出了四種算法在簡單環境下運行50次的最優適應度、最差適應度和平均適應度，適應度值對應路徑規劃的總成本。

由表3可知，本文提出的IDBO算法的平均路徑規劃成本相對于原DBO算法降低了10.6%，并且優于JS算法和SSA算法；在最優路徑規劃成本與最劣規劃成本上，IDBO算法也優于其他三種算法，說明了IDBO算法的尋優穩定性高。

綜上，IDBO算法在簡單三維障礙物環境下表現出優秀的適應性。

為進一步驗證IDBO算法的優越性，將模型障礙數增加到9個，不同算法在此復雜環境下運行50次得到的最優路徑規劃三維視圖、俯視圖、飛行高度圖及適應度迭代曲線如圖10、圖11所示。

從圖10可以看出，隨著障礙物數量的增多，SSA、JS、DBO算法在此復雜環境下規劃出的路徑質量較差，而本文所提的IDBO算法仍能快速收斂，依然可以生成一條安全、高效的飛行路徑。

再結合圖11分析，不難發現IDBO算法擁有比其他算法收斂速度更快、規劃的路徑更短、探索節點的有效性更高、飛行高度更加穩定的優勢，從側面驗證了本文算法在局部和全局搜索階段引入的各項改進策略能有效解決環境復雜度增加的情況下的路徑規劃問題。

表4給出了四種算法在復雜環境下運行50次的最優適應度、最差適應度和平均適應度。

由表4可以看出，IDBO算法得到的各結果均優于JS、SSA、DBO算法，相對于原DBO算法，IDBO算法的平均路徑規劃總成本降低了12.03%。故本文算法在復雜三維環境中也能表現出優秀的路徑規劃性能。

4" 結" 語

針對DBO算法存在的容易陷入局部最優、搜索效率低等問題，本文利用Circle混沌映射策略、反余弦函數策略、時間控制機制和主動運動策略、動態選擇策略與自適應t分布擾動對DBO算法進行了改進。基于標準測試函數仿真實驗，驗證了IDBO算法相對于其他7種對比算法具有收斂速度快、搜索精度高的優點。最后將IDBO算法應用于無人機三維路徑規劃之中，考慮路徑長度成本、、路徑安全成本、飛行高度成本、轉向角與爬升角成本約束，仿真實驗結果表明，相比于其他算法，IDBO算法在路徑長度與平滑度、總成本函數和收斂速度方面表現出優越的性能，能夠有效實現無人機不同環境下的三維路徑規劃。

參考文獻

[1] 高九州，徐威峰，張立輝，等.基于改進A*算法的無人機避障航線規劃[J].現代電子技術，2023，46（8）：181?186.

[2] 田茹，曹茂永，馬鳳英，等.基于改進A*算法的農用無人機路徑規劃[J].現代電子技術，2022，45（4）：182?186.

[3] DHULKEFL E， DURDU A， TERZIO?LU H. Dijkstra algorithm using UAV path planning [J]. Konya journal of engineering sciences， 2020， 8： 92?105.

[4] TANG G， TANG C Q， ZHOU H， et al. R?DFS： A coverage path planning approach based on region optimal decomposition [J]. Remote sensing， 2021， 13（8）： 1525.

[5] 胡觀凱，鐘建華，李永正，等.基于IPSO?GA算法的無人機三維路徑規劃[J].現代電子技術，2023，46（7）：115?120.

[6] 柯永斌，謝田，姜程文，等.基于改進袋獾優化算法的無人機路徑規劃[J].電子器件，2023，46（2）：397?403.

[7] 楊青青，鄧敏儀，彭藝.基于改進甲蟲搜索算法的城市無人機路徑規劃[J].系統仿真學報，2023，35（12）：2527?2536.

[8] 孔維立，王峰，周平華，等.改進蟻群算法的無人機三維路徑規劃[J].電光與控制，2023，30（3）：63?69.

[9] XUE J K， SHEN B. Dung beetle optimizer： A new meta?heuris tic algorithm for global optimization [J]. The journal of supercomputing， 2023， 79（7）： 7305?7336.

[10] CHOU J S， TRUONG D N. A novel metaheuristic optimizer inspired by behavior of jellyfish in ocean [J]. Applied mathema?tics and computation， 2021， 389： 125535.

[11] 唐文倩，徐海芹，劉洋.基于改進PSO混合算法的無人機三維路徑規劃研究[J].青島大學學報（自然科學版），2023，36（3）：57?63.

[12] 劉紫燕，吳應雨，梁靜，等.基于雜交策略的自適應灰狼優化算法[J].計算機應用研究，2022，39（1）：113?117.

[13] 李庚松，劉藝，鄭奇斌，等.基于蟻獅算法的元特征選擇方法[J].系統工程與電子技術，2023，45（9）：2831?2842.

[14] 李安東，劉升.混合策略改進鯨魚優化算法[J].計算機應用研究，2022，39（5）：1415?1421.

[15] XUE J K， SHEN B. A novel swarm intelligence optimization approach： Sparrow search algorithm [J]. Systems science amp; control engineering， 2020， 8（1）： 22?34.

[16] KHISHE M， MOSAVI M R. Chimp optimization algorithm [J]. Expert systems with applications， 2020， 149： 113338.