基于改進收斂因子的CGWO無人機路徑規劃

摘" 要：在無人機（UAVs， Unmanned Aerial Vehicles）集群應用場景中，無人機集群間面臨簇間通信受阻的情況。常規的解決方案是利用無人機收集簇群數據，并將問題轉化為TSP（Traveling Salesman Problem）問題。該文研究無人機數據采集過程中的路徑規劃問題。在灰狼算法（GWO）的基礎上提出改進收斂因子的CGWO算法，通過改進收斂因子提高算法的全局搜索能力，使之能適用于無人機數據采集過程中的路徑規劃問題。通過MATLAB仿真實驗表明，CGWO算法相比于GWO算法具有更好的搜索性能。在進行30個采集節點的實驗中，CGWO算法相比于現有的改進GWO算法將最短距離縮短27.24%。

關鍵詞：UAVs；CGWO；GWO；TSP；路徑規劃

中圖分類號：TP18" " " "文獻標志碼：A" " " " " 文章編號：2095-2945（2023）13-0075-04

Abstract： In the cluster application scenario of UAVs （Unmanned Aerial Vehicles）， the communication between clusters may blocked. A conventional solution is to use drones to collect cluster data and transform the problem into a TSP problem. In this paper， we study the path planning problem during UAV data collection. On the basis of Grey Wolf Algorithm （GWO）， the CGWO algorithm with improved convergence factor was proposed. By improving the convergence factor， the global search capability of the algorithm is improved， making it applicable to the path planning problem in the process of UAV data acquisition. MATLAB simulation shows that CGWO algorithm has better search performance than GWO algorithm. In the experiment of 30 acquisition nodes， the CGWO algorithm reduces the shortest distance by 27.24% compared with the existing improved GWO algorithm.

Keywords： UAVs; CGWO; GWO; TSP; path planning

無人機具有尺寸小且對起降場地要求不高的特點，因此除了在軍事領域的應用外，還廣泛應用于巡邏、探測和現場救援指揮等任務中。這些應用場景的特點是通信距離較遠且通信環境相對復雜，容易面臨集群間通信受阻、無人機節點失聯等情況。因此需要制定高效的無人機數據采集策略。常見的解決方案是使用高功率的無人機進行簇群間數據采集，其次利用智能化算法對采集無人機進行路徑規劃。

經典路徑規劃算法需要提前載入環境信息。主要有模擬退火算法、模糊邏輯算法等。而智能化算法是根據實時測量的環境與節點自身位置信息計算從而進行路徑規劃。常用的有蟻群算法、遺傳算法等。區別在于智能化算法具有實時性特征，更適用于位置信息不明確或場景復雜多變的場景。

無人機集群任務場景復雜，不能提前獲取簇群節點的位置，本文采用智能化算法進行路徑規劃。提出基于改進收斂因子的CGWO算法（Convergence Grey Wolf Optimize）。通過改進灰狼優化算法（Grey Wolf Optimize）的收斂因子，提高算法的全局搜索能力。

1" 基于改進收斂因子的CGWO路徑規劃

1.1" 灰狼算法

灰狼算法是群體智能優化算法。該算法模仿灰狼的狩獵和社會等級行為，存在能夠自適應調整的收斂因子及信息反饋機制，能夠在局部尋優與全局搜索之間實現平衡。

灰狼優化算法將狼群分為4個等級，通過計算種群每個個體的適應度，將狼群中適應度最好的3匹灰狼依次標記為α、β、δ，而剩下的灰狼標記為ω。即灰狼群體中的社會等級從高往低排列依次為α、β、δ及 ω。GWO的優化過程主要由每代種群中最好的3個解（α、β、δ）來指導完成。

灰狼的狩獵過程分為3個階段，分別為包圍獵物、靠近獵物和攻擊獵物。當灰狼識別出列為位置后在α、β、δ的帶領下指導狼群包圍獵物?；依莻€體跟蹤獵物位置的數學模型描述如下

Dα＝|C1×Xα-X|Dβ=|C2×Xβ-X|Dδ=|C3×Xδ-X|，（1）

式中：Dα、Dβ和Dδ分別表示α、β、δ與其他個體間的距離；Xα、Xβ和Xδ分別代表α、β、δ當前位置；C1C2C3是隨機向量，X是當前灰狼的位置。

X1=|Xα-A1×Dα|X2=|Xβ-A2×Dβ|X3=|Xδ-A3×Dδ|。（2）

。（3）

式（2）定義了狼群中ω個體朝向α、β、δ前進的步長和方向，式（3）定義了ω的最終位置。

1.2" 灰狼算法解決TSP問題

灰狼算法具有高效并行全局搜索的能力，相比于其他遺傳算法能夠更好更快地完成最優解地搜尋。用灰狼算法解決路徑規劃問題的使用流程如下：①初始化參數為灰狼個數、迭代次數和簇頭節點位置信息等；②根據簇頭節點位置信息，計算任意2點間的距離，構建網絡圖；③初始化灰狼種群中各個灰狼的位置；④根據重新定義的公式，更新各個灰狼的當前位置及其適應值；⑤選取新的？琢狼、？茁狼、？啄狼，并更新當前迭代次數；⑥判斷是否滿足終止條件；⑦滿足終止條件則？琢狼的解即為最優路線；⑧未滿足終止條件，則重復④。

1.3" 改進灰狼算法

灰狼優化算法中收斂因子a從2線性降到0，而a影響協同系數向量A，后者決定了灰狼的位置更新步長。當|A|gt;1時，灰狼間盡量分散并在各區域并行搜索。當|A|lt;1時，灰狼將集中搜索某個或某些區域?，F有的收斂因子隨迭代次數線性下降，在TSP問題中，需要盡量避免陷入最優解，也即擴大全局搜索的能力。

本文的算法性能分析部分，對比了常見的幾種非線性函數作為收斂因子后的實驗效果。根據實驗結果可知，收斂因子為a=2×（1- ）時的改進效果較好，比較適合解決TSP問題。此類型函數的特點是在Agt;1或Alt;-1時的分布較其他函數多，也即該收斂因子的全局搜索能力較強。因此本文采用的改進收斂因子的非線性函數如下

，（4）

式中：a為收斂因子，t為當前迭代輪次，T為迭代總次數。

2" 算法性能分析

收斂因子會影響算法的全局搜索和局部搜索性能，為探索適合TSP問題的收斂因子的表達形式，現有文獻中收斂因子改進方案應用到針對TSP問題設計的實驗中，各收斂因子的表現效果如圖1—圖4所示。

上述實驗中，收斂因子為圖5時，其中的μ在不同取值下算法的性能表現有些許差異。μ=0.1時，最優值為628.407 7；μ=0.5時，最優值為519.237 6；μ=0.9時，最優值為561.004 9。并且該方案在反復迭代后表現較好。

通過對不同收斂因子下的實驗效果對比，可以看到其中表現最優的是如圖6所示的收斂因子為a=2×（1- ）時，函數的特點是利用A=2a×r1-a計算得到的A，在Agt;1或Alt;-1時的分布較其他函數多，即該收斂因子的全局搜索能力較強，比較適合解決TSP問題。因此針對該函數的特點設計出新的收斂因子的表達式為a=2- ，實驗效果如圖5—圖7所示。

圖7為改進收斂因子后的實驗效果，該函數表達式吸收了收斂因子為a=2×（1- ）時，產生的全局搜索效果較好的優點，同時在此基礎上進行增強。實驗表明改進后的收斂因子比當前最優效果取得了更好的表現，詳見表1。

3" 結束語

本文主要研究利用智能算法解決無人機數據收集過程中的路徑規劃問題。通過分析GWO算法的性能，提出通過改進收斂因子來優化GWO算法在TSP問題中的表現。通過對比現有文獻中常規的收斂因子設置方案，得出適合TSP解決問題的收斂因子的函數形式。改進后的收斂因子為a=2 ，最優值為455.427 5，相比于收斂因子為a=2×e 最優值為625.957 3，將實驗結果提高了27.24%。

參考文獻：

[1] SM A，SM B，AL A.Grey Wolf Optimizer[J].Advances in Engineering Software，2014（69）：46-61.

[2] 張陽，周溪召.求解全局優化問題的改進灰狼算法[J].上海理工大學學報， 2021，43（1）：73-82.

[3] 許樂，趙文龍.基于新型灰狼優化算法的無人機航跡規劃[J].電子測量技術，2022，45（5）：55-61.

[4] LONG W， LIANG X， CAI S， et al. A modified augmented Lagrangian with improved grey wolf optimization to constrained optimization problems[J].Neural Computing amp;amp; Applications， 2016，28（S1）：1-18.