王怡翔，李?yuàn)跫意?，張祖銘，葉朝潔，蔡洋洋

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

0 引言

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

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

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

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

圖1 粒子群算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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

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