基于改進金豺算法的無人機三維航跡規劃

摘" 要： 針對傳統金豺優化算法（GJO）在求解無人機航跡規劃時存在的穩定性差、尋優能力不足等問題，提出一種改進金豺優化算法（IGJO）。首先使用改進Tent混沌映射初始化種群；然后結合北方蒼鷹優化算法思想，開發一種新型探索階段位置更新方式；其次，采用動態能量因子策略來轉換能量遞減方式；最后，提出一種用于平衡探索和開發的閾值雙重自適應t分布擾動變異策略，完成對GJO算法的改進。另外，建立一個無人機三維航跡規劃模型，并利用IGJO算法求解以航程代價、高度代價等為目標函數的無人機三維航跡規劃問題。結果表明，IGJO算法可適用于不同的復雜地形環境，且規劃的航跡具有最優的成本代價。

關鍵詞： 無人機； 航跡規劃； 金豺優化算法； 改進Tent混沌映射； 動態能量因子； 自適應t分布

中圖分類號： TN919?34； V249.1； TP301" " " " " " " "文獻標識碼： A" " " " " " " "文章編號： 1004?373X（2024）16?0103?07

UAV 3D path planning based on improved golden jackal algorithm

WANG Yinuo1， ZHENG Huanqi2， 3， YANG Shengkun3， ZHOU Yucheng2

（1. School of Information and Electrical Engineering， Shandong Jianzhu University， Jinan 250101， China;

2. School of Architecture and Urban Planning， Shandong Jianzhu University， Jinan 250101， China;

3. National Inspection and Testing Center for Decorative Building Material， Jinan 250102， China）

Abstract： In allusion to the poor stability and inadequate optimization capability of the traditional golden jackal optimization （GJO） algorithm in solving unmanned aerial vehicle （UAV） trajectory planning， an improved golden jackal optimization （IGJO） algorithm is proposed. An improved Tent chaotic mapping is used to initialize the population. Then， integrating the concept of the northern goshawk optimization algorithm， a new exploration phase position updating method is developed. A dynamic energy factor strategy is employed to transform the energy decay mode. A dual?threshold adaptive t?distribution perturbation strategy for balancing exploration and development is proposed to improve the GJO algorithm. A UAV 3D （three?dimensional） path planning model is established， and the IGJO algorithm is utilized to improve UAV 3D path planning with objective functions such as flight distance cost and altitude cost. The results show that the IGJO algorithm can be used to different complex terrain environments， and the planned flight path has the optimal cost.

Keywords： unmanned aerial vehicle; path planning; golden jackal optimization algorithm; improved Tent chaotic mapping; dynamic energy factor; adaptive t?distribution

0" 引" 言

近年來，無人機制造業快速發展，無人機憑借其成本較低、體積較小等優點被廣泛應用于民用及軍事領域[1]。而規劃一條耗能低、距離短的最優航跡是無人機完成各項任務的前提。

傳統路徑規劃算法例如A*算法、Dijsktra算法和隨機樹算法等求解速度過慢[2]，無法同時進行軌跡生成和問題尋優，因此無法解決具有更高精度要求和更強靈活性的路徑規劃問題。群智能優化算法憑借其優異的啟發式搜索能力被越來越多地應用于求解路徑規劃問題上。文獻[3]中使用透鏡成像對立學習等多種最優解更新方式來改進金槍魚優化算法，解決了無人機航跡規劃問題；但改進后的算法仍然存在尋優速度和實時性表現不足的缺陷。文獻[4]提出基于精英保留等策略的改進蜉蝣算法（CMA）來求解航跡規劃問題，獲得較優的航跡解；但CMA算法在若干次實驗中相比原始算法的尋優能力無明顯優勢。文獻[5]將改進灰狼算法應用于求解靜態二維無人機最優路徑的問題；然而，其改進策略在一些測試函數上仍無法尋得理論最優值，在算法能力提升方面還有改進的空間。文獻[6]引入柯西變異和自適應權值等策略來增加哈里斯鷹算法的種群多樣性和尋優能力，有效提升了哈里斯鷹算法求解最優路徑的性能；但其只與原始優化算法進行對比實驗，算法驗證不充分。文獻[7]提出融合改進人工勢場的蟻群算法，有效提升了算法尋優性能；但其在算法中引入的預搜索和信息素濃度更改策略，增加了算法的時間復雜度。

以上群智能優化算法通過不同改進策略對特定情境下的路徑規劃有一定的可行性，但依然存在尋優穩定性差、收斂精度不足等問題。金豺優化（GJO）算法是一種新型元啟發式優化算法[8]，其模型簡單、影響參數少、易實現，適用于解決大多工程應用問題。但GJO算法同其他原始優化算法一樣，均存在搜索能力不足和易陷入局部最優的局限性。因此，文獻[9]提出融合粒子群的改進金豺算法，將其應用于無人機路徑規劃，驗證了其有效性。文獻[10]采用柯西變異等策略改進了金豺優化算法，但在多種測試函數上并沒有展現出其較強的優越性。文獻[11]提出一種基于精英反向學習技術和單純從技術增強全局尋優能力的改進GJO算法，但算法的有效性還需進一步驗證。文獻[12]在GJO算法的基礎上引入快速隨機對立學習策略，提升了算法的勘探和開發能力，但尋優穩定性沒有獲得明顯的改進。上述改進策略雖然一定程度上提高了GJO算法的性能，但部分改進GJO算法并沒有很好地解決GJO算法的不足。

為此，本文提出一種混合策略改進的金豺優化算法（IGJO）。首先，使用改進Tent映射進行種群初始化，提高初始解質量；然后為GJO算法勘探階段提供一種新的基于北方蒼鷹算法的位置更新公式，增加全局搜索能力和種群多樣性；其次，采用動態能量因子策略轉換能量遞減方式，避免算法落入局部最優解；最后，提出一種閾值雙重自適應t分布變異策略來平衡算法的全局搜索與局部搜索，從而提高算法的收斂精度。將IGJO算法應用到三維無人機航跡規劃中，實驗結果驗證了其具備較強的航跡規劃求解性能和求解穩定性。

1" 金豺優化算法

GJO算法是模擬金豺協同狩獵行為發展而來的一種元啟發式算法，算法分為初始化、探索和進攻三個階段。

GJO算法采用隨機的方式初始化種群，公式如下：

[Y0=Ymin+rand（Ymax-Ymin）] （1）

式中：[Ymin]和[Ymax]表示尋優空間的下限和上限；[rand]表示[0，1]中的均勻分布隨機值。

探索階段：初始化后，根據適應度值排名選取最優解和次優解分別作為雄金豺和雌金豺，探索階段金豺會根據自身情況進行狩獵，即雌金豺會跟隨雄金豺，在搜索區域等待和尋找其他獵物。此情況下的計算公式如下：

[Y1（t）=YM（t）-YM（t）-rL·prey（t）] （2）

[Y2（t）=YFM（t）-YFM（t）-rL·prey（t）] （3）

式中：[t]表示當前迭代次數；[prey（t）]表示獵物位置向量；[YM（t）]和[YFM（t）]分別表示雄金豺和雌金豺的位置；[Y1（t）]和[Y2（t）]分別為雄金豺和雌金豺相對于獵物更新后的位置；[rL]表示采用Levy分布的隨機向量。[E]為獵物的逃避能量，其計算公式如下：

[E=E1-E0] （4）

[E0=2r-1] （5）

[E1=C1-（1-tT）] （6）

式中：[E1]表示從1.5遞減到0的獵物逃避能量；[E0]是初始逃跑能量；[C1]是數值為1.5的常數；[r]表示[0，1]的隨機數。最后采用如下公式更新金豺位置。

[Y（t+1）=Y1（t）+Y2（t）2] （7）

進攻階段：圍捕獵物階段在迭代過程中，獵物逃避能量[E]下降。金豺攻擊獵物后開始圍捕獵物。這種雄雌金豺共同狩獵行為的數學建模如下：

[Y1（t）=YM（t）-E·rL·YM（t）-prey（t）] （8）

[Y2（t）=YFM（t）-E·rL·YFM（t）-prey（t）] （9）

最后，根據公式（7）更新金豺位置。

2" IGJO算法設計

2.1" 改進Tent混沌映射種群初始化

GJO算法通過隨機生成的方法構建初始種群，會出現劣質解，從而導致收斂速度降低。而Tent混沌映射具有較好的隨機性，且結構相比其他映射更為簡單。但Tent映射存在小周期和不穩周期點，其數學公式為：

[xi+1=2xi，" " " " " " " " " "0≤x≤122（1-xi），" " " "12lt;x≤1] （10）

為了避免出現上述問題，在原有的Tent映射中加入一種隨機變量[13]，改進后的Tent映射可表示為：

[xi+1=2xi+rand（0，1）·1N，" " " " " " " " 0≤x≤122（1-xi）+rand（0，1）·1N，" " 12lt;x≤1] （11）

式中[N]是種群的大小。隨機變量的引入既增加了Tent混沌的可控隨機性，又保證了Tent映射的規律性。為驗證改進Tent映射的優越性，采用改進Tent映射、Tent映射、Logistic映射和Circle映射分別進行種群初始化。四種混沌映射頻數分布直方圖如圖1所示。

從圖1可以看出，改進Tent混沌映射在四種映射中的混沌值分布最為均勻。因此，利用改進Tent混沌映射代替隨機生成方法進行高質量種群初始化。

2.2" 融合北方蒼鷹算法的改進探索策略

在每次迭代的初始階段，雄性豺狼個體通常迅速收斂于全局最優解決方案，以實現較強的搜索能力。然而，通過這種方式獲取全局最優解常常忽略了對附近搜索空間的探索，導致在探索階段的搜索空間嚴重不足，并易陷入局部最優解。相比之下，北方蒼鷹算法的更新策略是通過隨機選擇獵物來實現的[14]，并且金豺尋優過程為：當前種群最優解雄金豺引領次優解雌金豺共同進行搜索尋優，因此利用北方蒼鷹的更新策略替代探索階段雄性金豺位置更新公式，可有效增強GJO算法的全局探索能力。

新的雄金豺探索階段位置更新公式如下：

[Y1（t）=YM（t）-r（P-I?YM（t）），" FPlt;FYM（t）-r（YM（t）-P），" " " " FP≥F] （12）

式中：[P]為雄金豺隨機選擇獵物的位置；[F]為雄金豺的函數值；[FP]為目標函數值；[I]為1或2。

2.3" 動態能量因子策略

逃避能量控制算法在迭代過程中由全局搜索到局部搜索，當逃避能量[E≥1]時，算法進行全局搜索；當逃避能量[Elt;1]時，算法進行局部搜索。原始GJO算法[E1]線性遞減，不能滿足復雜問題的非線性尋優過程。為此，本文提出一種動態能量因子策略，具體公式如下：

[E11=C11-11+exp-ktTmax-0.5] （13）

式中：[t]為當前迭代次數；[Tmax]為最大迭代次數。經過實驗，[k]取值為12時，策略效果最佳。

為了驗證本文提出的動態能量因子策略的優勢，列舉一種常見的非線性收斂策略，公式如下：

[E12=C11-tTmaxa] （14）

式中[a]是值為4的常數。

三種逃避能量策略的仿真曲線如圖2所示。與[E1]、[E12]相比，在迭代前期，[E11]以慢速下降的方式得到較大的探索步長，幫助種群在尋優空間內廣泛搜索，進而增強其跳出局部最優的能力。在迭代后期，[E11]迅速衰減至較小的值，使得算法進行精細的局部搜索，有利于加速種群收斂。

因此，本文提出的動態能量因子策略可以更好地應用于非線性復雜優化問題的求解。獵物的逃避能量[E]公式更新為：

[E=E11-E0] （15）

2.4" 閾值雙重自適應t分布變異策略

[t]分布又稱學生分布，含有自由度參數[15]，其概率密度函數表達式如下：

[p（x）=Γm+12m?πΓm21+x22-m+12] （16）

本文選用一種自適應迭代次數[tn]充當[t]分布的自由度參數，如式（17）所示，使得[t]分布在算法迭代前期較長時間內趨近于柯西分布，算法的全局搜索能力將獲得增強；在迭代后期，[tn]數值攀升使得[t]分布快速趨近于高斯分布，從而增強算法的局部搜索水平。這種雙重自適應[t]分布可有效平衡探索和開發，進而增強算法的收斂精度。

[tn=exp4?tTmax2] （17）

雙重自適應[t]分布隨機干擾項的增加雖然可以提高算法性能，但是對每個個體均引入變異算子，會阻礙算法本身的優勢，增加迭代時間。為此，設定閾值[r]來調節變異算子的使用頻率。最終的金豺位置更新公式如下：

[Ynew=Y（t+1），" " " " " " " " " " " " " " " " " " "rlt;0.5Y（t+1）+Y（t+1）?t（tn），" r≥0.5] （18）

式中[r]表示[0，1]的隨機數。

2.5" IGJO算法尋優

步驟1：設置最大迭代次數[Tmax]、種群數量[N]等初始參數，使用改進Tent混沌映射來初始化種群。

步驟2：計算初始適應度值，最優值為雄金豺，次優值為雌金豺。

步驟3：利用公式（15）計算逃避能量[E]。

步驟4：如果[E≥1]，則進入探索階段，利用式（12）、式（3）更新雄、雌金豺位置；反之進入進攻階段，利用式（8）、式（9）更新雄、雌金豺位置。

步驟5：根據添加閾值雙重自適應[t]分布變異策略的公式（18）更新最優個體位置。

步驟6：更新迭代次數，判斷是否達到最大迭代次數[Tmax]，若未達到，則返回步驟2；反之，輸出最優解。

IGJO算法尋優流程如圖3所示。

3" 航跡規劃問題三維建模

3.1" 三維地理環境建模

無人機三維航跡規劃是基于實際三維地形環境對航跡做出規劃的一種問題。本文利用柵格法模擬城市和丘陵兩種無人機飛行環境地形，并生成三維地圖模型，如圖4所示。

3.2" 約束條件

3.2.1" 飛行高度

在執行建筑勘探任務時，需考慮安全性以及相關空域規定，因此需要對無人機的飛行高度進行限制。設定最大、最小飛行高度分別為[hmax]和[hmin]，飛行高度應滿足如下公式：

[hmin≤h≤hmax] （19）

3.2.2" 俯仰角度約束

俯仰角度是速度方向與當前航跡點水平面的夾角，為了無人機可以正常起飛，需要設置最大俯仰角度為[γmax]。航跡規劃過程中的飛行角度應滿足[-γmax≤γ≤γmax]，飛行角度計算公式如下：

[ze-ze-1（xe-xe-1）2+（ye-ye-1）2≤tanγ， e=2，3，…，n] （20）

3.2.3" 轉彎角度約束

無人機在執行任務時水平方向會發生改變，其水平方向轉彎角度應使得航跡盡可能地平滑，且不能超過無人機本身允許的最大轉彎角度[βmax]。轉彎角度公式如下：

[βi=arccosf1f2≤βmax] （21）

[f1=（xe-xe-1）（xe+1-xe）+（ye-ye-1）（ye+1-ye）] （22）

[f2=（xe-xe-1）2+（ye-ye-1）2·（xe+1-xe）2+（ye+1-ye）2] （23）

式中：[（xe，ye，ze）]和[（xe+1，ye+1，ze+1）]分別表示無人機飛行航跡中的第[e]和第[e+1]個航跡節點。

3.3" 目標函數

3.3.1" 航程代價

無人機在執行任務過程中，由于存儲的能量有限，使得最大航程有所限制。航程代價函數[g1]可表示為：

[g1=e=1Slele+1] （24）

式中：[lele+1]表示第[e]個飛行節點和第[e+1]個飛行節點之間的距離；[S]表示總飛行節點數。

3.3.2" 威脅代價

無人機作業過程中需要躲避可能存在的障礙物，以避免造成對無人機的損壞，因此規定無人機需繞過此障礙。威脅代價函數[g2]定義為：

[g2=e=1Nde] （25）

式中[de]是第[e]個飛行節點的危險度。

3.3.3" 無人機高度代價

無人機的飛行高度低于規劃區域或者高于規劃區域時，可能產生無法預估的影響。因此，本文將高度代價函數[g3]定義為：

[g3=p1（hmin-h），" " hlt;hmin0，" " " " " " " " " " " " "hmin≤h≤hmaxp2（h-hmax），" " hgt;hmax] （26）

式中：[p1]和[p2]為比例系數。

綜上，三維無人機航跡規劃的目標函數可定義為：

[minG=δ1g1+δ2g2+δ3g3δ1+δ2+δ3=1] （27）

式中：[G]為總的目標函數；[δ1]、[δ2]和[δ3]表示目標權重系數。

4" 實驗分析

4.1" 實驗環境配置

為了驗證IGJO算法的有效性，進行Matlab環境下的無人機航跡規劃仿真建模。本文建立了兩種仿真環境：一種為環境中存在長方體障礙物、地形較為平整的城市地形A；另一種為添加圓柱體障礙物，且地形為崎嶇不平的丘陵地形B。

4.2" 三維航跡規劃測試

選擇標準GJO、混合策略改進的鯨魚優化算法（MSWOA）[16]、改進灰狼算法（IGWO）[17]和其他改進金豺算法（GJOA）[10]作為IGJO的對比算法進行航跡規劃仿真實驗。在城市環境A和丘陵環境B分別進行獨立實驗30次，種群規模[N]=30，最大迭代次數[Tmax]=60，記錄5種算法的適應度值。圖5和圖6為城市地形A和丘陵地形B中5種算法的航跡規劃解和航跡規劃適應度值。

根據圖5a）顯示，在給定城市環境A模型中，IGJO算法展現出最短的航跡長度和較少的轉彎次數，生成的航跡更加平滑；但也出現尋優失敗的現象，表明其在實際復雜工程應用中搜索精度有待提高。其余算法雖然能夠有效求解航跡規劃，但存在非必要的多次轉彎，無法獲得最優解。

結合適應度值圖5b）可知，IGJO算法憑借其優秀的尋優能力能夠最快地收斂至全局最優解，而其他4種算法則在不同程度上陷入局部最優解，導致航跡適應度值過高。IGJO算法在迭代初期的規劃代價明顯小于對比算法，驗證了其初始種群質量更優，進化至最優解的速度更快，能夠在適應度更優的個體間進行尋優進化，從而更高效地找到最優解。

圖6a）中，在給定的丘陵環境B模型中，5種算法都能生成一條安全、可行的飛行航跡。IGJO算法仍然可以搜索到航跡規劃最優解，其規劃的航跡長度最短且航跡俯仰角度更小，能有效避開禁飛區等威脅區域。而其余4種的規劃航跡均存在一定程度的方向偏離，飛行線路較長，且航跡存在明顯的大幅轉彎。

圖6b）為丘陵環境B下各算法求解的適應度值，IGWO和GJOA算法收斂速度要略快于IGJO和GJO，但在收斂精度方面，IGJO遠遠高于其他算法。可見IGJO具備不斷跳出局部最優解的能力，且在不同改進策略的影響下能持續探索尋優空間，從而能夠快速逼近全局最優解的鄰域，進而獲得最優解。統計結果如表1所示。

由表1可以看出，IGJO算法在兩種地形中均取得了最優的結果，相較于GJO算法、MSWOA算法、IGWO算法和GJOA算法，其最優適應度在城市地形A中分別降低了36.65%、32.29%、57.94%和10.8%，在丘陵地形B中分別降低了12.85%、4.62%、6.79%和4.21%。結合平均適應度值來看，在不同的地形中IGJO算法具有出色的解決復雜問題的能力；且在兩種地形中IGJO算法適應度標準差最小，即在改進策略的牽引下，該算法能夠更好地平衡全局搜索和局部開發，具有穩定的尋優能力。

5" 結" 語

為提高無人機三維航跡規劃的求解精度，解決航跡代價高的問題，本文設計了一種改進的金豺優化算法。該算法首先利用改進Tent映射來提升初始解質量；然后設計了一種融合北方蒼鷹算法的勘探策略，增強其全局尋優精度；最后引入動態能量因子和閾值雙重自適應t分布變異策略來增加算法搜索精度和加快收斂速度，防止航跡陷入局部最優解，甚至落入危險區域。實驗部分是利用IGJO算法來求解兩種具有地貌約束和性能約束威脅模型的航跡規劃問題。結果證明，IGJO算法能夠穩定地跳離局部最優，搜索到一條代價小且安全的航跡。

注：本文通訊作者為鄭煥祺。

參考文獻

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

[2] 孫曦，劉峰，薛曉.基于透鏡成像對立學習TSO算法的無人機三維航跡規劃[J/OL].電光與控制：1?9[2023?09?26].http：//kns.cnki. net/kcms/detail/41.1227.TN.20230925.0954.002.html.

[3] 謝繼武，席建新.瞬態搜索金槍魚優化城市物流無人機路徑規劃[J].計算機工程與設計，2023，44（12）：3745?3753.

[4] 席萬強，常保帥，林思偉，等.多策略改進蜉蝣算法的無人機航跡規劃[J].電光與控制，2023，30（11）：80?84.

[5] 劉云平，朱慧如，方衛華.改進灰狼算法的無人機路徑規劃[J].電光與控制，2023，30（7）：1?7.

[6] ZHANG R， LI S， DING Y， et al. UAV path planning algorithm based on improved Harris hawks optimization [J]. Sensors， 2022， 22（14）： 5232.

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

[8] CHOPRA N， ANSARI M M. Golden jackal optimization： a novel nature?inspired optimizer for engineering applications [J]. Expert systems with applications， 2022， 198： 116924.

[9] 回立川，曹明遠，遲一璇.融合粒子群的改進金豺算法及應用[J].計算機集成制造系統，2024，30（5）：1733?1744.

[10] 朱興淋，汪廷華，賴志勇.混合策略改進的金豺優化算法[J].計算機工程與應用，2024，60（4）：99?112.

[11] ZHANG J， ZHANG G， KONG M， et al. Adaptive infinite impulse response system identification using an enhanced golden jackal optimization [J]. The journal of supercomputing， 2023（2）： 1?26.

[12] MOHAPATRA S， MOHAPATRA P. Fast random opposition?based learning golden jackal optimization algorithm [J]. Knowledge?based systems， 2023， 275： 110679.

[13] 毛清華，王迎港，牛曉輝.基于反吸引速度更新機制的改進蜉蝣算法[J/OL].北京航空航天大學學報：1?16[2022?09?16].https：//doi.org/10.13700/j.bh.1001?5965.2022.0550.

[14] 王士彬，李多，趙娜，等.基于改進北方蒼鷹算法優化混合核極限學習機的變壓器故障診斷方法[J].湖南電力，2023，43（4）：125?132.

[15] 劉凱，吉衛喜.改進SHO求解自動化立體倉庫能耗優化調度問題[J/OL].計算機工程與應用：1?11[2023?08?14].http：//kns.cnki.net/ kcms/detail/11.2127.TP.20230814.1025.002.html.

[16] 郝曉弘，宋吉祥，周強，等.混合策略改進的鯨魚優化算法[J].計算機應用研究，2020，37（12）：3622?3626.

[17] 丁瑞成，周玉成.引入萊維飛行與動態權重的改進灰狼算法[J].計算機工程與應用，2022，58（23）：74?82.