麻雀搜索算法在路徑規(guī)劃的應(yīng)用

舒 紅

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

0 引言

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

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

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

1 蟻群算法

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

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

2 麻雀搜索算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 麻雀搜索算法流程圖

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)結(jié)果

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

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

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

圖4 收斂曲線對(duì)比圖

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

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

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

5 結(jié)論

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