基于精英策略的蟻群算法在AGV路徑優化中的應用*

□ 孫宇翔，陳浩鵬，任傳榮

(江蘇科技大學 張家港校區，江蘇 張家港 215600)

1 引言

在現代物流的倉儲中，貨物搬運效率的顯著提升得益于自動引導車(Automated Guided Vehicle，AGV)的出現，也為企業節省了大量的勞動力成本[1]。在這種全自動化設備的運行過程中，為了搜尋一條相對更優的路徑，使AGV在運行過程中可以避開所有障礙物的同時行駛較短的距離，依靠的是背后強大的算法。

傳統蟻群算法的隨機選擇雖然能搜索更大的任務范圍，有助于搜尋潛在的全局最優解，但是需要相對比較長的時間才能發揮正反饋的作用，致使算法在開始階段收斂速度較慢。同時，蟻群算法具有正反饋的特性，若蟻群算法在開始搜索時受次優解影響，那么正反饋會使次優解很快占據優勢，使算法陷入局部最優。針對上述問題，很多先前的研究者在蟻群算法的基礎上做出了改進，曹新亮等[2]針對蟻群算法在初期搜索目標的盲目性，建立了新的數學模型，對開始的信息素濃度提前進行差異化設置，進而提高算法收斂速度；占偉等[3]在初始階段就賦予了蟻群算法一個確定的搜索方向，在信息素更新策略上平衡全局和局部搜索的能力，盡力以最快的速度找到最優解；韓顏等[4]將粒子群算法和蟻群算法融合改進，在蟻群算法中設定柵格標識，從而增強小車的避障能力。

本文針對傳統蟻群算法中存在的問題，加入了精英策略，通過模擬仿真來驗證改進后的算法在搜索AGV運行的最優路徑上的有效性。

2 蟻群算法邏輯

2.1 傳統蟻群算法

通常認為，在蟻群算法開始之前，各目標點及路徑上各點的信息素濃度一致為0，有τ0=τij(0)；用ηij(t)來表示啟發函數，即在時刻t時，螞蟻從目標點i轉向目標點j的期望程度。

allowedk={C-tabuk}是t時刻螞蟻下一步允許選擇的柵格塊(沒有訪問過的柵格)；tabuk(k=1,2,…,m)是禁忌表，記錄已走過的柵格塊。

2.2 改進蟻群算法的信息素更新規則

2.2.1 信息素更新策略

信息素的更新機制直接影響了蟻群算法整體的性能。在蟻群算法中引入遺傳算法的精英策略[6]，使得螞蟻在尋路的過程中，將每次迭代完成后的精英螞蟻對應的解取出來，對精英螞蟻的路徑進行局部的信息素調整，即對每條精英路徑依據長度賦予不同的比例參數ω，路徑長度越小，則參數越大，信息量濃度也越大。這樣，不僅增強了蟻群算法的正反饋機制，提升了算法效率，同時，采取局部信息素更新和全局信息素更新相結合的方式，避免了算法早熟收斂。

2.2.2 信息素更新規則

信息濃度更新規則如下所示：

最優路徑的信息素更新規則：

其余螞蟻相關路徑中的信息素更新規則:

其中，w-r表示第r只精英螞蟻的信息素更新比例參數，Δτbest(i,j)表示在當代循e只(即最短路徑)精英螞蟻在柵格(i,j)上釋放的信息素濃度。

3 模擬仿真

3.1 柵格法建立環境

將蟻群算法應用于AGV小車路徑規劃之前，需要將實際環境虛擬化，即建立環境模型。在全局的路徑規劃中，使用頻率最高的就算柵格法[7]。柵格法的建立過程就是在AGV的可運動范圍內建立二維的平面直角坐標系，隨后根據障礙物的布局、大小模擬出柵格區域的大小。把柵格分為障礙類柵格和可行駛柵格，對前者賦值為1，對后者賦值為0，這樣機器人就可以根據柵格的屬性值區分障礙物和可行駛區域。

3.2 仿真應用

該仿真模擬中采用20*20的柵格圖作為仿真模擬環境，黑色代表障礙物，白色代表可移動區域。其中算法的具體相關參數如表1所示。

在Matlab中，分別使用傳統蟻群算法和基于精英策略后的蟻群算法進行模擬，得到的結果如圖1-4所示。

表1 改進后的蟻群算法相關參數

圖1 傳統蟻群算法路徑圖

圖3 傳統蟻群算法收斂曲線

圖4 精英策略下的蟻群算法收斂曲線

如圖1和圖2所示，用傳統蟻群算法和改進后的蟻群算法運行得到的路徑并不相同，經過數據比對，改進后的蟻群算法所生成的路徑更優。

觀察傳統蟻群算法收斂曲線(見圖3、圖4)，可發現未優化的蟻群算法收斂不平穩、速度慢，最終所得到的路徑較長。而改進后的蟻群算法所規劃的路徑更為集中，且集中在了最優路徑的周圍。

表2 改進前后路徑長度及到達終點螞蟻數量

通過比對生成的詳細數據可以看到，傳統蟻群算法搜索到的最優路徑長度為33.20，而精英策略下的蟻群算法搜索到的最優路徑長度為31.79，并且在兩個算法運行的過程中，傳統蟻群算法搜索到的可行解的平均值高于改進后的蟻群算法。

在兩個算法各迭代100次的過程中，傳統蟻群算法只有2279只螞蟻最終到達了終點，而精英策略下的蟻群算法有4061只螞蟻成功到達了終點，說明改進后的蟻群算法提高了螞蟻的搜索效率。

在修改柵格法中障礙物的布局和更換目標點位置后，分別用傳統蟻群算法和改進后的蟻群算法搜索路徑結果，得出了8組優化前后的路徑長度，并求出了優化比例。其結果如表3所示。

分析比對結果可知，總體來看，加入精英策略后的蟻群算法搜索到的最優路徑長度相較于傳統蟻群算法有所減少，在大多數情況下優化效果明顯。

通過Matlab仿真后生成的相關數據可以看出，本文所改進的蟻群算法能夠在復雜的環境下更快速地搜索到最優解，并且所得結果優于傳統蟻群算法，也提升了算法運行過程中的搜索效率。

表3 優化前后路徑長度及優化比例

4 結語

本文針對傳統蟻群算法初期收斂速度慢、容易陷入局部最優解等問題，在傳統蟻群算法的基礎上加入了精英策略，運用對精英螞蟻的信息素進行局部更新的思想，替換了信息素的更新規則。經過仿真模擬后發現，改進后的蟻群算法提高了算法的收斂速度和搜索效率，其搜索的路徑結果更優，證實了該算法的可行性和有效性。