基于改進麻雀搜索算法的路徑規(guī)劃*

司馬燊,劉漢明,?,劉財輝,郭 港,余 聰,胡鵬程

(1.贛南師范大學 數(shù)學與計算機科學學院;2.江西省數(shù)值模擬與仿真技術(shù)重點實驗室,江西 贛州 341000)

0 引言

路徑規(guī)劃[1]算法可分為兩大類,一種是以A*、快速搜索隨機樹[2-4]等為主的啟發(fā)式算法,另一種是以蟻群算法(Ant colony optimization,ACO)[5]、遺傳算法(Genetic Algorithms,GA)[6]、模擬退火算法(Simulated Annealing,SA)[6]、麻雀搜索算法(Sparrow search algorithm,SSA)[7]等為代表的群智能算法.其中,啟發(fā)式算法存在搜索時間長、全局遍歷開銷大、計算效率低等問題.群智能算法由于尋優(yōu)能力強、實現(xiàn)容易等優(yōu)點被廣泛使用,如工業(yè)優(yōu)化[8]、路徑規(guī)劃[9-15]、優(yōu)化計算[16]等領(lǐng)域,這些領(lǐng)域中也經(jīng)?？吹铰槿杆惴╗17]的身影.在群智能路徑規(guī)劃領(lǐng)域,MIAO[12]等提出基于自適應(yīng)蟻群算法的室內(nèi)移動機器人路徑規(guī)劃算法,采用自適應(yīng)啟發(fā)因子和信息素揮發(fā)因子來平衡全局搜索和算法的收斂能力.MACTT[18]等人提出分層的路徑規(guī)劃方法,平衡路徑的平滑度和最短路徑.以上文獻雖然取得了不錯的效果,但是搜尋實驗地圖中的障礙物分布較為集中,并沒有真正平衡算法全局和局部搜索.

受上述文獻的啟發(fā),本文提出基于適應(yīng)度值變化的自適應(yīng)麻雀搜索算法(Adaptive sparrow search algorithm,ASSA)的移動機器人(Automated guided vehicle, AGV)路徑規(guī)劃.

1 麻雀搜索算法基本原理

SSA把麻雀分為發(fā)現(xiàn)者、追隨者和預(yù)警者三種角色進行尋優(yōu).每只麻雀代表當前問題的可行解,麻雀的位置可表示為

(1)

其中n表示群體中麻雀的數(shù)量,d是要優(yōu)化的變量的維度.麻雀和食物之間的匹配程度用適應(yīng)度衡量,其適應(yīng)度值為

(2)

發(fā)現(xiàn)者第t+1輪迭代時的位置:

(3)

一旦發(fā)現(xiàn)者找到更好的食物,他們就會立即前往相應(yīng)的位置進行競爭.追隨者第t+1輪迭代時的位置

(4)

另外,麻雀群體中的預(yù)警者對天敵作出預(yù)警,使得發(fā)現(xiàn)者帶領(lǐng)群體飛向更安全的地方.預(yù)警者t+1輪迭代時的位置

(5)

2 改進的麻雀搜索算法

2.1 發(fā)現(xiàn)者更新策略

由式(3)知,R2和ST的取值決定其是把群體帶到安全區(qū)域還是在原有區(qū)域繼續(xù)搜索,即全局搜索或局部搜索.現(xiàn)有研究大多集中在更新策略[19-22],在ST的取值上研究不多.結(jié)合本文研究的具體實例,將適應(yīng)度值變化與ST的更新進行關(guān)聯(lián),即在迭代過程中最優(yōu)適應(yīng)度值發(fā)生變化時(麻雀找到了更好的食物),將ST的取值擴大,促使發(fā)現(xiàn)者在當前迭代中偏向于局部搜索,加速種群的收斂速度,反之則偏向于全局搜索,進一步擴大搜索范圍.具體更新策略為

(6)

2.2 追隨者更新策略

SSA追隨者以固定的n/2為更新策略邊界,限制了算法的適應(yīng)性,同時A+的復(fù)雜運算拖慢了算法的運算速度.這里將式(4)的更新策略邊界改為B,隨迭代數(shù)變化而變化

(7)

圖1 改進后的算法流程

2.3 隨機保留策略

SSA的更新策略在迭代前期效果較好,但中后期,麻雀均聚集在最優(yōu)解附近,使種群趨同性嚴重,增加了陷入局部最優(yōu)的風險.本文以一定概率隨機地保留意識到危險的麻雀和劣于上一輪迭代的追隨者的位置不變,有助于提高種群多樣性,降低陷入局部最優(yōu)的風險.隨機保留策略為

(9)

2.4 改進后的算法流程(圖1)

3 實驗結(jié)果與分析

為驗證算法改進在理論上可行,除節(jié)3.4算法應(yīng)用實驗外,其它實驗所使用的測試集為基準公開測試集[23]中的11個(表1).實驗環(huán)境為Windows11 64位、內(nèi)存16GB、Intel Core i7-10870H.

表1 基準測試函數(shù)

3.1 ξ參數(shù)優(yōu)化

取ξ為0.1-0.9(步長0.1)的ASSA實驗結(jié)果如表2、表3所示,其中Best和Mean分別表示獲得最好的最優(yōu)值、均值的數(shù)量.

表2 常數(shù)ξ優(yōu)化實驗結(jié)果*

*較好的結(jié)果加粗傾斜表示,表4同.

表3 常數(shù)ξ優(yōu)化實驗結(jié)果統(tǒng)計*

*各算法在11個測試函數(shù)中取得最好的最優(yōu)值和均值的函數(shù)數(shù)量.

由表2、表3可知,參數(shù)ξ為0.4左右時效果較優(yōu).

3.2 性能比較

為驗證ASSA的性能,把其與麻雀算法(Sparrow search algorithm,SSA)、粒子群算法(Particle swarm optimization,PSO)、灰狼算法(Grey wolf optimization,GWO)、正余弦算法(Sine cosine algorithm,SCA)、樹種優(yōu)化算法(Tree seed algorithm,TSA)和風驅(qū)動算法(Wind driven optimization,WDO) 進行對比實驗.PSO參數(shù)的c1=2,c2=2,ω=2,SCA的a=2,TSA的st=0.1,WDO的rt=0.3,g=0.2,alp=0.4,ω=0.3,GWO的αinitial=2,αend=0,SSA的PD=0.2,SD=0.2.所有算法的種群規(guī)模為50、最大迭代次數(shù)為100,進行30次獨立實驗,取各算法求解的最優(yōu)值(Best)、最差值(Worst)、均值(Mean)及標準差(Std),實驗結(jié)果示于表4,同時表5給出了各算法平均性能優(yōu)于其他算法的數(shù)量.

表4 對比實驗結(jié)果

表4顯示,雖然SSA與ASSA一樣都能在實驗中取得相同的最優(yōu)值(Best),但在算法的平均性能(Mean)上SSA均劣于ASSA.另外,表5顯示ASSA的平均性能在所有測試算法中最優(yōu).

3.3 收斂速度比較

為直觀對比各算法收斂速度,繪制30次實驗中各輪迭代適應(yīng)度值均值的變化曲線(圖2-12),為了更好地顯示與SSA的差異,單獨繪制ASSA與SSA對比.

圖2 F1平均適應(yīng)度曲線 圖3 F2平均適應(yīng)度曲線

圖4 F3平均適應(yīng)度曲線 圖5 F4平均適應(yīng)度曲線

圖6 F5平均適應(yīng)度曲線 圖7 F6平均適應(yīng)度曲線

圖8 F7平均適應(yīng)度曲線 圖9 F8平均適應(yīng)度曲線

圖10 F9平均適應(yīng)度曲線 圖11 F10平均適應(yīng)度曲線

根據(jù)圖2-12函數(shù)平均適應(yīng)度值收斂曲線知,

圖12 F11平均適應(yīng)度曲線

不論是在單峰還是多峰函數(shù),改進后的ASSA算法在不降低尋優(yōu)能力的前提下獲得了更快的收斂速度,收斂到同等精度所需的迭代次數(shù)更少,尤其在迭代前期收斂速度增加更為明顯,說明對麻雀算法在發(fā)現(xiàn)者和追隨者的策略選擇閾值上改進有效,隨著算法迭代到后期,ASSA和SSA收斂趨勢基本趨同,說明隨機舍棄策略并未對算法收斂產(chǎn)生較明顯的負面影響.

3.4 移動機器人路徑規(guī)劃

為驗證ASSA在移動機器人路徑規(guī)劃上的效果,將其與原算法SSA應(yīng)用于柵格地圖下進行路徑規(guī)劃,實驗環(huán)境與理論驗證相同,柵格地圖為隨機生成.

3.4.1 任務(wù)環(huán)境建模

在進行機器人路徑規(guī)劃前選用柵格地圖法[24]建模.這里用矩形柵格表示地圖,地圖中有隨機分布的障礙物(藍色柵格)、可行區(qū)域(白色柵格),并包含起點(綠色柵格)和終點(紅色柵格).除起點和終點外,地圖中每一個柵格存在關(guān)系

(10)

3.4.2 代價函數(shù)

路徑規(guī)劃常將路徑長度作為其優(yōu)劣程度的評價指標,故本文路徑長度的代價函數(shù)為

(11)

n表示生成路徑中柵格的個數(shù).

表6 路徑規(guī)劃參數(shù)

表7 路徑規(guī)劃結(jié)果

3.4.3 實驗參數(shù)說明

柵格地圖大小、麻雀數(shù)量、最大迭代次數(shù)等參數(shù)如表6所示,均進行30次獨立實驗,實驗要求在每一列選擇一個可行柵格直至終點.

3.4.4 實驗結(jié)果與分析

實驗結(jié)果如表7及圖13-18所示.

根據(jù)表7中的實驗結(jié)果知,在三類大小地圖中ASSA規(guī)劃出來的平均路徑長度均小于SSA,證明在路徑長度上ASSA整體性能優(yōu)于SSA.,結(jié)合圖13-18的兩類算法規(guī)劃的路徑圖,ASSA規(guī)劃出的路徑比SSA更平滑.但實驗表明,隨著地圖的增大、障礙物分布的復(fù)雜程度上升,不論是ASSA還是SSA都無法憑借自身單一的算法找到最優(yōu)路徑.故此,在后續(xù)的研究上除算法改進外還需考慮柵格地圖處理.

圖13 15×20地圖的ASSA最優(yōu)路徑 圖14 15×20地圖的SSA算法最優(yōu)路徑 圖15 20×30地圖的ASSA算法最優(yōu)路徑

圖16 20×30地圖的SSA算法最優(yōu)路徑 圖17 30×50地圖的ASSA算法最優(yōu)路徑 圖18 30×50地圖的ASSA算法最優(yōu)路徑

4 結(jié)論

對于SSA算法存在的易陷入局部最優(yōu)等問題,本文提出了改進的算法ASSA.該算法通過動態(tài)調(diào)整發(fā)現(xiàn)者的預(yù)警值、追隨者的邊界值及隨機保留追隨者和預(yù)警者非最優(yōu)位置等策略提高了算法的全局尋優(yōu)能力,降低了算法陷入局部最優(yōu)的概率,提升了算法整體的尋優(yōu)效率和精度.與6個常用算法在11個基準測試函數(shù)的比較實驗結(jié)果表明,相比于SSA,ASSA具有更好的性能和更快的收斂速度及更強的魯棒性,綜合性能上有較大的提升,并在路徑規(guī)劃中取得了較好的結(jié)果.但大規(guī)模地圖、障礙物分布復(fù)雜的情況下, ASSA與SSA一樣,無法獲得最優(yōu)路徑,有待于后續(xù)的進一步研究.