



















摘 要:山區地勢具有陡峭、溝深壑大的環境特點,導致基于啟發式算法的山區無人機路徑規劃速度慢、質量差,針對該問題提出了基于自適應動作策略蜣螂算法的路徑規劃方法。以路徑長度、飛行安全性以及路徑平滑度構建路徑規劃目標函數;在蜣螂算法中引入種群相似性動作變異策略和反向學習策略,平衡局部優化和全局優化能力;通過對比麻雀算法、蜣螂算法和灰狼算法在12 個基準函數上的算法性能,結果表明所提方法具有更快的收斂速度、不易陷入局部最優。山區路徑規劃仿真實驗表明,所提方法比蜣螂算法的路徑規劃質量提高了37. 66% 。
關鍵詞:路徑規劃;蜣螂算法;反向學習;自適應動作策略
中圖分類號:TP242;TP18 文獻標志碼:A 開放科學(資源服務)標識碼(OSID):
文章編號:1003-3106(2024)04-0928-09
0 引言
山區地形的復雜性、起伏高差較大和交通不便等特點常常導致部分區域難以通過傳統方式進行探測、巡視和物資配送等工作,而無人機憑借其機動靈活的優勢在山區得到廣泛應用,因此在山區復雜環境下,高質量、快速地規劃飛行路徑對提高無人機任務效率具有重要意義[1-2]。
面向無人機三維路徑規劃問題,許多學者基于啟發式算法展開了豐富的研究。藺文軒等[3]針對三維路徑規劃問題,在粒子群算法中引入分組優化策略,并在小組粒子優化時采取模擬退火操作,有效避免了陷入局部最優和收斂慢的缺點。蘇菲[4]在傳統蝙蝠算法中引入黃金正弦算法,對最優個體進行全維和單維搜索,提高了收斂速度。黃鶴等[5]在飛蛾撲火算法中引入交叉算子和高斯變異算子,增強了全局搜索能力并提高了算法尋優精度。巫茜等[6]提出了改進信息素更新規則的蟻群算法并引入航跡導航因子,一定程度上克服了山區影響,避免路徑陷入局部最優。郭啟程等[7]在鯨魚優化算法中加入萊維飛行進行隨機擾動,并引入信息交流機制平衡搜索能力,提高收斂精度和速度。Zeng 等[8]基于距離動態鄰域設計粒子群算法速度更新機制并與差分進化算法進行融合以緩解過早收斂,增強搜索能力。段建民等[9]將遺傳算法和改進的人工勢場模型結合并行搜索,利用人工勢場法優化遺傳算法全局路徑,增強跳出局部最優的能力。許諾[10]將粒子群算法與遺傳算法結合,設置動態慣性權重并引入步長因子平衡局部和全局搜索。
上述方法在一定程度上提升了規劃路徑的質量和算法的收斂速度,但是面向山區陡峭地勢的復雜環境,仍存在路徑規劃效果差的問題。因此,本文分析無人機運動約束條件和路徑規劃要求,構建了山區環境中三維路徑規劃問題模型;結合蜣螂算法位置更新策略多的優勢,引入反向學習策略和種群相似性變異策略,提出自適應變異蜣螂算法(AdaptiveMutation Dung Beetle Algorithm,AMDBO)使得在進行山區路徑規劃時蜣螂能自適應地選擇動作,從而有效跳出局部最優,獲得高質量路徑。
1 無人機三維路徑規劃目標函數
無人機三維路徑規劃問題屬于優化問題,本文從路徑長度、路徑平滑度和飛行安全度方面構建路徑規劃目標函數。
① 路徑長度
路徑長度是判斷路徑質量的重要依據,路徑長度越短,越有利于無人機節省能耗[11]。因此路徑長度為:
式中:n 為航跡點數目,(xi,yi,zi)為第i 個航跡點的位置。
② 路徑平滑度
規劃路徑應盡量減少大角度偏航和高度的突變,需要保持路徑平滑。由于山區陡峭、落差大的地形特點,無人機在山區飛行需要飛行路徑滿足自身最大爬升角和爬升率的要求[12]。li 表示2 個航跡點之間的距離,式(2)和式(3)分別表示偏轉角φi 和俯仰角i,路徑平滑度成本函數定義為式(4)。
③ 飛行安全性
路徑規劃中的路徑還必須要確保無人機的安全運行,因此引入飛行安全性能夠引導無人機躲避環境中的障礙物[13]。如圖1 所示,空域內存在中心坐標為Ok,半徑為Rk 的障礙物k,無人機的飛行節點與障礙物的垂線距離dk 應該大于安全距離閾值S,即無人機必須限定在陰影之外的區域飛行,才能確保飛行的安全,飛行安全性的計算如下:
對上述各類成本函數進行加權綜合,構成多目標路徑規劃問題的目標函數F:
F = ω1 Fl + ω2 Fe + ω3 Fs , (6)
式中:Fl、Fe、Fs 依次為上述3 種代價函數,ω1 、ω2 、ω3 分別為路徑長度、航跡平滑度和飛行安全性的權重系數。目標函數值越小代表路徑質量就越好。
2 蜣螂優化算法
2. 1 原始蜣螂算法
蜣螂優化算法(Dung Beetle Optimizer Algorithm,DBO)是一種新穎的群體智能算法,通過模擬蜣螂的滾球、繁殖、覓食和偷竊4 個動作行為進行位置更新和優化,每種策略側重的方向有所不同[14]。蜣螂算法的多樣化位置更新策略可以更加全面地探索搜索空間,在實際應用中能夠有效地解決復雜的搜索和優化問題。
① 滾球行為
蜣螂滾球行為分為有障礙模式和無障礙模式。當無障礙時,光源的強度會影響蜣螂的位置,蜣螂在滾球行為過程中位置更新如式(7)所示;當遇到障礙物無法前進時,通過使用切線函數來模擬跳舞行為,位置更新如式(8)所示。
xt+1i = xti+ λ·k·xt-1i + b· xti- xworst , (7)
xt+1i = xti+ tan(θ) xti- xt-1i , (8)
式中:xti為t 次迭代時第i 個個體的位置,λ 模擬自然因素隨機取-1 或1,k 為[0,1]的隨機偏轉系數,b為隨機系數,xworst 為最差個體位置。
② 繁殖行為
利用邊界選擇策略來模擬蜣螂產卵的安全區域,如式(9)所示;確定產卵區域后,雛球的位置隨產卵區域進行動態變化,如式(10)所示。
式中:xlbest 為局部最優解,R = 1- t/tmax,tmax 為最大迭代次數,t 為當前迭代次數;Lb 為下界,Ub 為上界,b1 、b2 為2 個D 維獨立隨機向量。
③ 覓食行為
覓食區域同樣利用邊界選擇策略來動態模擬,如式(11)所示。覓食蜣螂會在局部范圍內進行覓食行為,蜣螂的位置更新如式(12)所示。
式中:xgbest 為全局最優解,C1 為服從正態分布的D維隨機向量,C2 為[0,1]的D 維隨機向量。
④ 偷竊行為
最佳食物來源則是最適合競爭食物的地方,偷竊蜣螂的位置更新如下:
xt+1i = xgbest + S × g × ( xti- xgbest + xti- xlbest ),(13)
式中:S 為常數,g 為服從正態分布的D 維隨機向量。
從4 種個體行為的位置更新公式可知,只有滾球行為在算法各時期都具有較好的全局搜索能力;覓食行為在自身位置附近根據動態上下界范圍進行搜索,動態上下界會越來越小,使得覓食行為隨著迭代次數的增加從全局搜索變為局部搜索;繁殖行為和偷竊行為則是在最佳個體的附近根據動態上下界范圍進行局部搜索。
2. 2 自適應蜣螂算法
2. 2. 1 混沌序列初始化種群
在處理復雜的優化問題時,原始蜣螂算法采用隨機生成種群的方法進行種群初始化,可能會導致種群多樣性低、種群分布不均勻和快速收斂到局部最優解等問題。Tent 混沌映射可以生成均勻遍布解空間和相關性較強的初始種群[15],因此本文引入Tent 混沌映射作為改善蜣螂算法初始化種群多樣性的方法,從而提高智能算法的求解精度和收斂速度。Tent 混沌映射公式如下所示:
對x0 賦初值,經過循環迭代,可以得到[0,1]的隨機序列,該序列具有良好的統計特性,通常用于生成算法的初解,以增加物種的多樣性。當控制參數α =0. 45 時,初始總體(一維)分布如圖2 所示。
蜣螂種群初始化過程如下:先隨機生成一個[0,1]的D 維向量作為初始混沌序列;然后將D 維向量的每一維數值依次帶入式(14)計算生成一個新的D 維向量作為第2 個混沌序列,重復上述步驟,直到生成N 個混沌序列;最后將全部混沌序列映射到種群個體的取值范圍內,生成Tent 混沌初始化蜣螂種群。
2. 2. 2 自適應的蜣螂行為變異策略
針對原始蜣螂算法4 種動作行為的分配比例不均勻,且每個個體只能進行一種動作行為,可能會導致對解空間的搜索不充分或收斂速度慢的問題,本文提出了基于種群相似性的蜣螂動作變異策略和反向學習策略。
① 基于種群相似性的蜣螂動作變異策略
為了使每個蜣螂都能執行4 種動作行為,本文用迭代次數模擬時間變化,每隔M 次迭代進行一次蜣螂的動作變異,將當前動作行為變異為下一種行為策略。本文利用余弦相似度來衡量種群相似性,種群多樣性表示如下:
當Diver 大于0. 5 時,種群多樣性過低,可能會陷入局部最優,而滾球蜣螂和覓食蜣螂的數量決定了算法對解空間的探索能力和收斂速度。因此將執行繁殖和覓食行為的個體變異為執行滾球行為的個體,增強算法的全局搜索能力以增強物種多樣性,找到新的最佳個體或達到變異個體迭代閾值Tmax 后將變異個體重新恢復為原來的行為個體繼續搜索。
② 反向學習策略
由于繁殖和偷竊行為的全局搜索能力會隨著迭代次數的增加而下降,而反向學習策略[16]的思想主要是通過生成當前可行解的反向解,并將反向解與原解進行適應度比較選出更好的解,本文利用反向學習策略增強繁殖和偷竊行為的全局搜索能力:
式中:xtr 為反向解,lb 和ub 為D 維向量表示每一維的下界和上界,rand()為D 維隨機向量,xti為當前可行解。
綜上所述,AMDBO 算法流程如圖3 所示。
3 仿真實驗與分析
本文的仿真實驗分為兩部分:① 在CEC2017中選擇具有不同特征的基準函數[17],對比不同算法最優解的搜索速度和搜索質量,驗證AMDBO 算法的收斂性能、是否具備跳出局部最優的能力;② 構建山區路徑規劃環境,對比不同算法路徑搜索速度和路徑質量,驗證AMDBO 算法在復雜山區環境是否仍具有較快的收斂速度和尋優能力。
3. 1 基于多樣性基準函數的算法性能分析
為了驗證AMDBO 算法的尋優性能,本文選取DBO、改進灰狼算法(Improved Grey Wolf OptimizerAlgorithm,IGWO)和麻雀搜索算法(Sparrow SearchAlgorithm,SSA)在CEC2017 中的12 個具有不同特征的基準函數上進行算法性能的對比分析。其中,選擇5 個單峰基準函數(F1 ~ F5 )分析各算法的單目標求解能力,選擇4 個多峰基準函數(F6 ~ F9 )和3 個混合基準函數(F10 ~ F12 )分析算法能否跳出局部最優。測試函數具體信息如表1 所示。
為了提高測試結果的可靠性,降低啟發式算法隨機性的影響,本文將所有算法的種群大小和迭代次數分別設置為30 和500,對每個基準函數都運行30 次[18],得到30 次獨立運行下的最優值(該最優值指的是本次運行下取得的目標函數最優值),并統計出平均值(Mean)、最佳值(Best)和標準差(Std),統計對象為30 次獨立運行下的最優值結果。平均值表現的是算法對該目標函數的平均的優化能力;最佳值表現的是30 次算法運行中對目標函數的最佳優化效果;標準差表現的是算法在該目標函數上優化能力的穩定性。4 種優化算法對12 個基準函數的測試結果對比如表2 所示。
在5 個單峰基準函數(F1 ~ F5 )測試中,AMDBO在F1 ~ F4 基準函數上的Mean、Std 和Best 均優于其他3 種算法。對比F5 基準函數下Mean、Std 和Best的具體數值比較可知:DBO 的Best 比AMDBO 的Best僅高57. 76% ,但是AMDBO 的Mean、Std 分別比DBO的值高了73. 80% 和109. 52% 。綜合F1 ~ F5 的整體表現,AMDBO 的整體性能優于其他3 種算法。
在4 個多峰基準函數(F6 ~ F9 )測試中,AMDBO的Mean 和Best 均獲得了第一且精度高于DBO 和IGWO;AMDBO 的Std 除了在F6 上略低于SSA,在其他多峰基準函數上都遠遠優于IGWO 和DBO。
在3 個混合基準函數(F10 ~ F12 )的測試中,4 種算法的Best 均能取得理論最優解;AMDBO 的Mean和Std 在F10 和F11 上略低于IGWO,但也都優于SSA 和DBO;在混合基準函數F12 上,4 種算法都能得到理論最優的Mean 和Best,但AMDBO 的Std 優于其他3 種算法。雖然其他算法的Mean 和Best 都能達到理論最優值,但是AMDBO 的收斂速度更快、迭代次數更少。圖4(j)~ 圖4(l)為混合基準函數(F10 ~ F12 )測試的收斂曲線,AMDBO 的收斂速度僅次于SSA,優于DBO 和IGWO。
綜合上述測試,在3 類基準函數上AMDBO 的Mean 和Best 大部分優于其他3 種算法;在收斂到相同精度的結果時,AMDBO 所用的迭代次數也更低。DBO 性能略差于AMDBO,但是大部分測試結果相比SSA 和IGWO 較優或齊平。
3. 2 面向山區三維路徑規劃分析。
讀取某一山區環境的數字高程模型地圖,該地區最大高度落差超過2 km,地勢起伏劇烈分布溝壑眾多,在該地形中隨機生成環境擾動如圖5 所示(粉色圓柱)。設置無人機的起點和終點分別為(10,90,1. 115)和(130,10,1. 367),單位為km。由3. 1 中的算法性能實驗可知DBO 與SSA、IGWO 相比,性能更優,因此路徑規劃實驗中選取DBO 與AMDBO 進行對比。算法中種群個體數量統一為30,最大迭代次數為500。基于AMDBO 和DBO 生成的路徑如圖5 和圖6 所示,圖中,線路1 為AMDBO 算法路徑規劃結果,線路2 為DBO 算法路徑規劃結果。
對比DBO 和AMDBO 的飛行路徑可以看出,原始DBO 在進行迭代時陷入了局部最優,且飛行路徑長沒有規避環境擾動,飛行高度低沒有保障離地安全高度;而AMDBO 算法的飛行路徑平滑,有效規避了環境擾動并且保障了與障礙物之間的距離和離地安全高度。
目標函數收斂曲線如圖7 所示。可以看出,原始DBO 的收斂較慢,在250 次迭代之后逐漸開始收斂。本文算法在開始時能夠快速地持續搜索,在200 次迭代之后逐漸收斂,且收斂值低于DBO,結果表明DBO 在迭代次數達到95 和150 時都陷入了局部最優,驗證了AMDBO 具備跳出局部最優的能力。
綜合各類表現看,本文算法具有更快的收斂速度且能快速跳出局部最優解,能夠在山區復雜環境中規劃出較高質量的路徑。
4 結束語
受山區環境影響,基于啟發式算法的路徑規劃易陷入局部最優且收斂速度慢,本文在蜣螂算法進行初始化時引入混沌初始化使得種群分布更均勻,有效提高了種群多樣性;構建了種群相似性動作變異策略和反向學習策略,平衡局部優化和全局優化能力。對基于多個基準函數的尋優能力進行對比分析,結果表明AMDBO 相比DBO、SSA、IGWO 具有更好的求解速度和精度;山區環境中的路徑規劃結果表明AMDBO 比DBO 收斂更快,能較快地跳出局部最優,路徑質量更高。下一步研究將考慮如何提升山區多目標點的路徑規劃質量。
參考文獻
[1] 路晶,史宇,張書暢,等. 無人機航跡規劃算法綜述[J]. 航空計算技術,2022,52(4):131-134.
[2] 雷耀麟,丁文銳,李雅,等. 群體智能支撐的無人機群航路規劃應用綜述[J]. 無線電工程,2023,53 (7):1509-1519.
[3] 藺文軒,謝文俊,張鵬,等. 基于分組優化改進粒子群算法的無人機三維路徑規劃[J]. 火力與指揮控制,2023,48(1):20-25.
[4] 蘇菲. 基于改進蝙蝠算法的無人機三維路徑規劃[J].無線電工程,2022,52(12):2229-2236.
[5] 黃鶴,吳琨,王會峰,等. 基于改進飛蛾撲火算法的無人機低空突防路徑規劃[J]. 中國慣性技術學報,2021,29(2):256-263.
[6] 巫茜,黃浩,曾青,等. 改進ACO 算法的UAV 航跡規劃在山區物流配送中的應用研究[J]. 重慶理工大學學報(自然科學),2022,36(10):185-191.
[7] 郭啟程,杜曉玉,張延宇,等. 基于改進鯨魚算法的無人機三維路徑規劃[J]. 計算機科學,2021,48 (12):304-311.
[8] ZENG N Y,WANG Z D,LIU W B,et al. A Dynamic Neighborhoodbased Switching Particle Swarm Optimization Algorithm [J]. IEEE Transactions on Cybernetics,2022,52(9):9290-9301.
[9] 段建民,陳強龍. 基于改進人工勢場-遺傳算法的路徑規劃算法研究[J]. 國外電子測量技術,2019,38(3):19-24.
[10] 許諾. 基于改進PSO 算法的UAV 三維路徑規劃研究[J]. 電子測量技術,2022,45(2):78-83.
[11] 陳明強,李奇峰,馮樹娟,等. 基于改進粒子群算法的無人機三維航跡規劃[J]. 無線電工程,2023,53(2):394-400.
[12] 許樂,趙文龍. 基于新型灰狼優化算法的無人機航跡規劃[J]. 電子測量技術,2022,45(5):55-61.
[13] 趙棣宇,鄭賓,殷云華,等. 改進粒子群算法的UAV 突防路徑規劃[J]. 電光與控制,2023,30(4):12-16.
[14] XUE J K,SHEN B. Dung Beetle Optimizer:A New Meta-heuristic Algorithm for Global Optimization[J]Supercom-put,2023,79:7305-7336.
[15] 宋立業,胡朋舉. 改進SSA 在三維路徑規劃中的應用[J]. 傳感器與微系統,2022,41(3):158-160.
[16] 馮增喜,何鑫,崔巍,等. 混合隨機反向學習和高斯變異的混沌松鼠搜索算法[J]. 計算機集成制造系統,2023,29(2):604-615.
[17] 舒聰. 面向無人機航跡規劃的改進麻雀搜索算法及應用[D]. 廣州:廣州大學,2022.
[18] 歐陽城添,唐風,朱東林. 融合禁忌搜索的SSA 算法及其路徑規劃的應用[J]. 電子測量技術,2022,45(22):32-40.
作者簡介
遠翔宇 男,(1999—),碩士研究生。主要研究方向:路徑規劃、目標分配。
楊風暴 男,(1968—),博士,教授。主要研究方向:信息融合、不確定信息推理。
楊童瑤 女,(1997—),博士研究生。主要研究方向:威脅評估、意圖估計與態勢預測。