基于多策略改進(jìn)灰狼算法的多無人機(jī)三維路徑規(guī)劃
2024-02-22 00:00:00許子俍胡濤劉凱越安樂寧楊思為
航空兵器 2024年6期
摘 要：""""" 多無人機(jī)三維路徑規(guī)劃旨在滿足約束且規(guī)避威脅的基礎(chǔ)上給出各個(gè)無人機(jī)到自身目標(biāo)合理可行的飛行路徑。 針對當(dāng)前元啟發(fā)式算法在求解多約束、 多威脅三維空間路徑規(guī)劃時(shí)搜索速度慢、 規(guī)劃路徑質(zhì)量差的問題， 提出一種基于多策略改進(jìn)灰狼優(yōu)化算法的路徑規(guī)劃方法。 使用數(shù)字高程模型完成三維空間環(huán)境建模， 結(jié)合飛行場景建立包含長度、 威脅、 高度、 平滑多因素綜合評價(jià)函數(shù)。 通過復(fù)合混沌序列和準(zhǔn)反向?qū)W習(xí)策略優(yōu)化初始種群， 基于迭代階段上層狼對種群收斂的關(guān)鍵影響， 使用精英狼凸透鏡反射學(xué)習(xí)策略提升算法規(guī)避局部最優(yōu)解能力。 仿真實(shí)驗(yàn)表明， 多策略改進(jìn)灰狼優(yōu)化算法綜合評價(jià)函數(shù)統(tǒng)計(jì)結(jié)果的最優(yōu)值、 平均值、 最差值三項(xiàng)指標(biāo)相較原算法分別提升了6.1%， 5.1%和13.3%， 驗(yàn)證了本文方法在多約束、 多威脅的三維空間路徑規(guī)劃問題求解時(shí)的有效性。
關(guān)鍵詞："""" 多無人機(jī)； 三維路徑規(guī)劃； 灰狼優(yōu)化算法； 復(fù)合混沌序列； 準(zhǔn)反向?qū)W習(xí)； 精英狼凸透鏡反射學(xué)習(xí)
中圖分類號：nbsp;""""" TJ760
文獻(xiàn)標(biāo)識碼：""" A
文章編號："""" 1673-5048（2024）06-0086-08
DOI： 10.12132/ISSN.1673-5048.2024.0080
0 引" 言
伴隨科技快速進(jìn)步， 無人機(jī)（Unmanned Aerial Vehicle， UAV）憑借其在復(fù)雜和危險(xiǎn)環(huán)境中的工作能力而在軍事領(lǐng)域備受關(guān)注。 多無人機(jī)路徑規(guī)劃是多無人機(jī)任務(wù)規(guī)劃系統(tǒng)的重點(diǎn)環(huán)節(jié)之一， 其目的是當(dāng)多無人機(jī)在三維空間中飛行時(shí)， 可以在滿足相應(yīng)約束條件及不與障礙物碰撞的前提下， 以盡可能小的成本代價(jià)為每架無人機(jī)找到一條飛往各自目標(biāo)的最優(yōu)路徑［1］。
當(dāng)前， 三維路徑規(guī)劃方法已取得許多研究成果， 傳統(tǒng)路徑規(guī)劃方法有A*算法［2］、 快速探索隨機(jī)樹算法［3］、 人工勢場法［4］、 Dijkstra算法［5］等， 該類方法由于需要大量計(jì)算時(shí)間和資源， 對于地形變化較多、 障礙類型多樣的戰(zhàn)場環(huán)境而言大多難以適用。 元啟發(fā)式算法是仿照自然行為的群智能算法， 具有計(jì)算速度快、 計(jì)算邏輯簡單、 算法靈活性強(qiáng)的特點(diǎn)， 正被越來越多地應(yīng)用于解決復(fù)雜空間中的多無人機(jī)三維路徑規(guī)劃問題。 典型元啟發(fā)式算法有粒子群算法［6］（Particle Swarm Optimization， PSO）、 蟻群算法［7］（Ant Colony Optimization， ACO）、 遺傳算法［8］（Genetic Algorithm， GA）、 麻雀算法［9］（Sparrow Search Algorithm， SSA）等。 例如， Shao等［10］提出一種改進(jìn)PSO的多無人機(jī)三維路徑規(guī)劃方法， 通過引入Logistic混沌映射和自適應(yīng)線性變化系數(shù)提升算法性能， 實(shí)驗(yàn)表明， 該方法不僅加快了收斂速度， 同時(shí)提高了解的最優(yōu)性。 Ali等［11］將ACO與差分進(jìn)化算法融合， 提出一種適用于山脈環(huán)境多機(jī)協(xié)同路徑規(guī)劃的最大最小蟻群算法， 結(jié)果表明算法魯棒性及跳出局部最優(yōu)能力得到提升。 鄧灝等［12］通過引入貪婪算子、 策略選擇閾值方式動(dòng)態(tài)調(diào)整變異概率， 提出一種基于改進(jìn)GA的多無人機(jī)搜索路徑規(guī)劃方法。 王玲玲等［13］提出一種基于改進(jìn)SSA的實(shí)時(shí)路徑規(guī)劃方法， 通過分別優(yōu)化初始種群分布和迭代過程提升了算法的收斂精度和速度。
上述研究表明元啟發(fā)式算法在解決多無人機(jī)路徑規(guī)劃問題具有很大的應(yīng)用潛力和改進(jìn)空間。 灰狼優(yōu)化算法［14］（Grey Wolf Optimization， GWO）是由Mirjalili等于2014年提出的一種仿照自然界中灰狼群捕獵行為的元啟發(fā)式算法。 相較于其他啟發(fā)式算法， GWO具有結(jié)構(gòu)簡單、 參數(shù)較少、 易于實(shí)現(xiàn)的優(yōu)點(diǎn)， 目前已被應(yīng)用于解決頻譜感知［15］、 工程設(shè)計(jì)［16］、 疾病診斷［17］等多類問題。 然而， 標(biāo)準(zhǔn)GWO在求解多約束、 多威脅三維空間路徑規(guī)劃時(shí)存在搜索速度慢、 易陷入局部最優(yōu)解、 規(guī)劃路徑質(zhì)量差的不足。 為此， 在使用數(shù)字高程模型（Digital Elevation Model， DEM）建模及構(gòu)建多目標(biāo)評價(jià)函數(shù)的基礎(chǔ)上， 本文在標(biāo)準(zhǔn)GWO中引入復(fù)合混沌序列、 準(zhǔn)反向?qū)W習(xí)和精英狼凸透鏡反射學(xué)習(xí)策略， 提出一種多策略改進(jìn)灰狼優(yōu)化算法（Multi-Strategy Improved Gray Wolf Optimization， MSIGWO）。 同時(shí)， 將MSIGWO與多種元啟發(fā)式算法進(jìn)行對比實(shí)驗(yàn)， 結(jié)果表明所提算法能夠得到更優(yōu)的UAV飛行路徑規(guī)劃。
1 三維路徑規(guī)劃模型
1.1 問題描述
本文考慮戰(zhàn)場環(huán)境下， 多UAV協(xié)同執(zhí)行多個(gè)地面目標(biāo)的路徑規(guī)劃問題， 設(shè)定各UAV在任務(wù)分配完畢后從指定基地起飛， 穿過戰(zhàn)場中心區(qū)域前往敵方陣地目標(biāo)點(diǎn)完成各自任務(wù)， 任務(wù)區(qū)域內(nèi)存在多處威脅源和山峰組成的禁飛區(qū)域， 考慮UAV為躲避威脅源和隨地形起伏的飛行高度變化。
使用DEM完成三維空間環(huán)境建模， 該模型由原始數(shù)字地形模型和等效威脅地形模型組成。 原始數(shù)字地形模型如下：
h1（x， y）=sin（y+a）+b·sinx+
c·cos（d·x2+y2）+e·cosy+
f·sin（g·x2+y2） （1）
式中： x， y為水平面的投影坐標(biāo)， h1（x， y）表示對應(yīng)水平面投影坐標(biāo)的高度； a， b， c， d， e， f， g為系數(shù)， 通過調(diào)節(jié)系數(shù)值可以改變地形。
威脅地形等效模型如下：
h2（x， y）=∑ki=1h（i）·exp－x－xoixsi2－y－yoiysi2（2）
式中： x， y為水平面的投影坐標(biāo)， h2（x， y）為x， y對應(yīng)的山峰高度； h（i）表示山峰i的最高點(diǎn)高度； xoi， yoi為山峰i最高點(diǎn)對應(yīng)的水平面投影坐標(biāo)； xsi， ysi表示山峰i沿x軸和y軸坡度相關(guān)的變量， 當(dāng)高度確定時(shí)， xsi， ysi越小則山峰越陡峭。
將上面兩種地形結(jié)合， 即可構(gòu)建一個(gè)路徑規(guī)劃的基礎(chǔ)三維空間模型：
h（x， y）=max（h1（x， y）， h2（x， y））（3）
為合理簡化問題， 聚焦研究目標(biāo)， 在三維空間環(huán)境建模中將UAV等效為一個(gè)質(zhì)點(diǎn)。 對于一條已規(guī)劃的路徑， UAV從起點(diǎn)開始經(jīng)一系列路徑點(diǎn)后到達(dá)目標(biāo)， Lkij={xkij， ykij， zkij}表示無人機(jī)Vi執(zhí)行目標(biāo)Tj的路徑點(diǎn)集合中的第k個(gè)路徑點(diǎn)的坐標(biāo)。
1.2 約束條件及評價(jià)函數(shù)
為有效評判路徑規(guī)劃結(jié)果優(yōu)劣， 考慮UAV三維空間實(shí)際飛行場景和相關(guān)約束條件， 本文三維路徑規(guī)劃評價(jià)函數(shù)由四部分組成： 路徑長度代價(jià)、 路徑威脅代價(jià)、 路徑高度代價(jià)、 路徑平滑代價(jià)。
（1） 路徑長度代價(jià)。 經(jīng)過路徑規(guī)劃得到的UAV路徑距離越短， 反映出UAV燃料消耗和飛行時(shí)長越少， 因此將UAV路徑距離作為評價(jià)函數(shù)指標(biāo)之一， 表示為
F1（Pathij）=∑n-1k=1LkijLk + 1ij（4）
式中： LkijLk+1ij表示無人機(jī)Vi執(zhí)行目標(biāo)Tj中第k個(gè)路徑點(diǎn)和第k+1個(gè)路徑點(diǎn)間的歐氏距離； n表示無人機(jī)Vi執(zhí)行目標(biāo)Tj的路徑點(diǎn)總數(shù)。
（2） 路徑威脅代價(jià)。 考慮到實(shí)際飛行過程中， UAV因控制精度、 定位誤差等因素導(dǎo)致實(shí)際路徑與規(guī)劃路徑間存在一定偏差， 因此規(guī)劃出的路徑不僅要避開障礙物和威脅源， 還應(yīng)留有適當(dāng)強(qiáng)制安全冗余距離。 如圖1所示， Om為第m個(gè)威脅源的中心點(diǎn)； Rm為對應(yīng)的威脅半徑； Z為強(qiáng)制安全冗余距離； E為脫離威脅距離； Dk+1k為路徑LkijLk+1ij到威脅源的距離。 當(dāng)UAV位于威脅源的威脅半徑或強(qiáng)制安全冗余距離內(nèi)時(shí)， 即視為損毀； 當(dāng)UAV介于強(qiáng)制安全冗余距離之外和脫離威脅距離之內(nèi)時(shí)， 設(shè)定威脅代價(jià)與Dk+1k負(fù)相關(guān)； 當(dāng)UAV位于脫離威脅距離之外時(shí)， 視為無威脅代價(jià)。 路徑威脅代價(jià)表示如下：
F2（Pathij）=∑n－1k=1∑Mm=1Bk（LkijLk+1ij）（5）
Bk（LkijLk+1ij）=0， Dk+1kgt;Rm+Z+ERm+Z+E－Dk+1k， Zlt;Dk+1k－Rm≤Z+E∞， Dk+1k≤Rm+Z（6）
式中： Bk（LkijLk+1ij）表示第k個(gè)路徑點(diǎn)和第k+1個(gè)路徑點(diǎn)間的威脅代價(jià)； M為任務(wù)區(qū)域內(nèi)的威脅源總數(shù)。
（3） 路徑高度代價(jià)。 在作戰(zhàn)任務(wù)過程中， UAV飛行高度通常被限制在一定范圍之內(nèi)， 例如偵察任務(wù)中UAV不應(yīng)超過相機(jī)指定分辨率最大高度， 同時(shí)， 為躲避地面輕武器并避免隨地形反復(fù)調(diào)整飛行高度， UAV不應(yīng)低于設(shè)定最低高度。 如圖2所示， Hmax和Hmin分別為最大高度和最低高度， 則路徑高度代價(jià)如下：
F3Pathij=Hij－（Hmax+Hmin）2， Hmin≤Hij≤Hmax∞， else" （7）
（4） 路徑平滑代價(jià)。 由于UAV轉(zhuǎn)向和爬升時(shí)會(huì)增加機(jī)體控制難度、 加速油量消耗， 因此路徑規(guī)劃傾向于同
等情況下讓UAV飛行軌跡保持平穩(wěn)。 設(shè)定路徑平滑代價(jià)包括轉(zhuǎn)向代價(jià)和爬升代價(jià)， 如圖3所示， 轉(zhuǎn)向角度θij為兩個(gè)連續(xù)路徑段LkijLk+1ij和Lk+1ijLk+2ij在水平面投影的夾角； Lk+1′ijLk+2′ij為UAV從第k+1個(gè)路徑點(diǎn)到第k+2個(gè)路徑點(diǎn)的路徑在水平面上投影； δij為UAV該段路徑的爬升角度。 根據(jù)UAV性能約束， 設(shè)定θij和δij分別不得超過最大轉(zhuǎn)向角θmax和最大爬升角δmax。
取Z為沿Z軸正向的單位向量， 根據(jù)圖3所示， 轉(zhuǎn)向角度θij可表示為
θkij=arctanLk′ijLk+1′ij·Lk+1′ijLk+2′ijLk+1′ijLk+2′ij·Lk+1′ijLk+2′ij（8）
爬升角度δij可表示為
δkij=arctanZk+1ij－ZkijLk′ijLk+1′ij（9）
路徑平滑代價(jià)可表示為
F4（Pathij）=ω1∑n－2k=1θkij+ω2∑n－1k=1δkij－δk－1ij（10）
式中： ω1和ω2分別表示轉(zhuǎn)向代價(jià)和爬升代價(jià)的權(quán)重。
綜上所述， 每架UAV的路徑規(guī)劃評價(jià)函數(shù)如下：
Fall（Pathij）=λ1·F1（Pathij）+λ2·F2（Pathij）+
λ3·F3（Pathij）+λ4·F4（Pathij）（11）
式中： λ1， λ2， λ3， λ4分別為路徑長度代價(jià)、 路徑威脅代價(jià)、 路徑高度代價(jià)、 路徑平滑代價(jià)的權(quán)重。
2 MSIGWO算法設(shè)計(jì)
2.1 標(biāo)準(zhǔn)GWO
GWO的仿生原理為： 在大自然中， 灰狼群內(nèi)部具有嚴(yán)密的等級制度， 其中： 最強(qiáng)壯的狼王α擁有絕對領(lǐng)導(dǎo)權(quán)； 其次為β 狼， 負(fù)責(zé)傳達(dá)狼王的命令； 之后為δ狼， 主要負(fù)責(zé)放哨、 看護(hù)等事項(xiàng)； 其余的狼為下層狼， 負(fù)責(zé)接受上層狼的指揮領(lǐng)導(dǎo)。 在GWO中， 每只灰狼代表一個(gè)潛在解， 在迭代過程中， 上下層的狼會(huì)隨著各自的強(qiáng)壯程度（適應(yīng)度值）進(jìn)行競爭和替代。
模擬灰狼群的狩獵過程， GWO的主要內(nèi)容可以分為四個(gè)部分：
（1） 初始化階段。 在該階段中， 狼群個(gè)體隨機(jī)分布， 通過計(jì)算各個(gè)灰狼的適應(yīng)度值并按照由優(yōu)到劣的順序排列， 將前三的個(gè)體依次指定為α狼、 β狼和δ狼， 其所處位置分別定義為Xα， Xβ和Xδ， 其余個(gè)體統(tǒng)一定義為下層狼。
（2） 包圍獵物。 在狩獵時(shí)， 將灰狼圍捕獵物的行為模擬為
X（t+1）=Xp（t）－A·D（12）
D=C·Xp（t）－X（t）（13）
式中： X（t+1）為更新后灰狼的位置； Xp（t）為當(dāng)前獵物的位置； D為當(dāng)前灰狼與獵物的距離； t為當(dāng)前的迭代次數(shù)。 系數(shù)A和C用于控制灰狼在搜索空間中的移動(dòng)， 其中， A決定灰狼是向獵物靠近還是遠(yuǎn)離， 當(dāng)Agt;1時(shí)灰狼個(gè)體遠(yuǎn)離獵物， 為全局搜索階段， 反之為局部搜索階段； C的作用是有助于增強(qiáng)算法的多樣性。 系數(shù)A和C分別表示為
A=2a·r1－a（14）
a=2－2tT（15）
C=2r2（16）
式中： a為從2線性遞減至0的收斂因子； r1和r2為區(qū)間［0， 1］上的隨機(jī)變量。
（3） 追捕獵物。 在大自然中， 灰狼群是通過狼王α的指示對獵物進(jìn)行包圍、 追捕和攻擊的。 然而， 在優(yōu)化問題中， 由于獵物（全局最優(yōu)解） 的位置是未知的， 僅憑借狼王α的位置Xα是無法精準(zhǔn)找到獵物的位置。 因此， 為了更多獲取獵物的位置信息， 需要保留上一次迭代中上層狼的位置信息， 用于下一次迭代時(shí)估計(jì)獵物位置， 當(dāng)?shù)Y(jié)束時(shí)， 輸出狼王α的位置作為最優(yōu)解的位置。 灰狼個(gè)體的更新公式如下：
X（t+1）=（X1+X2+X3）3（17）
X1=Xα（t）－A1·Dα， Dα=|C1·Xα（t）－X（t）|（18）
X2=Xβ（t）－A2·Dβ， Dβ=|C2·Xβ（t）－X（t）|（19）
X3=Xδ（t）－A3·Dδ， Dδ=|C3·Xδ（t）－X（t）|（20）
式中： X1， X2， X3分別為灰狼個(gè)體受α狼、 β狼和δ狼影響移動(dòng)的步長。
2.2 基于復(fù)合混沌序列和準(zhǔn)反向?qū)W習(xí)的種群初始化
作為元啟發(fā)式算法， GWO初始分布對于算法優(yōu)化求解速度和質(zhì)量有很大影響， 然而GWO在種群初始化階段使用的隨機(jī)策略有可能產(chǎn)生較為集中或者分散的初始灰狼群， 這兩種情況都不利于算法求解。 作為一種隨機(jī)性、 敏感性和確定性的混合序列， 混沌序列在保證隨機(jī)性的同時(shí)可避免種群中個(gè)體重復(fù)， 因此常被應(yīng)用于優(yōu)化種群初始分布， 然而大多數(shù)應(yīng)用都只局限于引入簡單的混沌序列， 但是由于不同的混沌序列存在不同的特性， 如最常用的Logistic序列對初始值敏感， 生成的隨機(jī)數(shù)在兩端分布較多， 一定程度限制了混沌序列在改善初始種群分布時(shí)實(shí)際效果。 基于上述分析， 本文在MSIGWO初始化階段引入融合Logistic序列和Tent序列的復(fù)合混沌序列Logistic－Tent， 數(shù)學(xué)表達(dá)式如下：
xi+1=
rxi（1－xi）+（4－r）xi2mod1， xilt;0.5， r∈（0， 4）
rxi（1－xi）+（4－r）（1－xi）2mod1， xi≥0.5， r∈（0， 4）" （21）
該混沌序列融合了Logistic序列的復(fù)雜混沌動(dòng)力學(xué)特性和Tent序列更快的迭代速度。 圖4為10 000次混沌值分布統(tǒng)計(jì)， 相較于單一的Logistic序列， Logistic－Tent序列產(chǎn)生的隨機(jī)數(shù)在［0， 1］區(qū)間內(nèi)分布更加均勻。
為更好地提升初始種群生成質(zhì)量， 本文在使用Logistic－Tent混沌序列的基礎(chǔ)上進(jìn)一步引入準(zhǔn)反向?qū)W習(xí)策略。 準(zhǔn)反向?qū)W習(xí)表示如下：
Xqo（t）=randLB+UB2， Xo（t）（22）
Xo（t）=LB+UB－X（t）（23）
式中： X（t）為當(dāng)前解； Xo（t）為反向?qū)W習(xí)后的解； Xqo（t）為準(zhǔn)反向?qū)W習(xí)解； LB和UB分別為解空間的下界和上界。 如圖5所示， 可看到準(zhǔn)反向?qū)W習(xí)在反向?qū)W習(xí)基礎(chǔ)上做了進(jìn)一步隨機(jī)化操作， 相較于反向?qū)W習(xí)每次產(chǎn)生的映射為一個(gè)確定值， 準(zhǔn)反向?qū)W習(xí)產(chǎn)生的映射Xqo（t）在解空間上下界中間值和反向?qū)W習(xí)映射Xo（t）之間隨機(jī)分布。 研究表明， 在尋找全局最優(yōu)解時(shí)， 添加了隨機(jī)性的準(zhǔn)反向解比反向解更加有效［18］。
2.3 基于精英狼凸透鏡反射學(xué)習(xí)的種群迭代
由算法原理可知， 參數(shù)A對于協(xié)調(diào)GWO全局搜索和局部尋優(yōu)的能力具有關(guān)鍵影響， 其值與a相關(guān)聯(lián)， 因參數(shù)A隨著迭代次數(shù)的增加而減小， 所以伴隨迭代次數(shù)增大， GWO更多地由全局搜索逐漸轉(zhuǎn)變?yōu)榫植繉?yōu)， 由于灰狼群中的下層狼個(gè)體通過追尋上層α狼、 β狼和δ狼的位置實(shí)現(xiàn)對獵物的包圍， 此時(shí)若上層α狼、 β狼和δ狼位于局部最優(yōu)解附近， 則很容易導(dǎo)致GWO陷入局部最優(yōu)解。 針對此問題， 本文在迭代階段引入基于凸透鏡成像原理的精英狼反向?qū)W習(xí)策略。
假設(shè)在解空間中有高度h的個(gè)體P， 其在X軸上的投影為XP， 選擇（LB+UB）/2的位置為基點(diǎn)O并放置焦距為F的凸透鏡， 個(gè)體P經(jīng)凸透鏡得到一個(gè)高度h*的倒像P*， 此時(shí)P*在X軸上的投影XP*即為反向個(gè)體， 成像方式如圖6所示。
XP與其反向個(gè)體XP*間的關(guān)系如下：
（UB+LB）/2－XPXP*－（UB+LB）/2=η （24）
η=hh*（25）
式中： η作為伸縮因子， 表示凸透鏡中物與像的比例對應(yīng)關(guān)系。 為提升MSIGWO在解空間中搜索的能力， 將η設(shè)置為隨算法迭代非線性遞減， 以使得MSIGWO的反向個(gè)體在迭代前期可以獲得較大的生成范圍， 提高搜索能力； 在迭代后期獲得較小的生成范圍， 提高局部尋優(yōu)能力。
η=ηmax－（ηmax－ηmin）·（t/tmax）2（26）
式中： ηmax和ηmin分別為最大伸縮因子和最小伸縮因子。
將式（24）進(jìn)行變化可得反向個(gè)體XP*的表達(dá)式：
XP*=UB+LB2+UB+LB2η－XPη（27）
將式（27）推廣至D維搜索空間可得
XP*j=UjB+LjB2+UjB+LjB2η－Xjη（28）
由于GWO算法中的上層狼在算法收斂階段指引整個(gè)種群更新且為迭代中的歷史最優(yōu)前三解， 所以上層狼的更新機(jī)制是避免GWO陷入局部最優(yōu)的關(guān)鍵。 本文將 α狼、 β狼和δ狼定義為精英狼， 在每次迭代過程中使用式（28）生成精英狼的反向個(gè)體， 采用貪婪機(jī)制對上層狼進(jìn)行擇優(yōu)篩選替代。
2.4 MSIGWO算法流程
本文提出的基于MSIGWO的三維路徑規(guī)劃算法流程如圖7所示。
步驟1： 導(dǎo)入地形數(shù)據(jù)， 依據(jù)式（3）生成DEM數(shù)字地形圖， 設(shè)定式（11）中評價(jià)函數(shù)的各參數(shù)值；
步驟2： 使用Logistic－Tent混沌序列生成初始種群， 在此基礎(chǔ)上生成準(zhǔn)反向?qū)W習(xí)初始種群； 計(jì)算每個(gè)個(gè)體的適應(yīng)度值， 使用貪婪機(jī)制完成初始種群擇優(yōu)替代， 確定α 狼、 β狼和δ狼；
步驟3： 依據(jù)式（14）～（16）完成參數(shù)a， A以及C的更新；
步驟4： 依據(jù)式（28）生成α狼、 β狼和δ狼的凸透鏡反向個(gè)體， 使用貪婪機(jī)制完成上層狼的擇優(yōu)替換；
步驟5： 依據(jù)式（17）～（20）更新灰狼群位置， 計(jì)算適應(yīng)度并更新α狼、 β狼和δ狼；
步驟6： 檢測是否滿足終止條件， 若未滿足則返回步驟3， 若滿足則轉(zhuǎn)到步驟7；
步驟7： 輸出最優(yōu)值， 算法結(jié)束。
2.5 MSIGWO算法的時(shí)間復(fù)雜度分析
設(shè)定種群規(guī)模為N， 問題維度為D， 迭代次數(shù)為M。 在標(biāo)準(zhǔn)的GWO算法中， 假設(shè)完成初始化階段所需時(shí)間為T1； 根據(jù)式（17）， 個(gè)體更新每一維位置所需時(shí)間為T2； 根據(jù)式（11）， 個(gè)體求解適應(yīng)度值所需時(shí)間為f（D）。 則標(biāo)準(zhǔn)GWO的時(shí)間復(fù)雜度為
TGWO=O（T1+MN（DT2+f（D）））=O（D+f（D））（29）
在本文的MSIGWO算法中， 假設(shè)初始化階段引入的Logistic－Tent復(fù)合混沌序列生成初始種群所需時(shí)間為T3， 在此基礎(chǔ)上進(jìn)行準(zhǔn)反向?qū)W習(xí)所需時(shí)間為T4； 迭代階段種群執(zhí)行精英狼凸透鏡反射學(xué)習(xí)所需時(shí)間為T5，采用貪婪機(jī)制進(jìn)行篩選的時(shí)間為T6。 則MSIGWO的時(shí)間復(fù)雜度為
TMSIGWO=O（T3+T4+M（NDT2+T5+T6+Nf（D））=O（D+f（D））（30）
綜上， 與標(biāo)準(zhǔn)GWO相比， MSIGWO并未增加額外的時(shí)間復(fù)雜度， 算法執(zhí)行效率未下降。
3 仿真實(shí)驗(yàn)
3.1 仿真參數(shù)設(shè)置
設(shè)定使用3架UAV分別執(zhí)行三個(gè)目標(biāo)的作戰(zhàn)任務(wù)， UAV起點(diǎn)和目標(biāo)的位置如表1所示， 威脅源的設(shè)置如表2所示。 原始數(shù)字地形模型中的參數(shù)a， b， c， d， e， f， g分別設(shè)置為1， 0.2， 1， 0.6， 0.1， 0.1， 0.1， 同時(shí)為增加地形復(fù)雜度， 將威脅地形等效模型中的山峰數(shù)目設(shè)置為10， 每個(gè)山峰對應(yīng)的xoi， yoi， xsi， ysi四項(xiàng)參數(shù)為隨機(jī)產(chǎn)生， 評價(jià)函數(shù)中的參數(shù)λ1， λ2， λ3， λ4分別設(shè)置為5， 1， 10， 1。 約束條件設(shè)置如表3所示， 凸透鏡反向?qū)W習(xí)中的參數(shù)ηmax和ηmin分別設(shè)置為10和1。
為說明MSIGWO算法性能， 在相同地圖下利用GWO算法、 小龍蝦優(yōu)化算法［19］（Crayfish Optimization Algorithm， COA）、 蜘蛛蜂優(yōu)化算法［20］（Spider Wasp Optimizer， SWO）、 光譜優(yōu)化算法［21］（Light Spectrum Optimizer， LSO）和本文改進(jìn)MSIGWO算法進(jìn)行三維路徑規(guī)劃仿真對比實(shí)驗(yàn)， 種群規(guī)模大小設(shè)置為100， 最大迭代次數(shù)設(shè)置為500。
3.2 仿真結(jié)果及分析
圖8～12分別為MSIGWO， GWO， COA， SWO， LSO算法的仿真結(jié)果。
從圖8～12中的三維及二維路徑規(guī)劃圖可以看出， 相關(guān)算法均給出了各自路徑規(guī)劃結(jié)果且所規(guī)劃路徑都避開了戰(zhàn)場中的山峰和威脅源。 從總成本及成本分布圖可知， 在各算法路徑規(guī)劃方案中， MSIGWO給出的路徑規(guī)劃總成本最低。 一方面， MSIGWO規(guī)劃方案路徑長度最短， 使得路徑成本大大降低； 另一方面， 其所規(guī)劃路徑有效減少了UAV飛行時(shí)的高度變化和轉(zhuǎn)向調(diào)整， 降低了高度成本和平滑成本。 在三維路徑規(guī)劃圖中也可直觀看到， MSIGWO的UAV規(guī)劃路徑最短且較為平滑。
由于元啟發(fā)式算法具有隨機(jī)性， 為更好地說明算法性能， 保證結(jié)果的可靠性， 將各算法重復(fù)運(yùn)行100次， 各算法評價(jià)函數(shù)統(tǒng)計(jì)結(jié)果如表4所示。
從表4中可以看出， MSIGWO在100次統(tǒng)計(jì)結(jié)果中的最優(yōu)值和平均值均優(yōu)于其他對比算法， 最差值僅比SWO稍高， 排名第二。 相較于GWO， MSIGWO的最優(yōu)值、 平均值、 最差值三項(xiàng)指標(biāo)分別提升了6.1%， 5.1%和13.3%， 這一方面得益于MSIGWO初始階段采用的復(fù)合混沌和準(zhǔn)反向?qū)W習(xí)策略生成的初始種群更加均勻， 減少了全局搜索階段時(shí)的無效搜索； 另一方面， 最差值在三項(xiàng)指標(biāo)中提升幅度最大， 也表明MSIGWO采用的精英狼凸透鏡反射策略對上層狼位置的重點(diǎn)調(diào)整優(yōu)化， 有效避免了算法在迭代階段陷入局部最優(yōu)解。
4 結(jié)" 論
本文針對多無人機(jī)三維路徑規(guī)劃開展研究。 首先， 使用DEM構(gòu)建了三維空間模型， 結(jié)合約束條件、 任務(wù)需求構(gòu)建了多目標(biāo)評價(jià)函數(shù)； 其次， 分析了GWO的基本原理， 介紹了MSIGWO在算法初始化階段和迭代階段采取的改進(jìn)策略； 最后， 使用MSIGWO與四種啟發(fā)式算法進(jìn)行對比實(shí)驗(yàn)， 在包含長度代價(jià)、 威脅代價(jià)、 高度代價(jià)和平滑代價(jià)的綜合評價(jià)函數(shù)重復(fù)實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果中， MSIGWO所得路徑規(guī)劃方案的最優(yōu)值、 平均值、 最差值三項(xiàng)指標(biāo)相較原算法分別提升了6.1%， 5.1%和13.3%， 驗(yàn)證了MSIGWO可有效應(yīng)用于路徑規(guī)劃問題求解。 為更好模擬戰(zhàn)場環(huán)境， 在后續(xù)研究中可進(jìn)一步考慮移動(dòng)障礙物、 天氣變化等各類復(fù)雜情況對多無人機(jī)路徑規(guī)劃問題求解帶來的不同影響。
參考文獻(xiàn)：
［1］ Ricardo J A， Giacomossi L， Trentin J A F S， et al. Cooperative Threat Engagement Using Drone Swarms［J］. IEEE Access， 2023， 11： 9529-9546.
［2］ 王洪斌， 尹鵬衡， 鄭維， 等. 基于改進(jìn)的A*算法與動(dòng)態(tài)窗口法的移動(dòng)機(jī)器人路徑規(guī)劃［J］. 機(jī)器人， 2020， 42（3）： 346-353.
Wang Hongbin， Yin Pengheng， Zheng Wei， et al. Mobile Robot Path Planning Based on Improved A* Algorithm and Dynamic Window Method［J］. Robot， 2020， 42（3）： 346-353. （in Chinese）
［3］ 余敏， 羅建軍， 王明明， 等. 一種改進(jìn) RRT* 結(jié)合四次樣條的協(xié)調(diào)路徑規(guī)劃方法［J］. 力學(xué)學(xué)報(bào)， 2020， 52（4）： 1024-1034.
Yu Min， Luo Jianjun， Wang Mingming， et al. Coordinated Path Planning by Integrating Improved RRT* and Quartic Spline［J］. Chinese Journal of Theoretical and Applied Mechanics， 2020， 52（4）： 1024-1034. （in Chinese）
［4］ 陳明強(qiáng)， 馮樹娟， 李奇峰. 基于改進(jìn)人工勢場的物流無人機(jī)三維航跡規(guī)劃［J］. 無線電工程， 2023， 53（10）： 2352-2359.
Chen Mingqiang， Feng Shujuan， Li Qifeng. Three-Dimensional Trajectory Planning of Logistics UAV Based on Improved Artificial Potential Field［J］. Radio Engineering， 2023， 53（10）： 2352-2359.（in Chinese）
［5］ 姜辰凱， 李智， 盤書寶， 等. 基于改進(jìn)Dijkstra算法的AGVs無碰撞路徑規(guī)劃［J］. 計(jì)算機(jī)科學(xué)， 2020， 47（8）： 272-277.
Jiang Chenkai， Li Zhi， Pan Shubao， et al. Collision-Free Path Planning of AGVs Based on Improved Dijkstra Algorithm［J］. Computer Science， 2020， 47（8）： 272-277. （in Chinese）
［6］ 趙玉花， 石永康. 改進(jìn)粒子群算法的多無人機(jī)航跡優(yōu)化［J］. 電光與控制， 2023， 30（5）： 29-33.
Zhao Yuhua， Shi Yongkang. Improved Particle Swarm Optimization Algorithm for Multi-UAV Flight Path Planning［J］. Electronics Optics amp; Control， 2023， 30（5）： 29-33.（in Chinese）
［7］ 宋阿妮， 包賢哲. 精英擴(kuò)散蟻群優(yōu)化算法求解運(yùn)輸無人機(jī)三維路徑規(guī)劃［J］. 計(jì)算機(jī)工程與科學(xué)， 2021， 43（10）： 1891-1900.
Song Ani， Bao Xianzhe. An Elite Diffusion Ant Colony Optimization Algorithm for Solving 3D Path Planning of Transportation UAV［J］. Computer Engineering amp; Science， 2021， 43（10）： 1891-1900.（in Chinese）
［8］ Cao Y， Wei W Y， Bai Y， et al. Multi-Base Multi-UAV Cooperative Reconnaissance Path Planning with Genetic Algorithm［J］. Cluster Computing， 2019， 22（S3）： 5175-5184.
［9］ Xue J K， Shen B. A Novel Swarm Intelligence Optimization Approach： Sparrow Search Algorithm［J］. Systems Science amp; Control Engineering， 2020， 8（1）： 22-34.
［10］ Shao S K， Peng Y， He C L， et al. Efficient Path Planning for UAV Formation via Comprehensively Improved Particle Swarm Optimization［J］. ISA Transactions， 2020， 97： 415-430.
［11］ Ali Z A， Han Z G， Di Z R. Path Planning of Multiple UAVs Using MMACO and DE Algorithm in Dynamic Environment［J］. Measurement and Control， 2023， 56（3/4）： 459-469.
［12］ 鄧灝， 唐希浪， 蔡忠義， 等. 基于改進(jìn)遺傳算法的多無人機(jī)搜索航路規(guī)劃［J］. 電光與控制， 2024， 31（4）： 12-17.
Deng Hao， Tang Xilang， Cai Zhongyi， et al. Multi-UAV Search Route Planning Based on Improved Genetic Algorithm［J］. Electronics Optics amp; Control， 2024， 31（4）： 12-17.（in Chinese）
［13］ 王玲玲， 孫磊， 丁光平， 等. 基于改進(jìn)麻雀搜索算法的無人機(jī)航路規(guī)劃研究［J］. 彈箭與制導(dǎo)學(xué)報(bào)， 2022， 42（6）： 55-60.
Wang Lingling， Sun Lei， Ding Guangping， et al. Research on UAV Route Planning Based on Improved Sparrow Search Algorithm［J］. Journal of Projectiles， Rockets， Missiles and Guidance， 2022， 42（6）： 55-60.（in Chinese）
［14］ 劉聰. 改進(jìn)的灰狼優(yōu)化算法及其應(yīng)用研究［D］. 哈爾濱： 哈爾濱師范大學(xué)， 2023.
Liu Cong. Improved Grey Wolf Optimization Algorithm and Its Application Research［D］.Harbin： Harbin Normal University， 2023. （in Chinese）
［15］ 余飛. 基于群智優(yōu)化算法的頻譜感知和頻譜分配研究［D］. 南京： 南京郵電大學(xué)， 2023.
Yu Fei. Research on Spectrum Sensing and Spectrum Allocation Based on Swarm Intelligence Optimization Algorithm［D］.Nanjing： Nanjing University of Posts and Telecommunications， 2023. （in Chinese）
［16］ 崔慶. 基于多目標(biāo)灰狼算法的園區(qū)微電網(wǎng)綜合能源優(yōu)化調(diào)度［J］. 電腦知識與技術(shù)， 2024， 20（4）： 16-18.
Cui Qing. Comprehensive Energy Optimization and Scheduling of Park Microgrid Based on Multi-Objective Grey Wolf Algorithm［J］. Computer Knowledge and Technology， 2024， 20（4）： 16-18.（in Chinese）
［17］ 穆曉霞， 鄭李婧. 基于F-score和二進(jìn)制灰狼優(yōu)化的腫瘤基因選擇方法［J］. 南京師大學(xué)報(bào)： 自然科學(xué)版， 2024， 47（1）： 111-120.
Mu Xiaoxia， Zheng Lijing. Tumor Gene Selection Based on F-score and Binary Grey Wolf Optimization［J］. Journal of Nanjing Normal University： Natural Science Edition， 2024， 47（1）： 111-120.（in Chinese）
［18］ Tizhoosh H R. Opposition-Based Learning： A New Scheme for Machine Intelligence［C］∥International Conference on Computational Intelligence for Modelling， Control and Automation and International Conference on Intelligent Agents， Web Technologies and Internet Commerce （CIMCA-IAWTIC'06）， 2005： 695-701.
［19］ Jia H M， Rao H H， Wen C S， et al. Crayfish Optimization Algorithm［J］. Artificial Intelligence Review， 2023， 56（S2）： 1919-1979.
［20］ Abdel-Basset M， Mohamed R， Jameel M， et al. Spider Wasp Optimizer： A Novel Meta-Heuristic Optimization Algorithm［J］. Artificial Intelligence Review， 2023， 56（10）： 11675-11738.
［21］ Abdel-Basset M， Mohamed R， Sallam K M， et al. Light Spectrum Optimizer： A Novel Physics-Inspired Metaheuristic Optimization Algorithm［J］. Mathematics， 2022， 10（19）： 3466.
Multi-Drone 3D Path Planning Based on Multi-Strategy
Improved Grey Wolf Algorithm
Xu Ziliang1， 2， Hu Tao1*， Liu Kaiyue1， An Lening1， Yang Siwei1
（1. University of Information Engineering， Zhengzhou 450000， China; 2. Unit 66389 of PLA， Zhengzhou 450000， China）
Abstract： Multiple UAV three-dimensional path planning aims to provide reasonable and feasible flight paths for each UAV to its target while satisfying constraints and avoiding threats. Addressing the issues of slow search speed and poor path quality of current metaheuristic algorithms in solving multi-constraint and multi-threat three-dimensional spatial path planning， a path planning method based on a multi-strategy improved grey wolf optimization algorithm is proposed. Digital elevation models are used to complete three-dimensional spatial environment modeling， and a comprehensive evaluation function incorporating factors such as length， threat， height， and smoothness is established based on the flight scenario. By optimizing the initial population using a composite chaotic sequence and quasi-reverse learning strategy， and considering the crucial impact of upper-level wolves on population convergence in iterative stages， the algorithm’s ability to avoid local optima is enhanced using the elite wolf convex lens reflection learning strategy. Simulation experiments show that the multi-strategy improved grey wolf optimization algorithm improves the optimal， average， and worst values of the comprehensive evaluation function statistics by 6.1%， 5.1%， and 13.3%， respectively， compared to the original algorithm. This validates the effectiveness of the proposed method in solving multi-constraint and multi-threat three-dimensional spatial path planning problems.
Key words：" multiple UAVs; three-dimensional path planning; grey wolf optimization algorithm; composite chaotic sequence; quasi-reverse learning; elite wolf convex lens reflection learning
