四種智能仿生學算法的無人機航路規(guī)劃應用對比

王怡翔，李姮，王家怡，張祖銘，葉朝潔，蔡洋洋

（1.桂林電子科技大學 計算機與信息安全學院，廣西 桂林 541004；2.桂林電子科技大學 電子工程與自動化學院，廣西 桂林 541004；3.桂林電子科技大學 生命與環(huán)境科學學院，廣西 桂林 541004）

0 引言

隨著無線電控制技術(shù)的發(fā)展與計算機技術(shù)的興起與融合，輕小型無人機在環(huán)境監(jiān)測、地質(zhì)勘探、城市規(guī)劃以及安防巡檢等眾多工業(yè)領(lǐng)域具有廣闊的發(fā)展空間[1]。執(zhí)飛不同工作任務的工業(yè)無人機工作環(huán)境錯綜復雜，合理快速的航線路徑規(guī)劃可增強無人機在不同應用環(huán)境的時效性、安全性和適應性。而如何根據(jù)外部環(huán)境信息為無人機尋求一個或多個相對最優(yōu)航跡路線，躲避障礙和威脅區(qū)域，是實現(xiàn)無人機航路規(guī)劃的關(guān)鍵。

基于生物群體社會學以及自然規(guī)律的智能仿生學算法具有較強的自適應能力，可解決復雜優(yōu)化等問題。將這些生物群體行為融入到航路規(guī)劃問題的求解過程中，用以進一步提高無人機航路規(guī)劃的性能。其中常見的智能仿生學算法主要包括粒子群算法[2]、遺傳算法[3]、蟻群算法[4]以及人工蜂群算法[5]等。本文分析常見的智能仿生學優(yōu)化技術(shù)的算法原理，對基于智能仿生學算法無人機航路規(guī)劃進行歸納整理。綜合比對各類優(yōu)化算法的優(yōu)缺點，為無人機航路規(guī)劃提供參考。

1 基于粒子群算法的無人機航路規(guī)劃

粒子群算法是受飛鳥集群覓食活動規(guī)律啟發(fā)而提出的一種智能仿生演化算法。該算法以隨機全局搜索為特征，將搜索空間的飛鳥群抽象為粒子，每個粒子包含有適度函數(shù)、確定飛行方向的位移矢量和確定距離的速度矢量等參數(shù)變量，算法實現(xiàn)過程如圖1所示。該算法通過反復迭代更新粒子群，以群體粒子之間的合作與競爭產(chǎn)生的群體智指導優(yōu)化搜索，求解輸出最優(yōu)路徑。

圖1 粒子群算法流程

粒子群算法具有簡潔性、易實現(xiàn)、高精度、參數(shù)便于調(diào)整、運算速度快等優(yōu)點，因而在無人機飛行路線規(guī)劃中得到有廣泛應用。徐利峰等[6]采用混合粒子群算法對植保無人機路徑點進行排序，為農(nóng)作物噴藥的全自動化提供新方向；Góez等[7]采用粒子群優(yōu)化算法分段改變慣性權(quán)重，并采用微控制器對算法改進，為無人機在線航路規(guī)劃技術(shù)提供解決方案。

在規(guī)劃航路的過程中，粒子群算法因算法隨機性較差，導致在迭代過程中容易陷入局部最優(yōu)，使得無人機避障系統(tǒng)無法選取全局最優(yōu)解。如何優(yōu)化粒子群算法，盡可能避免迭代過程陷入局部最優(yōu)值，使之適用于無人機航路規(guī)劃是當下粒子群算法的研究熱點，目前已有眾多研究者對此進行優(yōu)化。趙艷麗等[8]將柯西分布擾動引入量子粒子群算法，提高算法的收斂速度與搜索能力；方群等[9]通過慣性權(quán)值改變算法，提高了無人機三維航跡規(guī)劃算法的穩(wěn)定性，同時避免算法陷入局部最優(yōu)；張建南等[10]將自然選擇思想與粒子群算法結(jié)合，同時引入慣性權(quán)重，縮小了最優(yōu)航線的搜索范圍，為避免算法陷入局部最優(yōu)值提供解決方案。

與其他算法相比，粒子群算法易于建模且便于計算，主要用于實現(xiàn)復雜環(huán)境下無人機的最優(yōu)航路規(guī)劃，但是粒子群算法的輸出結(jié)果易陷入局部最優(yōu)值。對該算法在無人機避障的應用場景中進行改進與優(yōu)化是當下的熱點問題。

2 基于遺傳算法的無人機航路規(guī)劃

遺傳算法是基于生物進化論的自然選擇和遺傳學機理求解最優(yōu)解的智能仿生進化算法，以隨機全局搜索為特點，基于“適者生存”的原則，完成“優(yōu)勝劣汰”的自然選擇并提高種群適應度，其算法實現(xiàn)如圖2所示。該算法通過計算分析無人機航路關(guān)鍵參數(shù)的約束條件，采用對基因編碼種群初始化、對個體性能評價的適應度函數(shù)構(gòu)造與解碼分析的三步驟運算，可在迭代過程中實現(xiàn)自適應，計算輸出無人機最優(yōu)運行軌跡。

圖2 遺傳算法實現(xiàn)流程

遺傳算法作為一種非確定性的擬自然全局搜索算法，算法簡單可解決非線性問題，為復雜系統(tǒng)的優(yōu)化提供了一種新方法。目前，眾多研究者將遺傳算法融入到無人機航路規(guī)劃中：王娜等[11]將遺傳算法應用到農(nóng)用無人機航路規(guī)劃中，避免了無人機誤撞障礙物的現(xiàn)象發(fā)生；方偉等[12]采用左、右部分匹配交叉法改良染色體交叉方式，并且采用翻轉(zhuǎn)突變法與兩點交換法提高染色體變異的多樣性，有效解決了無人機對海偵察航路規(guī)劃問題；Vahid等[13]將并行遺傳算法應用于多維控制器環(huán)境中，實現(xiàn)無人機平滑航路規(guī)劃。

在無人機避障場景中，遺傳算法的局部尋優(yōu)精度較低，穩(wěn)定性較差。針對此問題，眾多學者充分利用遺傳算法具備良好擴展性的特點，將其與其他算法進行融合，為算法的改進提供新的解決方案：魚佳欣等[14]引進移民算子與人工選擇算子實現(xiàn)多種群協(xié)同進化，提高了無人機航路規(guī)劃的效率以及穩(wěn)定性；李楠等[15]通過對自適應度高的個體進行復制增加改進選擇過程，提高尋優(yōu)精度的同時增快了算法的迭代速度，為無人機三維航路的避障及航路規(guī)劃提供解決方案；Yuan等[16]采用優(yōu)良點集算法改良種群初始化，降低無人機航路規(guī)劃陷入局部最優(yōu)的風險。

遺傳算法在無人機航路規(guī)劃中具備良好的擴展性，可與其他算法相結(jié)合且不受到應用領(lǐng)域限制，具備快速搜尋能力。但是遺傳算法實現(xiàn)過程復雜，搜索效率相對較低，其最終結(jié)果對變異率、交叉率以及適應度等參數(shù)具有較強的依賴，因而如何在加快求解速度的同時提高優(yōu)良個體的保留率是當下基于遺傳算法的無人機航路規(guī)劃中需解決的問題。

3 基于蟻群算法的無人機航路規(guī)劃

蟻群算法是來源自螞蟻集體尋徑覓食行為啟發(fā)而提出的智能仿生學算法。該算法模擬螞蟻選擇最短路徑的行為過程，其采用分布式種群搜索策略求解問題的最優(yōu)解，算法流程如圖3所示。該算法實現(xiàn)主要分為數(shù)據(jù)初始化、信息素更新以及路徑選擇3個部分。其中數(shù)據(jù)初始化負責實現(xiàn)環(huán)境變量的設(shè)置以及新代螞蟻的生成；信息素更新依賴預先設(shè)置的限制性條件，滿足率越高，信息素生成越多。其中信息素是蟻群之間進行溝通的化學物質(zhì)，負責導向蟻群的行進路線；以路徑上的信息素含量為依據(jù)進行路徑選擇，對于信息素含量越高的路徑，該路徑的被選擇概率越大，最終通過循環(huán)判斷實現(xiàn)最優(yōu)航線的確定。

圖3 蟻群算法實現(xiàn)流程

蟻群算法是無人機航路規(guī)劃中的常用算法，在無人機航路規(guī)劃已取得廣泛應用：唐立等[17]將泰森多邊形作為算法的初始解，以躲避山區(qū)障礙物為限制性條件，提高無人機在山區(qū)對障礙物的躲避能力；王宇等[18]將無人機在二維坐標的作業(yè)路徑離散化并采用插值的方式求取其三維作業(yè)航跡，提高了植保無人機應對含有障礙物的復雜地形的適應能力；袁夢婷等[19]采用綜合啟發(fā)的方式改良蟻群算法的狀態(tài)轉(zhuǎn)移函數(shù)，通過離散化的方式規(guī)劃無人機遇到障礙時的解脫路徑；Guo等[20]在信息素更新規(guī)則中加入碰撞威脅代價和路徑長度，解決了傳統(tǒng)蟻群算法僅可優(yōu)化單個目標的問題，為無人機在復雜環(huán)境下障礙躲避提供一種可行有效的解決方案。

蟻群算法采用局部正反饋機制，不易陷入局部最優(yōu)，但是該算法收斂速度較慢，尋優(yōu)時間較長。提高蟻群算法的收斂速度，降低算法運行時間是此算法的未來發(fā)展方向。眾多研究者對于該算法應用于無人機航路規(guī)劃中提出對應的解決方案：曹建秋等[21]使用A*算法實現(xiàn)初始化并且采用Dubins曲線對三維路線進行平滑處理，提高了收斂速度的同時實現(xiàn)可針對多目標的無人機三維航路規(guī)劃；Yang等[22]將蟻群算法應用到數(shù)字地形建模，在保證不損壞模型的情況下，大幅提高了圖像采集的工作效率。

蟻群算法采用了分布式正反饋機制感知局部信息，與其他智能仿生學算法相比，蟻群算法的計算效率高，更適用于三維地圖的無人機航路規(guī)劃。但是該算法的收斂性易受到初始化參數(shù)的影響，容易出現(xiàn)停滯現(xiàn)象。

4 基于人工蜂群算法的無人機航路規(guī)劃

人工蜂群算法是啟發(fā)于蜂群自發(fā)性分工協(xié)作高效采蜜行為而提出的智能仿生學算法。該算法將蜜源的位置作為問題的可行解，模擬蜜蜂采蜜機理可實現(xiàn)局部尋優(yōu)。蜂種之間的身份轉(zhuǎn)換是該算法的核心部分，其實現(xiàn)原理如圖4所示。在算法中設(shè)置了觀察、偵察以及采蜜共三個不同類型的蜂種，其中采蜜蜂負責招募觀察蜂并收集問題的可行解；觀察蜂可接收采蜜蜂傳播的信息，隨機跟隨一只采蜜蜂并實現(xiàn)身份轉(zhuǎn)換加入其中；偵察蜂隨機生成滿足條件的可行解，可實現(xiàn)結(jié)果的多樣性。

圖4 人工蜂群算法蜂種轉(zhuǎn)換原理

人工蜂群算法只以適應度函數(shù)作為搜索過程中的進化依據(jù)，具備易于操作、搜索精度較高、控制參數(shù)簡單、魯棒性較強的特點。目前人工蜂群算法已被廣泛應用于無人機航路規(guī)劃中：徐流沙等[23]采用差分進化算法對偵察階段進行改良，為高維度無人機航線規(guī)劃提供了有效的解決方案；Ding等[24]提出了一種概率縮放自適應人工蜂群算法，實現(xiàn)無人機避障的同時極大地減少了燃油的消耗。

人工蜂群算法參數(shù)依賴性較低，算法實現(xiàn)相對簡單，但是該算法在后期存在易陷入局部最優(yōu)且收斂速度慢等問題。如何對算法進行優(yōu)化，提高后期收斂速度是當前人工蜂群算法的熱點問題。目前已經(jīng)有眾多研究者對該算法在無人機避障的應用中進行改良：劉琨等[25]將禁忌搜索策略引入到偵察蜂中的搜索階段，避免算法提前陷入局部最優(yōu)解，提高了無人機的避障能力；王慶海等[26]通過引入動態(tài)評價策略以及Metropolis準則，有效改進了傳統(tǒng)算法后期收斂速度較慢的問題，提高了無人機三維航線規(guī)劃的魯棒性以及收斂速度。

在無人機航路規(guī)劃的應用場景下，人工蜂群算法相比于其他智能仿生學算法，具有操作簡單、穩(wěn)定性較強以及應用范圍廣等優(yōu)點。然而該算法在迭代的過程同樣會陷入局部最優(yōu)，對此類問題的解決是當下基于人工蜂群算法的無人機航路規(guī)劃的關(guān)鍵。

5 結(jié)語

相比于其他優(yōu)化算法，智能仿生學算法具有魯棒性強、靈活性高以及優(yōu)化結(jié)果全面等優(yōu)點，目前此類算法在無人機航路規(guī)劃中得以廣泛應用。綜上所述，4種常見的智能仿生學算法，都適用二/三維度，都是全局搜索方式。優(yōu)點方面，粒子群算法復雜度低，具有記憶性，航路規(guī)劃速度快；遺傳算法具有擴展性，適合復雜航路規(guī)劃，搜索能力強；蟻群算法采用正反饋機制，魯棒性強，航路規(guī)劃準確度高；人工蜂群算法操作簡單，易于實現(xiàn)，參數(shù)依賴性低。缺點方面，粒子群算法不確定性較大，容易陷入局部最優(yōu)，航路規(guī)劃準確性低；遺傳算法尋優(yōu)精度低，穩(wěn)定性差，控制參數(shù)較多，航路規(guī)劃速度慢；蟻群算法收斂性較低，航路規(guī)劃速度慢，易出現(xiàn)停滯現(xiàn)象；人工蜂群算法易陷入局部最優(yōu)。

智能仿生學算法在滿足限制性條件的同時可實現(xiàn)無人機航線的規(guī)劃，但是無人機航路規(guī)劃實現(xiàn)會受到包括氣象，地勢以及飛行高度等限制性飛行條件約束，存在多樣性與不確定性。單一的智能仿生學算法因算法原理不同導致本身性質(zhì)有所差異，只能在特定條件下做出最優(yōu)航路規(guī)劃決策。組合優(yōu)化算法將不同的智能仿生學算法進行調(diào)整與融合，可以提高算法的適應度，是未來無人機航路規(guī)劃的發(fā)展趨勢。