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

關(guān)鍵詞：UAVs；CGWO；GWO；TSP；路徑規(guī)劃

中圖分類號：TP18" " " "文獻標(biāo)志碼：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

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

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

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

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

1.1" 灰狼算法

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

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

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

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

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

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

。（3）

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

1.2" 灰狼算法解決TSP問題

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

1.3" 改進灰狼算法

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

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

，（4）

式中：a為收斂因子，t為當(dāng)前迭代輪次，T為迭代總次數(shù)。

2" 算法性能分析

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

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

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

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

3" 結(jié)束語

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

參考文獻：

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

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

[3] 許樂，趙文龍.基于新型灰狼優(yōu)化算法的無人機航跡規(guī)劃[J].電子測量技術(shù)，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.