基于墜落機制的混沌麻雀算法AGV路徑規(guī)劃＊

李一銘 王跟成

（①西藏民族大學(xué)信息工程學(xué)院，陜西 咸陽 712082；②西藏自治區(qū)光信息處理與可視化技術(shù)重點實驗室，陜西 咸陽 712082；③西藏網(wǎng)絡(luò)空間治理研究基地，陜西 咸陽 712082）

自動導(dǎo)引運輸車(AGV)的路徑規(guī)劃問題是在確保AGV安全的前提下，規(guī)劃出一條效率最高且能夠成功到達(dá)目標(biāo)位置的路徑。

傳統(tǒng)的AGV路徑規(guī)劃算法有A*算法[1]、人工視場算法[2]等。隨著智能仿生學(xué)算法的發(fā)展和應(yīng)用，越來越多的學(xué)者將蟻群算法(AOC)[3]、麻雀搜索算法(SSA)[4]等應(yīng)用于AGV路徑規(guī)劃。其中，麻雀搜索算法是一種啟發(fā)式的隨機搜索算法，具有優(yōu)秀的尋優(yōu)能力和魯棒性強的優(yōu)點，但它和其他啟發(fā)式算法一樣存在初試種群多樣性較弱、收斂速度慢以及最短路徑平滑性不足的缺點。針對以上問題，宋立業(yè)[5]等通過Tent映射改進(jìn)麻雀算法提高了算法的種群多樣性；魏曉鴿[6]等使用精英反向?qū)W習(xí)策略和動態(tài)權(quán)重系數(shù)的正弦余弦優(yōu)化算法改進(jìn)麻雀算法，提高了算法在的路徑尋優(yōu)能力；齊鵬飛[7]等通過改進(jìn)灰狼優(yōu)化(GWO)算法，有效避免了GWO算法目的地?zé)o法抵達(dá)的問題，并且提高了GWO算法的尋優(yōu)能力。以上改進(jìn)方法在不同程度上提高了算法的尋優(yōu)能力，但仍然存在收斂速度慢、尋優(yōu)路徑拐點處平滑性較差的缺點。

基于以上學(xué)者的研究，本文提出了基于墜落機制的混沌麻雀優(yōu)化算法(SSA-CD)來解決AGV路徑規(guī)劃算法。該算法引入變尺度混沌初始化種群提高種群多樣性；其次，引入動態(tài)黃金正弦策略提高算法發(fā)現(xiàn)者位置更新方式；提出了一種墜落機制；最后，通過埃爾米特插值平滑策略，進(jìn)一步優(yōu)化最優(yōu)解，獲得更短更平滑的路徑。從而提高了AGV路徑規(guī)劃的平滑性和性能，并將算法進(jìn)行仿真實驗。

1 基于墜落機制的混沌麻雀算法（SSA-CD）

1.1 初始化操作

出于模擬需要，通過柵格法[3]在二維平面上構(gòu)建解空間，搭建20 m×20 m柵格地圖環(huán)境，將障礙物定義為黑色不可行區(qū)域，白色柵格為可行區(qū)域作為路徑的生成節(jié)點，AGV在柵格內(nèi)共有8個行駛方向，柵格地圖環(huán)境如圖1所示。

圖1 柵格地圖環(huán)境

1.2 麻雀搜索算法

麻雀搜索算法是一種受麻雀種群進(jìn)食行為啟發(fā)提出的一種仿生優(yōu)化算法。

發(fā)現(xiàn)者具有較好的全局搜索能力能夠帶領(lǐng)種群向食物源移動，一般占種群規(guī)模的20%。發(fā)現(xiàn)者位置更新公式為

式中：t為當(dāng)前迭代次數(shù)，Tmax表示最大迭代次數(shù)；xi,j為第i只麻雀在第j維度上的位置信息；a為一個[0,1]之間的隨機數(shù)。R2和ST分別表示預(yù)警值和安全值。當(dāng)R2小于ST時表明發(fā)現(xiàn)者處在安全區(qū)域，可以進(jìn)行廣泛的全局搜索，當(dāng)R2大于ST時表明發(fā)現(xiàn)者察覺出危險，并向其他麻雀發(fā)出報警信息，帶領(lǐng)種群逃出危險區(qū)域；Q為服從正態(tài)分布的隨機數(shù)；L為1×d的全1矩陣。

麻雀搜索算法在每次迭代過程中，選擇種群位置中位置最優(yōu)的作為發(fā)現(xiàn)者，剩余的麻雀作為加入者，加入者的位置更新公式為

式中：Xp表示當(dāng)前迭代中最優(yōu)適應(yīng)度的發(fā)現(xiàn)者位置，Xworst表示為全局適應(yīng)度最差的麻雀個體位置。L為一個隨機賦值為1或-1的1×d矩陣，A+=AT(AAT)-1。n為種群的數(shù)量，當(dāng)i>n/2是，表示加入者處于饑餓狀態(tài)需要飛行到其他位置尋找食物，當(dāng)i

式中：xb表示當(dāng)前迭代全局最優(yōu)適應(yīng)度位置；β是步長控制參數(shù)，是一個符合正態(tài)分布的隨機數(shù)；K為[-1,1]的隨機數(shù)；z是最小的常數(shù)，用以避免分母出現(xiàn)0的情況。fi和fw分表表示最優(yōu)和最差的適應(yīng)度。當(dāng)麻雀處于最優(yōu)位置則逃離到以自身附近的位置。當(dāng)麻雀處于較差位置時，則將逃出到當(dāng)前最優(yōu)位置附近。

1.3 變尺度混沌策略

為了增強算法初始化種群的多樣性，本文引入Sinusoidal混沌映射完成麻雀種群初始化，混沌映射公式為

其中：本文取a=2.3、x1=0.7。迭代次數(shù)為1 000次的混沌狀態(tài)種群初始化如圖2所示。由圖2可知，使用Sinusoidal混沌映射初始化的種群分布更加均勻，能夠獲得比隨機初始化更加穩(wěn)定分布的初始化解。

圖2 Sinusoidal混沌映射圖

在搜索空間減小的問題上，混沌映射表現(xiàn)較好。當(dāng)搜索空間較大時，混沌映射可能存在失效的情況，因此在混沌映射公式中加入尺度變換來增強其在較大搜索空間上的表現(xiàn)性能。引入尺度變換的混沌映射公式為

其中：t為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)。當(dāng)最優(yōu)值在迭代10次還為發(fā)生變化時，可以認(rèn)定為算法進(jìn)入搜索停滯狀態(tài)。此時需要將種群再次通過混沌映射進(jìn)行擾動，增加種群的隨機性，使算法跳出搜索停滯狀態(tài)。

1.4 動態(tài)黃金正弦策略

發(fā)現(xiàn)者的搜索范圍較小的問題導(dǎo)致SSA算法存在易于陷入局部最優(yōu)和搜索停滯的缺陷。式（1）中的exp(-i/(αTmax))起到?jīng)Q定發(fā)現(xiàn)者勘探能力的作用，令p=exp(-i/(αTmax))，則其變化曲線如圖3所示。根據(jù)i值的不同，p的值總是落在[0.9,1]，從而導(dǎo)致發(fā)現(xiàn)者的位置搜索范圍較小，并且在迭代過程中種群不斷的趨近于0，由于發(fā)現(xiàn)者起著引領(lǐng)種群的特點，因此將導(dǎo)致整個種群在不斷的趨向于非原點。當(dāng)R2≥ST時,發(fā)現(xiàn)者所使用的正態(tài)隨機數(shù)的擾動策略效果有效。為了增強麻雀搜索算法的全局搜索能力，本文通過引入動態(tài)調(diào)整的黃金正弦[8]策略來改進(jìn)發(fā)現(xiàn)者全局搜索公式，增強發(fā)現(xiàn)者全局搜索能力和全局尋優(yōu)速度。改進(jìn)后的發(fā)現(xiàn)者更新公式為

圖3 參數(shù)p的數(shù)值分布

其中：xP為當(dāng)前迭代中最優(yōu)適應(yīng)度個體位置，r1和r2分別為取值 [0,2π]和 [0,π]的隨機數(shù)，c1和c2表示黃金分割系數(shù)，c1=a(1-g)+bg、c2=ag+b(1-g)、黃金分割率g=0.618，c1和c2縮小了搜索空間，在迭代過程當(dāng)中可以引導(dǎo)麻雀個體向全局最優(yōu)位置移動。

受文獻(xiàn)[6]中引入慣性權(quán)重思想的啟發(fā)，為了更好的平衡算法全局搜索和局部尋優(yōu)能力，改善算法在迭代后期陷入搜索停滯狀態(tài)的問題，在黃金正弦更新公式中引入非線性自適應(yīng)權(quán)重w，表達(dá)式為

非線性慣性權(quán)重保證算法在迭代初期全局探索范圍更大且更快的遞減速度有利于減少算法全局探索的迭代次數(shù)。隨著迭代次數(shù)的增多，探索范圍逐漸收斂切收斂速度減緩，更有利于算法進(jìn)行局部挖掘，解決算法后期因為范圍減小帶來的搜索停滯問題。加入非線性自適應(yīng)權(quán)重的發(fā)現(xiàn)者位置更新公式為

1.5 墜落機制

在標(biāo)準(zhǔn)SSA算法中，發(fā)現(xiàn)者位置更新的正態(tài)分布隨機數(shù)擾動的效果隨著迭代的增加效果有限，為了增加SSA算法的隨機性， 本文提出一種墜落機制，即麻雀在飛行和覓食的過程中有一定概率發(fā)生墜落或者被其他大型鳥類捕食的現(xiàn)象。為了確保經(jīng)過墜落后的種群數(shù)量不變，我們通過麻雀的位置和麻雀下降的步長來建立墜落機制模型，其具體模型為

其中：r3、r4和r5為取值區(qū)間(0,1)的隨機數(shù)，xstep為麻雀的墜落步長，其具體定義如下。

其中：ub和lb為第i維度的取值上界和下界，n為問題的維度，C2為步長因子，可以看出步長因子受迭代次數(shù)和最大迭代次數(shù)的邊界影響。麻雀墜落的概率Wf從迭代前期的0.1逐漸減少到0.05，表明在優(yōu)化過程當(dāng)中，隨著麻雀靠近最優(yōu)值解危險逐漸降低。

1.6 三次埃爾米特插值方法

SSA算法生成的路徑仍然不夠平滑，部分路徑中還存在尖銳拐點。受文獻(xiàn)[9]中通過B樣條曲線平滑路徑的思想啟發(fā)，在改進(jìn)SSA算法的基礎(chǔ)上引入三次埃爾米特插值多項式。埃爾米特插值和貝塞爾曲線[10]相比，具有能夠克服貝塞爾曲線存在的局 部性質(zhì)缺點的能 力 。 設(shè)在節(jié)點a≤x0＜x1＜ ···＜xn≤b上滿足條件yi=f(xi)，mi=f(xi)(i=0,1,···,n)，要求插值多項式H(x)滿足條件

因插值節(jié)點一共存在n+1個，當(dāng)給出2n+1個條件的時候，可以唯一確定一個次數(shù)不超過2n+1的多項式H2n+1(x)=H(x)，其表達(dá)式為

由基函數(shù)構(gòu)建埃爾米特插值多項式需要先求出插值的基函數(shù) αi(x)， βi(x)(i=0,1,···,n)，因而共得到2n+2個基函數(shù)，每個基函數(shù)為一個2n+1次的多項式，并且需要滿足

結(jié)合以上條件生成的埃爾米特插值項式的公式為

其中，三次埃爾米特插值的數(shù)學(xué)描述如下。

埃爾米特插值通過在區(qū)間內(nèi)生成一系列的中間插值節(jié)點，能夠生成一條平滑的曲線。通過將三次埃爾米特插值曲線引入到VGA的全局路徑規(guī)劃當(dāng)中，可以使得VGA的路徑移動更加符合動力學(xué)原理。

1.7 算法流程

改進(jìn)后的算法流程如圖4所示。

圖4 算法整體流程圖

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

2.1 簡單環(huán)境下對比試驗

為了驗證算法在低密度環(huán)境下，算法對AGV路徑尋優(yōu)的可行性和有效性，本實驗選取環(huán)境大小為20 m×20 m的二維環(huán)境，AGV所處的起始位置為(0,0)，終點位置為(20,20)。實驗設(shè)置種群規(guī)模為50，最大迭代次數(shù)為200次，單位柵格的邊長為1 m。分別采用CAO算法、CAO-GA算法[11]、SSA算法、混沌麻雀(SSA-C)[12]算法和SSA-CD算法進(jìn)行路徑規(guī)劃。其中ACO算法的信息素重要程度因子a=1、b=5、q=2 000、信息素的揮發(fā)因子p=0.7；SSA算法的參數(shù)設(shè)置為PD=70%、R2=0.8、SD=20%。各算法的最優(yōu)路徑對比如圖5所示，記錄各算法的迭代收斂曲線和最優(yōu)路徑信息如圖6和表1所示。

5種算法的迭代收斂過程如圖6所示，由圖可以看出，SSA-CD算法的收斂精度優(yōu)于其他對比算法。其中ACO-GA算法和SSA算法在迭代過程中陷入搜索停滯狀態(tài)，全局搜索能力較差。在迭代到40次左右時SSA-CD算法完成收斂，優(yōu)于其他對比算法。并且通過對比收斂曲線拐點數(shù)量可知，ACO算法收斂過程中拐點數(shù)目較多，SSA-CD算法收斂迭代過程收斂速度較快、拐點數(shù)目少，全局搜索和局部探索階段較為平衡，能夠更好地跳出局部最優(yōu)解。

圖6 5種算法迭代曲線對比

從圖5和表1中可以看出，SSA算法的最優(yōu)路徑長度為34.34 m，SSA-C的路徑長度為28.22 m，相較于SSA算法路徑減少了17.82%；SSA-CD算法對路徑進(jìn)行平滑優(yōu)化后的路徑長度為27.20 m，相較于SSA-C算法路徑長度縮短了3.61%，表明了本文所提出的改進(jìn)方法對于路徑長度縮短的有效性和可行性，能夠增強算法的全局收斂能力和局部探索能力，使算法具有更好的探索精度。ACO-GA算法的平均路徑長度為32.62 m，優(yōu)于ACO算法的路徑長度34.34 m，算法拐點數(shù)目較少，但是算法運行時間較長，不利于AGV路徑規(guī)劃對實時性的要求；ACO和SSA算法的迭代運行時間較為接近分別為12.45 s和11.81 s，迭代次數(shù)為63和65次，而SSACD算法的運行時間為8.95 s，迭代次數(shù)為40次，表明本文改進(jìn)方法能夠增強初試種群的多樣性，并且能夠縮短算法的全局探索能力，提高算法局部收斂精度，進(jìn)一步表明本文算法改進(jìn)的有效性和可行性。從整體上來看路徑尋優(yōu)能力上SSA-CD算法>SSA-C算法>ACO-GA算法>ACO算法。綜上所述，本文算法相較于ACO算法能夠減少20.7%的路徑長度，優(yōu)于對比算法。

表1 4種算法數(shù)據(jù)結(jié)果

圖5 5種算法仿真結(jié)果

2.2 復(fù)雜環(huán)境下對比試驗

為了進(jìn)一步證明算法的有效性和魯棒性。設(shè)置規(guī)模為40 m×40 m的正方形區(qū)域，柵格的大小為40×40，選取傳統(tǒng)的A*算法、SSA算法、SSA-C和SSA-CD算法進(jìn)行AGV路徑規(guī)劃。通過增加障礙物的數(shù)量和密度來驗證算法的魯棒性，實驗結(jié)果如圖7和表2所示。

表2 4種算法數(shù)據(jù)結(jié)果

圖7 4種種算法仿真結(jié)果

由圖7和表2可知，本文算法的路徑長度最短為57.92 m，優(yōu)于其他算法。在算法尋優(yōu)過程中A*算法陷入死區(qū)，路徑規(guī)劃失敗，表明本文改進(jìn)的算法相較于傳統(tǒng)A*算法具有更好的魯棒性。未經(jīng)過平滑處理的SSA-C算法的規(guī)劃路徑長度為60.42 m，經(jīng)過平滑處理后的SSA-CD算法比SSA-C算法路徑減少了4.13%，由此可以看出，不管在低密度和高密度環(huán)境下，三次埃爾米特插值平滑處理都可以減少路徑并且減少路徑的拐點數(shù)，提升了路徑規(guī)劃的能力。與傳統(tǒng)SSA算法相比，本文算法的規(guī)劃路徑長度減少了8.45 m，進(jìn)一步證明了本文改進(jìn)算法的有效性、魯棒性和可行性，能夠完成復(fù)雜環(huán)境下AGV路徑規(guī)劃任務(wù)。

3 結(jié)語

針對高密度復(fù)雜環(huán)境下的自動導(dǎo)引運輸車的路徑規(guī)劃問題，本算法通過融合混沌麻雀算法和三次埃爾米特插值解決AGV路徑規(guī)劃問題，并且通過變尺度混沌策略提高了麻雀算法的種群多樣性、收斂速度和尋優(yōu)精度，引入動態(tài)黃金正弦策略增強算法種群位置更新方式多樣性，然后提出了一種墜落機制，增強算法的隨機性，并且將三次埃爾米特插值方法引入到生成路徑的平滑處理中。最終通過實驗表明本文算法有效提高了自動導(dǎo)引運輸車的路徑規(guī)劃質(zhì)量，能夠在保證生成路徑效率最優(yōu)的同時減少拐點數(shù)量。今后還需深入研究不同環(huán)境對自動導(dǎo)引運輸車路徑規(guī)劃的影響，進(jìn)一步提高算法的應(yīng)用場景并將算法應(yīng)用于實際場景中。