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

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

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

1 引言

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

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

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

2 蟻群算法邏輯

2.1 傳統(tǒng)蟻群算法

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

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

2.2 改進蟻群算法的信息素更新規(guī)則

2.2.1 信息素更新策略

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

2.2.2 信息素更新規(guī)則

信息濃度更新規(guī)則如下所示：

最優(yōu)路徑的信息素更新規(guī)則：

其余螞蟻相關(guān)路徑中的信息素更新規(guī)則:

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

3 模擬仿真

3.1 柵格法建立環(huán)境

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

3.2 仿真應用

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

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

表1 改進后的蟻群算法相關(guān)參數(shù)

圖1 傳統(tǒng)蟻群算法路徑圖

圖3 傳統(tǒng)蟻群算法收斂曲線

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

如圖1和圖2所示，用傳統(tǒng)蟻群算法和改進后的蟻群算法運行得到的路徑并不相同，經(jīng)過數(shù)據(jù)比對，改進后的蟻群算法所生成的路徑更優(yōu)。

觀察傳統(tǒng)蟻群算法收斂曲線(見圖3、圖4)，可發(fā)現(xiàn)未優(yōu)化的蟻群算法收斂不平穩(wěn)、速度慢，最終所得到的路徑較長。而改進后的蟻群算法所規(guī)劃的路徑更為集中，且集中在了最優(yōu)路徑的周圍。

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

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

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

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

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

通過Matlab仿真后生成的相關(guān)數(shù)據(jù)可以看出，本文所改進的蟻群算法能夠在復雜的環(huán)境下更快速地搜索到最優(yōu)解，并且所得結(jié)果優(yōu)于傳統(tǒng)蟻群算法，也提升了算法運行過程中的搜索效率。

表3 優(yōu)化前后路徑長度及優(yōu)化比例

4 結(jié)語

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