基于改進(jìn)收斂因子的CGWO無人機(jī)路徑規(guī)劃

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

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

中圖分類號(hào)：TP18" " " "文獻(xiàn)標(biāo)志碼：A" " " " " 文章編號(hào)：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

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

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

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

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

1.1" 灰狼算法

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

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

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

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

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

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

。（3）

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

1.2" 灰狼算法解決TSP問題

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

1.3" 改進(jìn)灰狼算法

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

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

，（4）

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

2" 算法性能分析

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

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

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

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

3" 結(jié)束語

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

參考文獻(xiàn)：

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

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

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