舒 紅

（陜西工業(yè)職業(yè)技術(shù)學(xué)院 陜西 咸陽 712000）

0 引言

無論在汽車行業(yè)，還是移動機器人行業(yè)，路徑規(guī)劃技術(shù)都占有核心的地位，且為該行業(yè)研究的關(guān)鍵問題。從數(shù)學(xué)角度出發(fā)，路徑規(guī)劃是一個優(yōu)化問題，但是此問題具有復(fù)雜性、約束性等特點。因此，路徑規(guī)劃一直是研究人員的熱點問題。

從掌握的環(huán)境信息程度不同，可將路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃。若在已知所有環(huán)境信息的情況下完成路徑規(guī)劃，稱為全局路徑規(guī)劃。若在只知道局部環(huán)境信息或者完全不知道環(huán)境信息的情況下完成路徑規(guī)劃，稱為局部路徑規(guī)劃。兩種路徑規(guī)劃的主要不同點在于：全局路徑規(guī)劃的關(guān)鍵在于規(guī)劃出全環(huán)境的最優(yōu)路徑，而局部路徑規(guī)劃的關(guān)鍵在于利用汽車或者機器人本身的傳感器躲避障礙。本文探討全局路徑規(guī)劃的情況。

在近一個世紀(jì)的時間里，國內(nèi)外研究人員相繼提出很多有效路徑規(guī)劃的方法，例如模糊邏輯、人工神經(jīng)網(wǎng)絡(luò)、人工勢場法等。在設(shè)定的環(huán)境下，這些方法可以得到較好的效果，但是隨著問題越來越復(fù)雜，傳統(tǒng)方法具有復(fù)雜度高、穩(wěn)定性不好、效率低等缺點，無法滿足現(xiàn)階段對路徑規(guī)劃方面的要求。近些年來，隨著人工智能技術(shù)的提高，智能優(yōu)化算法已成為解決路徑規(guī)劃的主要方法，例如蟻群算法、粒子群算法、遺傳算法，這些方法都優(yōu)于傳統(tǒng)方法。因為該類算法都可以在規(guī)定的具有障礙物空間內(nèi)搜索最佳路徑。

1 蟻群算法

智能優(yōu)化算法的關(guān)鍵是遺傳進化過程，方法是受自然選擇和生物進化模型的啟發(fā)。在路徑規(guī)劃問題中蟻群算法（ACO）應(yīng)用最為廣泛，文獻也是最多。MANIEZZO 等[1]學(xué)者受在自然界中螞蟻覓食過程的啟發(fā)，提出螞蟻系統(tǒng)，并將其應(yīng)用到實際尋優(yōu)路徑的環(huán)境中得到很好的結(jié)果。后來有STUTZLE 等[2]提出了改進的蟻群算法。例如為了防止算法停滯不前，最大最小螞蟻系統(tǒng)提出了信息素的上下限。BULLNHEIMER[3]提出給不同路徑長度設(shè)立不同權(quán)重的螞蟻系統(tǒng)，可提高傳統(tǒng)蟻群算法的收斂速度。近年來，相關(guān)研究人員將傳統(tǒng)蟻群算法進行改進并將其應(yīng)用于不同行業(yè)，通過改變自適應(yīng)變化揮發(fā)度的相關(guān)參數(shù)，來克服蟻群算法易陷入局部最優(yōu)的問題[4]，以及通過改進啟發(fā)函數(shù)和信息素揮發(fā)因子提升螞蟻搜索的目的性及算法的運算速度[5]。

經(jīng)過改進之后的蟻群算法解決了路徑規(guī)劃的一些問題，其本身收斂性加快，局部最小問題大幅度減少。但是現(xiàn)實中的路徑規(guī)劃問題有很多類型，且一部分較為復(fù)雜。所以，不可能有一種算法可以解決所有類型的問題，也不存在可以解決所有問題的算法。因此，需要不斷學(xué)習(xí)新的算法，且將新算法應(yīng)用在實際問題中，與已有算法結(jié)果進行對比，再進行持續(xù)改進。張恩浩[6]在2020年提出麻雀搜索算法（SSA），此算法是受麻雀種群覓食過程和反捕食行為的啟發(fā)而提出。該算法具有搜索精度高、收斂速度快、高穩(wěn)定性等明顯的優(yōu)勢，很多學(xué)者已經(jīng)對其進行研究并應(yīng)用在很多行業(yè)中。本文將其應(yīng)用在路徑規(guī)劃的問題中。

2 麻雀搜索算法

麻雀搜索算法的基本思想如下：在算法中，主要有三個類型的個體：發(fā)現(xiàn)者、跟隨者以及警戒者。發(fā)現(xiàn)者是整個種群搜索食物并提供食物方向的個體，而跟隨者（加入者）是跟隨發(fā)現(xiàn)者的方向進行尋找食物的個體，警戒者是負責(zé)監(jiān)視尋找食物的整個區(qū)域的個體，一般是處在群體邊緣的麻雀，若遇到危險，警戒者則會發(fā)布信號，其他個體則會快速向安全地方前進。其中，警戒者一般占種群個數(shù)的10%～20%。三種個體通過不斷更新自己的位置，最后獲得食物[7]。

發(fā)現(xiàn)者一般是整個種群中能源儲備較高的個體，給加入者提供尋找食物的方向。建立模型的過程中，每個個體的適應(yīng)度值決定著儲備能量的高低。若警戒者意識到危險，則開始發(fā)出危險信號。若危險值大于安全值時，發(fā)現(xiàn)者將立刻帶領(lǐng)加入者到別的安全區(qū)域找尋食物。其中發(fā)現(xiàn)者和加入者的個體不是固定身份，會動態(tài)變化。只要可以找到更好的食物，每個個體都可以轉(zhuǎn)化為發(fā)現(xiàn)者身份，但是兩類個體在整個種群的比例不會變化。即一個麻雀變?yōu)榘l(fā)現(xiàn)者意味著另外一個麻雀成為加入者。且加入者能量儲備越低，它們的覓食位置也越差。一些非常饑餓的加入者可能為了獲取更多的食物，飛到其他地區(qū)尋找食物。

在尋找食物的過程中，加入者不僅可以找到發(fā)現(xiàn)者發(fā)現(xiàn)最好食物的位置，獲得食物，而且能量儲備較足的加入者對于發(fā)現(xiàn)者也存在危險性，加入者不斷監(jiān)視可找到最好食物的發(fā)現(xiàn)者位置，進而搶奪食物資源，提高自身的捕食率。而若遇到危險時，位于群體最外側(cè)的麻雀很快移動到安全地方，處于種群中間位置的麻雀也會隨機變動位置。所以種群的每個麻雀位置都會隨時變化。本文將每個麻雀的位置用數(shù)學(xué)符號表示為式（1）。

其中，d為未優(yōu)化問題的變量維度數(shù)，n是麻雀的數(shù)量。進而所有麻雀的適應(yīng)度值表示為式（2）。

其中，f為適應(yīng)度值。

在算法中，發(fā)現(xiàn)者若有較高的適應(yīng)度值，則在搜索中會先找到食物。因為發(fā)現(xiàn)者需要為整個群體的麻雀覓食，且需要為加入者提供食物的方向。所以，發(fā)現(xiàn)者尋找食物的范圍比加入者更大。根據(jù)式（1）和式（2），發(fā)現(xiàn)者在每次迭代的過程中的位置更新表示為式（3）。

其中，t指當(dāng)前的迭代數(shù)，j=1,2,3…d。itermax指最大迭代次數(shù)。指第i個麻雀在第j維的位置信息。a∈[0，1]為隨機數(shù)。R2∈[0，1]指預(yù)警值，ST∈[0.5,1]指安全值。Q為服從正態(tài)分布的隨機數(shù)。L為1×d1×d 的矩陣，該矩陣中每個元素都是1。

式（3）中R2＜ST，指當(dāng)前的周圍環(huán)境沒有危險，發(fā)現(xiàn)者可放心地進行搜索。當(dāng)R2≥ST時，指群體中的邊緣麻雀已經(jīng)具有危險，并需要向群體的其他麻雀發(fā)出警示信號，全部麻雀都需迅速飛到安全區(qū)域進行尋找食物。

麻雀群體在尋找食物的過程中，有一些加入者隨時盯著發(fā)現(xiàn)者。一旦知道發(fā)現(xiàn)者找到了更好的食物，就會立刻離開所在位置去爭搶食物。如果這些加入者贏了，就可以獲得發(fā)現(xiàn)者的食物，否則這些加入者繼續(xù)使用式（4）進行更新位置：

其中，XP指發(fā)現(xiàn)者當(dāng)前占據(jù)的最優(yōu)位置，Xworst指目前全局最差的位置。A為一個1×d的矩陣，將每個元素隨機賦值為1 或-1。當(dāng)i＞n/2 時，說明第i 個加入者處于十分饑餓的狀態(tài)，適應(yīng)度值較低，且沒有獲得食物，需要立即飛向其他地方尋找食物，獲得能量。

在仿真實驗中，一般假設(shè)屬于警戒者的麻雀占10%到20%，其初始位置是隨機產(chǎn)生的。警戒者的位置更新的數(shù)學(xué)表達式為式（5）：

式中，Xbest指目前全局最優(yōu)位置。β指步長控制參數(shù)，一般是服從正態(tài)分布的隨機數(shù)，其均值為0，方差為1。fi指麻雀個體的目前適應(yīng)度值。fg是當(dāng)前全局位置最佳適應(yīng)度值，fw是當(dāng)前全局位置最差的適應(yīng)度值。為了避免分母為零，ε為隨機一個常數(shù)。fi＞fg指麻雀當(dāng)前正處在群體的邊緣，非常容易受到危險者的攻擊。Xbest指處在這個位置的麻雀是十分安全的，也是群體中最好的位置。fi=fg指處在群體中間的麻雀感受到了危險，為了減少該類麻雀被害的危險，需要立刻靠近其他麻雀。K∈[-1,1]中的隨機數(shù)，指步長控制參數(shù)[8-10]。

3 算法實現(xiàn)步驟

根據(jù)麻雀搜索算法的原理，梳理該算法的流程圖見圖1。

圖1 麻雀搜索算法流程圖

算法實現(xiàn)步驟主要分為以下9 個步驟：

（1）初始化種群，定義最大迭代次數(shù)、種群大小、預(yù)警值、安全閾值等基本參數(shù)。

（2）設(shè)置種群中發(fā)現(xiàn)者和加入者的比例，開始進行第一次迭代。

（3）發(fā)現(xiàn)者讀取當(dāng)前所在柵格點的R2預(yù)警值，使用第（3）式更新發(fā)現(xiàn)者的位置。

（4）根據(jù)第（4）式更新追隨者的位置。

（5）根據(jù)式（5）隨機更新負責(zé)偵察預(yù)警的麻雀位置。

（6）迭代結(jié)果是當(dāng)前更新的位置，再判斷新位置是否比舊位置更優(yōu)。

（7）若新位置更優(yōu)，則替代舊位置。

（8）否則重復(fù)進行第（3）步驟到第（7）步驟。

（9）最終輸出麻雀個體所處最優(yōu)位置和最佳適應(yīng)度數(shù)值。

4 仿真實驗結(jié)果

為了進一步驗證麻雀搜索算法的路徑規(guī)劃能力，本文對已知環(huán)境使用柵格法建模，使用MATLAB R2018b 仿真軟件進行仿真，為了符合更多機器人和更多復(fù)雜環(huán)境下的路徑規(guī)劃，兩種算法都規(guī)定種群只在四個方向（上、下、左、右）行走。兩種算法的初始種群數(shù)量都是20，設(shè)置的最大迭代次數(shù)都是100。其中麻雀搜索算法的發(fā)現(xiàn)者比例為70%，S 為起點，E 為終點。為了驗證算法結(jié)果不具有偶然性，每個算法在固定參數(shù)后都會運行30 次，取平均值。兩種算法最終的路徑尋優(yōu)結(jié)果及收斂性如圖2～圖4所示。

圖2 蟻群算法尋優(yōu)圖

圖3 麻雀搜索算法尋優(yōu)圖

圖4 收斂曲線對比圖

在30 次的仿真實驗后，兩種算法在20×20 的柵格地圖下的平均最優(yōu)路徑長度、平均最優(yōu)路徑拐點個數(shù)以及平均最優(yōu)路徑搜索時間進行匯總對比，見表1所示：

表1 算法尋優(yōu)結(jié)果匯總表

根據(jù)以上圖表，對仿真結(jié)果進行分析，由圖2、圖3及表1可以明顯看出麻雀搜索算法相較于蟻群算法最優(yōu)路徑長度縮短10%，且拐點個數(shù)也縮短了35%，完美避開了多障礙物的中心區(qū)域，所以麻雀搜索算法的全局搜索能力優(yōu)于蟻群算法。在最優(yōu)路徑搜索時間方面，麻雀搜索算法運行時間節(jié)省約68%。通過圖3的收斂曲線對比圖，在最大迭代次數(shù)相同情況下，麻雀搜索算法在迭代10 次已經(jīng)趨于穩(wěn)定，蟻群算法在迭代20 次左右才趨于穩(wěn)定。通過以上四個角度分析，麻雀搜索算法明顯優(yōu)于蟻群算法的尋優(yōu)能力，所以麻雀搜索算法更適合在障礙物復(fù)雜的環(huán)境下找尋最優(yōu)路徑。

5 結(jié)論

本文仔細分析了麻雀搜索算法的步驟和算法流程，將算法應(yīng)用于路徑規(guī)劃問題中，可有效避開復(fù)雜障礙物區(qū)域，且在路徑規(guī)劃方面有著較好的表現(xiàn)。而且與基本蟻群算法在同一環(huán)境下的路徑規(guī)劃結(jié)果進行比較，無論是最優(yōu)路徑長短、拐點個數(shù)及尋優(yōu)時間，麻雀搜索算法的結(jié)果都明顯優(yōu)于蟻群算法。后續(xù)研究將把麻雀搜索算法的局部最優(yōu)問題進行改進，也將在不同障礙物環(huán)境下的搜尋時間進行研究，也盡可能提升此算法的運行速度，節(jié)約搜索時間。與此同時，對設(shè)置R2預(yù)警值與ST安全值與實際環(huán)境進行結(jié)合，可將此算法應(yīng)用到更多實際工程優(yōu)化問題中。