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

李一銘 王跟成

（①西藏民族大學信息工程學院，陜西 咸陽 712082；②西藏自治區光信息處理與可視化技術重點實驗室，陜西 咸陽 712082；③西藏網絡空間治理研究基地，陜西 咸陽 712082）

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

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

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

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

1.1 初始化操作

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

圖1 柵格地圖環境

1.2 麻雀搜索算法

麻雀搜索算法是一種受麻雀種群進食行為啟發提出的一種仿生優化算法。

發現者具有較好的全局搜索能力能夠帶領種群向食物源移動，一般占種群規模的20%。發現者位置更新公式為

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

麻雀搜索算法在每次迭代過程中，選擇種群位置中位置最優的作為發現者，剩余的麻雀作為加入者，加入者的位置更新公式為

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

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

1.3 變尺度混沌策略

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

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

圖2 Sinusoidal混沌映射圖

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

其中：t為當前迭代次數，Tmax為最大迭代次數。當最優值在迭代10次還為發生變化時，可以認定為算法進入搜索停滯狀態。此時需要將種群再次通過混沌映射進行擾動，增加種群的隨機性，使算法跳出搜索停滯狀態。

1.4 動態黃金正弦策略

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

圖3 參數p的數值分布

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

受文獻[6]中引入慣性權重思想的啟發，為了更好的平衡算法全局搜索和局部尋優能力，改善算法在迭代后期陷入搜索停滯狀態的問題，在黃金正弦更新公式中引入非線性自適應權重w，表達式為

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

1.5 墜落機制

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

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

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

1.6 三次埃爾米特插值方法

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

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

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

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

其中，三次埃爾米特插值的數學描述如下。

埃爾米特插值通過在區間內生成一系列的中間插值節點，能夠生成一條平滑的曲線。通過將三次埃爾米特插值曲線引入到VGA的全局路徑規劃當中，可以使得VGA的路徑移動更加符合動力學原理。

1.7 算法流程

改進后的算法流程如圖4所示。

圖4 算法整體流程圖

2 實驗結果與分析

2.1 簡單環境下對比試驗

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

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

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

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

表1 4種算法數據結果

圖5 5種算法仿真結果

2.2 復雜環境下對比試驗

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

表2 4種算法數據結果

圖7 4種種算法仿真結果

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

3 結語

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