基于分組優(yōu)化改進(jìn)粒子群算法的無人機(jī)三維路徑規(guī)劃*

藺文軒，謝文俊，張 鵬，紀(jì)良杰

（1.空軍工程大學(xué)研究生院，西安 710043；2.空軍工程大學(xué)裝備管理與無人機(jī)工程學(xué)院，西安 710043）

0 引言

近年來無人機(jī)憑借其優(yōu)異的性能在戰(zhàn)爭中嶄露頭角，表現(xiàn)出極強(qiáng)的戰(zhàn)斗力，成為一種新興的作戰(zhàn)力量，無人機(jī)能否成功、高效地完成作戰(zhàn)任務(wù)，路徑規(guī)劃起到了至關(guān)重要的作用。針對(duì)無人機(jī)路徑規(guī)劃問題，目前研究成果較多，主要的研究算法有遺傳算法［1］、蟻群算法［2］、A*算法［3］、人工勢場法［4］、粒子群算法［5］等。岳秀等人針對(duì)多無人機(jī)多目標(biāo)分配問題，首先采用A*算法對(duì)無人機(jī)進(jìn)行了最優(yōu)路徑的求解，再將多目標(biāo)分解為多個(gè)子目標(biāo)，利用改進(jìn)的模擬退火算法針對(duì)子目標(biāo)進(jìn)行航跡規(guī)劃，實(shí)現(xiàn)了無人機(jī)巡航狀態(tài)下對(duì)子目標(biāo)區(qū)域的高覆蓋［6］。賈會(huì)群等針對(duì)使用傳統(tǒng)粒子群算法對(duì)機(jī)器人進(jìn)行路徑規(guī)劃時(shí)出現(xiàn)的搜索滯留的缺點(diǎn)，向算法中引入雞群優(yōu)化算法中的母雞和小雞更新策略，對(duì)停滯粒子進(jìn)行擾動(dòng)，提高了算法的全局搜索能力［7］。范葉滿等針對(duì)植保無人機(jī)在丘陵山地區(qū)域工作效率低下的問題，以四旋翼無人機(jī)為例建立了相應(yīng)的運(yùn)動(dòng)學(xué)模型，并通過模擬退火算法完成了無人機(jī)在山地作業(yè)情況下最優(yōu)能耗的路徑規(guī)劃［8］。無人機(jī)路徑規(guī)劃需要考慮戰(zhàn)場環(huán)境、目標(biāo)威脅、自身?xiàng)l件等約束條件，實(shí)質(zhì)上是一個(gè)典型的多目標(biāo)優(yōu)化問題［9］，粒子群算法憑借其算法簡單、高效、運(yùn)算迅速的特點(diǎn)廣泛應(yīng)用于尋優(yōu)問題求解［10］，但其在求解無人機(jī)三維路徑規(guī)劃問題時(shí)存在易陷入局部極值、早熟、全局搜索能力較差等問題。本文以粒子群算法為基礎(chǔ)，針對(duì)其缺點(diǎn)提出了一種基于雞群分組優(yōu)化策略的粒子群算法，通過對(duì)粒子進(jìn)行分組提高粒子群算法的局部搜索能力，并采取模擬退火操作對(duì)粒子更新規(guī)則進(jìn)行處理，在算法早期增加了粒子的多樣性，能夠有效避免粒子群算法易陷入局部極值和早熟的問題，并通過實(shí)驗(yàn)仿真驗(yàn)證了其在解決無人機(jī)三維路徑規(guī)劃問題上的可行性。

1 算法原理

1.1 粒子群算法

粒子群算法通過模擬鳥類的捕食現(xiàn)象，利用群體中個(gè)體信息的共享，使得整個(gè)群體在求解空間中實(shí)現(xiàn)從無序到有序的過程，并尋得最優(yōu)解。算法的主要內(nèi)容為：假設(shè)在D 維搜索空間中，存在種群數(shù)量為N 的粒子群，每個(gè)粒子的位置及速度分別表示為Xi={Xi1，Xi2，…，Xin}，Vi={Vi1，Vi2，…，Vin}，每一個(gè)粒子的最優(yōu)解Pbest表示為Pi={Pi1，Pi2，…，Pin}，全局最優(yōu)解Gbest表示為Pg={Pg1，Pg2，…，Pgn}，粒子群中的每個(gè)粒子根據(jù)Pbest和Gbest更新自己的位置和速度，具體方法為：

式中，t 表示當(dāng)前迭代次數(shù)；Pid表示當(dāng)前更新粒子最優(yōu)解，Pgd表示當(dāng)前全局最優(yōu)解；c1，c2為學(xué)習(xí)因子，主要控制粒子根據(jù)現(xiàn)有信息進(jìn)行判斷，對(duì)自身位置進(jìn)行調(diào)整，向潛在最優(yōu)位置移動(dòng)；r1，r2為［0，1］上的隨機(jī)數(shù)。

1.2 雞群優(yōu)化算法

雞群算法［11］（chicken swarm optimization，CSO）是一種模擬雞群覓食行為的仿真算法，根據(jù)雞群內(nèi)的等級(jí)制度對(duì)粒子進(jìn)行分類，能夠有效地解決智能算法常見的早熟現(xiàn)象，且具有收斂速度快，尋優(yōu)能力強(qiáng)的特點(diǎn)。其算法原理如下：

雞群在覓食過程中根據(jù)公雞的數(shù)量進(jìn)行分組，小組內(nèi)的公雞在組內(nèi)具有領(lǐng)導(dǎo)作用，母雞的覓食線路受限于公雞，小雞的覓食線路受限于母雞。在算法初期根據(jù)粒子個(gè)體的適應(yīng)度差異對(duì)粒子進(jìn)行分組，根據(jù)適應(yīng)度的好壞將粒子依次分為公雞、母雞、小雞。

公雞的適應(yīng)度最好，具有最大的搜索范圍負(fù)責(zé)全局搜索，其位置更新規(guī)則如下：

母雞跟隨公雞的覓食路線，其位置更新策略如下：

式中，k1為母雞所在小組內(nèi)公雞對(duì)其的影響因子；k2為其他雞對(duì)其的影響因子；rand 表示［0，1］的隨機(jī)數(shù)；r1表示母雞跟隨的攻擊；r2表示任意小組的公雞或母雞。

小雞跟隨母雞的覓食路線，其位置更新策略入下：

式中，m 表示當(dāng)前小雞i 跟隨的母雞，F(xiàn)L 表示［0，2］上的隨機(jī)數(shù)。

2 基于分組優(yōu)化的粒子群算法設(shè)計(jì)

2.1 雞群算法與粒子群算法對(duì)比

粒子群算法與雞群算法的相同點(diǎn)：1）都是仿生智能算法；2）都是全局隨機(jī)搜索算法；3）都容易陷入局部最優(yōu)解；4）都選擇適應(yīng)度較好的個(gè)體作為更新標(biāo)準(zhǔn)；5）都受到先前經(jīng)驗(yàn)的影響。

粒子群算法與雞群算法的不同點(diǎn)：1）粒子群算法在運(yùn)算過程中整體是一個(gè)種群，雞群算法在進(jìn)化過程中將雞群分為若干小組，組內(nèi)與組間進(jìn)行信息交互與競爭；2）粒子群算法每個(gè)粒子都會(huì)存儲(chǔ)最優(yōu)適應(yīng)度，雞群算法中只有小組內(nèi)的公雞記錄小組的最優(yōu)解，其余成員根據(jù)公雞位置進(jìn)行位置更新；3）粒子群算法中每個(gè)個(gè)體的地位都是同級(jí)的，雞群算法中將個(gè)體按照適應(yīng)度進(jìn)行了等級(jí)劃分，適應(yīng)度好的個(gè)體具有較強(qiáng)的搜索能力，適應(yīng)度差的個(gè)體需要跟隨適應(yīng)度好的個(gè)體進(jìn)行搜索。

通過對(duì)兩種算法的對(duì)比發(fā)現(xiàn)其有很多相同之處，都強(qiáng)調(diào)個(gè)體的搜索功能，但在個(gè)體的等級(jí)劃分上存在區(qū)別。在進(jìn)行搜索的過程中，粒子群算法容易受到當(dāng)前全局最優(yōu)解的影響，容易陷入局部最優(yōu)循環(huán)，導(dǎo)致算法性能下降。綜合分析將兩種算法結(jié)合，以雞群分組更新策略改進(jìn)粒子群迭代更新策略，避免算法陷入局部最優(yōu)循環(huán)，提高全局搜索能力。

2.2 基于分組優(yōu)化的粒子群算法設(shè)計(jì)

改進(jìn)的算法描述為：在初始化過程中，根據(jù)雞群算法的分組策略，選擇適應(yīng)度較好的粒子作為排頭粒子，并將所有粒子分為n 組，將適應(yīng)度較好的粒子作為小組內(nèi)的最優(yōu)粒子。根據(jù)雞群算法原理，小組內(nèi)的最優(yōu)粒子能夠搜索較大的目標(biāo)區(qū)域，其余粒子主要在最優(yōu)粒子的影響下進(jìn)行局部區(qū)域的最優(yōu)搜索，小組內(nèi)的等級(jí)變化通過適應(yīng)度的改變進(jìn)行調(diào)整。經(jīng)此改進(jìn)，粒子群算法中的所有小組最優(yōu)粒子負(fù)責(zé)全局空間的最優(yōu)搜索；各小組內(nèi)的粒子負(fù)責(zé)目標(biāo)空間的局部搜索，提高算法的局部搜索能力。改進(jìn)后小組的粒子更新規(guī)則如下：

1）最優(yōu)粒子更新規(guī)則：

xij表示小組i 內(nèi)的第j 個(gè)粒子，S1=exp（fi，j-fi，jd）/（abs（fi，j）+ε），S2=exp（fi，gd-fi，j），是改進(jìn)后學(xué)習(xí)因子，fi，j表示當(dāng)前粒子的適應(yīng)度，pi，jd表示小組i 的最優(yōu)粒子xi，j的最優(yōu)解，pi，gd表示小組i 內(nèi)處最優(yōu)粒子外任一粒子的最優(yōu)解。k 為該小組內(nèi)最優(yōu)粒子外的任一其他粒子。

2）小組內(nèi)粒子更新規(guī)則：

式中，pid為小組內(nèi)粒子的最優(yōu)解；pgd為全部粒子的最優(yōu)解。由式（8）易得，小組粒子更新速度幾乎只受慣性權(quán)重ω 的影響，ω 的值隨著迭代次數(shù)的增加逐漸減小，這就導(dǎo)致了小組內(nèi)粒子更新的停滯，陷入局部最優(yōu)解，為解決這一問題，在小組粒子進(jìn)行局部搜索時(shí)加入模擬退火操作，增加小組粒子的多樣性，進(jìn)一步提高小組粒子的局部搜索能力。

模擬退火算法的基本原理為：當(dāng)固體溫度較高時(shí)，粒子區(qū)域無序；當(dāng)溫度降低時(shí)，粒子逐漸趨于穩(wěn)定［12-13］。當(dāng)固體具有一定的溫度時(shí)，算法具有絕對(duì)收斂到全局極值的能力，采用Metropolis 準(zhǔn)則［14］進(jìn)行算法更新，如下式所示：

設(shè)初始粒子數(shù)量為N，最大迭代次數(shù)為T，根據(jù)初始適應(yīng)度確定分組數(shù)量為n，具體的算法流程如下：

Step 1：初始化算法，設(shè)定各參數(shù)值；

Step 2：計(jì)算每個(gè)粒子的適應(yīng)度，根據(jù)適應(yīng)度將粒子分為n 組，確定小組最優(yōu)粒子；

Step 3：初始化小組最優(yōu)粒子、全局最優(yōu)粒子、模擬退火溫度；

Step 4：判斷是否符合終止條件。若符合條件輸出最優(yōu)規(guī)劃路徑，否則執(zhí)行Step 5；

Step 5：計(jì)算粒子適應(yīng)度fi（t），更新小組最優(yōu)解和全局最優(yōu)解；

Step 6：更新粒子速度和位置；根據(jù)式（7）、式（8）更新小組最優(yōu)粒子速度和位置，根據(jù)式（10）、式（11）更新小組內(nèi)其他粒子速度和位置；

Step 7：計(jì)算各粒子更新后的適應(yīng)度fi（t+1）和適應(yīng)度變化量Δf；

Step 8：根據(jù)式（12）判斷是否接受粒子更新后的速度和位置；

Step 9：進(jìn)行模擬退火操作，并跳轉(zhuǎn)Step 4；

改進(jìn)后的算法流程圖如圖1 所示。

圖1 基于雞群分組策略的粒子群算法流程圖Fig.1 Flow chart of particle swarm algorithm based on chicken swarm grouping strategy

3 無人機(jī)航跡規(guī)劃代價(jià)函數(shù)

3.1 航程代價(jià)

航程代價(jià)主要指無人機(jī)在飛行過程中的燃油消耗，假設(shè)無人機(jī)在執(zhí)行任務(wù)過程中達(dá)到規(guī)劃速度后保持勻速飛行，故燃油消耗量與無人機(jī)的總航程成正比，航程代價(jià)表示如下：

其中，ε 表示單位航程的燃油消耗量；Qv表示無人機(jī)所攜帶的燃油總量；Li表示第i 段航跡的長度。

3.2 飛行高度代價(jià)

無人機(jī)在飛行過程中，被敵方雷達(dá)探測到的概率與其飛行高度成正比，受地形威脅的概率與飛行高度成反比，為了提高無人機(jī)的生存概率，設(shè)定最高飛行高度Hmax和最低飛行高度Hmin，設(shè)當(dāng)前飛行高度為Hi，飛行高度代價(jià)函數(shù)表示如下：

3.3 威脅代價(jià)

受環(huán)境地形、禁飛區(qū)、防空火力等的影響，無人機(jī)航跡規(guī)劃時(shí)需考慮環(huán)境的威脅代價(jià)，設(shè)在規(guī)劃的第i 段航跡無人機(jī)接近威脅點(diǎn)k，將當(dāng)前航跡段Li分割成m 小段，則威脅點(diǎn)k 對(duì)航跡段Li的威脅代價(jià)函數(shù)表示如下：

式中，ni表示航跡規(guī)劃中的第i 段航跡Li；Pk表示第k 個(gè)威脅點(diǎn)的對(duì)無人機(jī)的毀傷概率；dm，k表示第k 個(gè)威脅點(diǎn)到航跡段Li中第m 小段的距離。

無人機(jī)航跡規(guī)劃受到的總威脅代價(jià)為：

3.4 多無人機(jī)協(xié)同航跡規(guī)劃收益函數(shù)

4 實(shí)驗(yàn)仿真及結(jié)果分析

4.1 實(shí)驗(yàn)仿真

為驗(yàn)證本文設(shè)計(jì)算法的可行性，使用Matlab 軟件對(duì)無人機(jī)三維路徑規(guī)劃進(jìn)行實(shí)驗(yàn)仿真。本次仿真地圖大小設(shè)置為：100 km*150 km*30 km，起飛點(diǎn)坐標(biāo)為（10，90），目標(biāo)點(diǎn)坐標(biāo)為（130，10）。威脅區(qū)域的二維坐標(biāo)參數(shù)如下頁表1 所示。

表1 威脅區(qū)域二維坐標(biāo)參數(shù)Table 1 2-D coordinate parameters of threat area

對(duì)威脅區(qū)域建模，使用粉色部分表示威脅區(qū)域，如圖2 所示。

圖2 三維威脅地形圖Fig.2 Three-dimensional threat topographic map

使用標(biāo)準(zhǔn)粒子群算法對(duì)上述問題進(jìn)行三維路徑規(guī)劃求解作為參考，其參數(shù)設(shè)置為：粒子數(shù)量N=30，最大迭代次數(shù)T=200，學(xué)習(xí)因子c1=c2=2，慣性權(quán)重ω=1，退化率為0.99。

仿真結(jié)果如圖3～圖5 所示。

圖3 二維航跡規(guī)劃圖Fig.3 Two-dimensional route planning diagram

圖4 三維航跡規(guī)劃圖Fig.4 3D route planning diagram

圖5 適應(yīng)度變化曲線Fig.5 Fitness change curve

優(yōu)化后的粒子群算法的參數(shù)設(shè)置為：粒子數(shù)量、最大迭代次數(shù)、學(xué)習(xí)因子、慣性權(quán)重取值、退化率均不變，小組數(shù)量為5，模擬退火初始溫度為400，溫度衰減系數(shù)為0.99。在對(duì)標(biāo)準(zhǔn)粒子群算法增加了雞群分組策略和模擬退火操作后的實(shí)驗(yàn)仿真結(jié)果如圖6～圖8 所示。

圖6 改進(jìn)后的二維航跡規(guī)劃圖Fig.6 Improved 2D route planning diagram

圖7 改進(jìn)后的三維航跡規(guī)劃圖Fig.7 Improved 3D route planning diagram

圖8 改進(jìn)后的適應(yīng)度變化曲線Fig.8 Fitness change curve after improvement

4.2 仿真結(jié)果分析

針對(duì)兩次實(shí)驗(yàn)結(jié)果進(jìn)行分析，可以看出標(biāo)準(zhǔn)粒子群算法規(guī)劃出的航線從兩個(gè)威脅區(qū)域之間穿過，這種方式有較大的風(fēng)險(xiǎn)隱患，容易被偵察探測到。改進(jìn)后的粒子群算法則避免了這種問題，最大程度規(guī)避了威脅區(qū)域，降低了執(zhí)行任務(wù)的風(fēng)險(xiǎn)，同時(shí)改進(jìn)后的粒子群算法規(guī)劃的航跡飛行高度較低，更加貼近山體飛行，能夠大幅降低被敵方地面雷達(dá)探測到的概率。根據(jù)適應(yīng)度曲線的變化可以看出，改進(jìn)后的粒子群算法迭代次數(shù)更多，迭代初期的目標(biāo)函數(shù)值更高，最后收斂的目標(biāo)函數(shù)值幾乎相同，這表明改進(jìn)后的算法搜索了更大的范圍，在全局搜索能力上更強(qiáng)。綜合考慮，改進(jìn)后的粒子群算法規(guī)劃的無人機(jī)航跡更好，驗(yàn)證了算法改進(jìn)的有效性。

在相同的環(huán)境下，分別用兩組算法進(jìn)行30 次的獨(dú)立仿真，對(duì)兩種算法的綜合代價(jià)模型進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如表2 所示。

表2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)Table 2 Statistics of experimental results

對(duì)兩組實(shí)驗(yàn)結(jié)果易知，兩種算法對(duì)無人機(jī)航跡進(jìn)行規(guī)劃時(shí)，最優(yōu)代價(jià)相差不大，但是標(biāo)準(zhǔn)粒子群算法的平均代價(jià)及標(biāo)準(zhǔn)差都不如改進(jìn)后的算法優(yōu)秀，這表明使用改進(jìn)的粒子群算法進(jìn)行航跡規(guī)劃時(shí)尋優(yōu)的穩(wěn)定性更好；改進(jìn)的粒子群算法的平均迭代次數(shù)明顯高于標(biāo)準(zhǔn)粒子群算法，表明改進(jìn)后的算法搜索的范圍更廣，全局搜索能力更強(qiáng)；雖然改進(jìn)后的算法在平均運(yùn)算耗時(shí)上有所增加，但時(shí)間相差不大，總體來看，改進(jìn)后的算法更加適用于無人機(jī)的三維路徑規(guī)劃。

5 結(jié)論

本文針對(duì)無人機(jī)三維路徑規(guī)劃問題，設(shè)計(jì)了一種基于雞群分組優(yōu)化策略的粒子群優(yōu)化算法，在改進(jìn)的算法中加入了模擬退火操作，并通過仿真實(shí)驗(yàn)驗(yàn)證了改進(jìn)后算法的可行性和有效性，相較于標(biāo)準(zhǔn)的粒子群算法，改進(jìn)后的算法在全局搜索能力上更強(qiáng)，尋優(yōu)的穩(wěn)定性更高，對(duì)局部區(qū)域的搜索能力較高，能夠有效地避免陷入局部最優(yōu)、過早成熟等問題，規(guī)劃的無人機(jī)航線更加合理，代價(jià)更優(yōu)。