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

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

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

0 引言

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

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

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

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

圖1 粒子群算法流程

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

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

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

2 基于遺傳算法的無人機航路規劃

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

圖2 遺傳算法實現流程

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

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

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

3 基于蟻群算法的無人機航路規劃

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

圖3 蟻群算法實現流程

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

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

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

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

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

圖4 人工蜂群算法蜂種轉換原理

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

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

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

5 結語

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

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