麻雀搜索算法在路徑規劃的應用

舒 紅

（陜西工業職業技術學院 陜西 咸陽 712000）

0 引言

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

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

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

1 蟻群算法

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

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

2 麻雀搜索算法

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

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

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

其中，d為未優化問題的變量維度數，n是麻雀的數量。進而所有麻雀的適應度值表示為式（2）。

其中，f為適應度值。

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

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

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

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

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

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

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

3 算法實現步驟

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

圖1 麻雀搜索算法流程圖

算法實現步驟主要分為以下9 個步驟：

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

（2）設置種群中發現者和加入者的比例，開始進行第一次迭代。

（3）發現者讀取當前所在柵格點的R2預警值，使用第（3）式更新發現者的位置。

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

（5）根據式（5）隨機更新負責偵察預警的麻雀位置。

（6）迭代結果是當前更新的位置，再判斷新位置是否比舊位置更優。

（7）若新位置更優，則替代舊位置。

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

（9）最終輸出麻雀個體所處最優位置和最佳適應度數值。

4 仿真實驗結果

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

圖2 蟻群算法尋優圖

圖3 麻雀搜索算法尋優圖

圖4 收斂曲線對比圖

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

表1 算法尋優結果匯總表

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

5 結論

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