顧文斌，陳澤宇，吳亞偉，苑明海

(1.河海大學(xué) 機電學(xué)院，江蘇 常州 213022；2.常州工程職業(yè)技術(shù)學(xué)院，江蘇 常州 213022)

0 引 言

自動引導(dǎo)小車(automated guided vehicle，AGV)最早出現(xiàn)于二十世紀五十年代，是一種智能化物料自動搬運設(shè)備，其特點在于自動化程度高、易于控制、節(jié)省勞動力、提高運輸效率、占地空間小等，因此，AGV在眾多生產(chǎn)制造物流行業(yè)中得到了廣泛應(yīng)用。在汽車制造行業(yè)中，物流領(lǐng)域自動化設(shè)備應(yīng)用是大勢所趨，使用AGV替代人力能夠降低汽車制造企業(yè)的運輸成本，提升服務(wù)質(zhì)量[1]。對煙草、醫(yī)藥、食品和化工等行業(yè)而言，業(yè)內(nèi)對搬運任務(wù)有清潔、無排放污染、安全等要求，AGV能夠較好地勝任。在倉儲業(yè)中，AGV使用程度更為廣泛，因為AGV有較強自動化水平和較高柔性，在倉儲物流行業(yè)中能夠降低人力成本，提高運輸效率[2]。在AGV的使用中，進行合理的路徑規(guī)劃對于降低企業(yè)運營成本，提高利潤率有重大作用，因此AGV的路徑規(guī)劃問題十分值得研究。

為了計算得到全局最優(yōu)路徑，目前采用的方法主要有遺傳算法[3-4]、粒子群算法[5-6]、快速擴展隨機樹尋路算法[7]和蟻群算法[8-9]。之后的研究主要針對這幾種算法進行改進，文獻[1]提出的改進遺傳算法減少了最短路徑的路程，文獻[2]對傳統(tǒng)遺傳算法進行改進，提高了算法的收斂速度和效率。文獻[5]提出的改進粒子群算法提高了在AGV在規(guī)避障礙時搜得解的精度。文獻[7]提出的改進快速擴展隨機樹尋路算法使得在復(fù)雜環(huán)境下機器人的運行更加平穩(wěn)，且在一定程度上縮短了路徑長度。文獻[8]提出的融合粒子群與蟻群算法提升了蟻群算法的整體性能。對于傳統(tǒng)蟻群算法收斂性差，容易陷入局部最優(yōu)，結(jié)果不穩(wěn)定的缺點，則考慮在對螞蟻和迭代質(zhì)量的評估之后，對每一次尋路的信息素進行區(qū)別更新，有利于擴大算法前期的搜索范圍，加強算法后期的收斂性，提高算法的穩(wěn)定性。

以上文獻所用方法是目前解決AGV路徑規(guī)劃問題中普遍認可的，較優(yōu)的算法，但是傳統(tǒng)算法存在容易進入局部最優(yōu)解，收斂性較差和搜尋結(jié)果穩(wěn)定性差的問題?；诖耍撐奶岢隽烁倪M型蟻群算法，使用兩次評估來合理區(qū)分蟻群，根據(jù)區(qū)分結(jié)果使用不同的信息素更新方式，以此實現(xiàn)提高算法解的多樣性、收斂性和穩(wěn)定性的目標(biāo)。此外使用蜂巢柵格建立地圖模型，使得模型更加實際可靠，能提高AGV小車行駛時的平穩(wěn)性，并降低避險路徑的長度。

1 環(huán)境模型建立

對于研究AGV的路徑規(guī)劃問題，建立其空間移動環(huán)境模型是基礎(chǔ)，常用的方法有可視圖法[10]、傳統(tǒng)柵格法[11]和人工勢場法[12]。柵格法(grid method)具有簡單，易于表達和靈活等優(yōu)點，所以采用柵格法建立AGV空間環(huán)境模型，并在傳統(tǒng)的柵格基礎(chǔ)上，模擬蜂巢建立起正六邊形的柵格，對AGV行駛環(huán)境進行分割。

1.1 蜂巢柵格模型建立

圖1 蜂巢型柵格

1.2 蜂巢型柵格和傳統(tǒng)柵格的對比分析

圖2 蜂巢柵格移動方向

圖3 避險路徑對比

圖4 最短路徑對比

綜上，蜂巢柵格在行駛的平穩(wěn)性和避險路徑的長度方面都優(yōu)于傳統(tǒng)的正方形柵格，因此后文的改良蟻群算法將在蜂巢柵格的背景下進行求解。

2 基于動態(tài)分級制度的改進型蟻群算法

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

在傳統(tǒng)的蟻群算法中，螞蟻會根據(jù)路徑上的信息素濃度選擇自己的路徑，并且根據(jù)路徑的質(zhì)量留下新的信息素，每一次迭代后所有路徑上的信息素都會消散一部分，使得路徑尋找不會過早地進入局部最優(yōu)。選擇方法如下。

(1)

(2)

(3)

式中，ρ∈(0,1)，為信息素在一次迭代中的揮發(fā)系數(shù)；Δτij為信息素的增量；K為螞蟻總數(shù)；Q為一常數(shù)。

2.2 選擇機制的改進

在傳統(tǒng)的蟻群算法中，路徑啟發(fā)因子ηij(t)是根據(jù)路徑(i，j)所確定的，但是這樣容易陷入局部最優(yōu)解。為了獲得全局優(yōu)解，在改進的算法中使用ηij(t)=1/d(i,s)，其中d(i,s)為螞蟻此時距離目標(biāo)點的距離，同時將allowedk改為螞蟻k相鄰可選擇的點，將柵格矩陣做鄰接處理，螞蟻k只能選擇所得鄰接矩陣中值不為0的點做下一目標(biāo)點，以減少不必要的計算。

2.3 對蟻群進行評估分類

對于傳統(tǒng)的蟻群算法，信息素的更新完全根據(jù)路徑長度，也有學(xué)者研究了改良的信息素更新規(guī)則[13]來優(yōu)化蟻群算法，但是在算法前期多樣性和后期的收斂性方面還有待提高。針對這個問題，文中在考慮螞蟻的動態(tài)分級[9]之上，考慮每一次迭代的質(zhì)量，將每一次的迭代性質(zhì)分為尋優(yōu)和偵察，不同性質(zhì)的迭代采用不同的信息素更新規(guī)則，以提高前期解的多樣性和后期解的收斂性。

具體來說，受到人工蜂群算法[14]的啟發(fā)，先將螞蟻分為偵察蟻和尋優(yōu)蟻。首先根據(jù)該螞蟻在一次迭代中所搜索到的路徑Lk與此次迭代中所搜索到的最短路徑Lmin相比較，得到該螞蟻的屬性值，該值設(shè)置為：Tk=Lmin/Lk。之后設(shè)置屬性值的閾值，記為T0。比較屬性值和閾值來區(qū)分偵察蟻和尋優(yōu)蟻，當(dāng)Tk>T0時，說明該螞蟻搜得結(jié)果與最優(yōu)解相近，為尋優(yōu)蟻，則該螞蟻在更新信息素時，將更新的參數(shù)調(diào)整使得余留更多的信息素。反之當(dāng)Tk≤T0時，說明該螞蟻搜得路徑與最短路徑之間的差距較大，為偵察蟻，則該螞蟻在更新信息素時，將參數(shù)調(diào)整使得余留更少的信息素。所以T0設(shè)置的值需要重點研究，如果T0太大容易導(dǎo)致更少的螞蟻成為尋優(yōu)蟻而導(dǎo)致算法最終不能很好地收斂，如果T0太小容易使更多的螞蟻成為尋優(yōu)蟻而導(dǎo)致蟻群容易陷入局部最優(yōu)解。經(jīng)過多次仿真，發(fā)現(xiàn)將T0設(shè)置為0.68時能得到很好的結(jié)果。

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

根據(jù)上文對蟻群的評估結(jié)果，將算法中的螞蟻分為了四種情況，對于四種螞蟻將采取不同的信息素更細規(guī)則。

首先對于尋優(yōu)蟻和偵察蟻，兩者在信息素更新時，滿足以下關(guān)系：

τij(t+1)=(1-ρ)τij(t)+Δτij

(4)

(5)

(6)

式(5)、式(6)中，ω為螞蟻質(zhì)量系數(shù)，其中ω1>ω2>0，Q為一常數(shù)，Tk為螞蟻的屬性值，T0為螞蟻屬性值的閾值。在此更新規(guī)則下，尋優(yōu)蟻的信息素余留要高于偵察蟻的信息素余留，這樣在進行全局搜素時，確保了較優(yōu)路徑上有高濃度的信息素，但是ω1和ω2之間的差值不能過大，否則容易在算法初期就陷入局部最優(yōu)。經(jīng)過實驗仿真，將ω1設(shè)置為5，ω2設(shè)置為3，能夠有效防止陷入局部最優(yōu)且最后收斂較好。

關(guān)于迭代質(zhì)量，由于在算法初期，螞蟻搜索范圍大，路徑長短參差不齊且相差較大，此時這一代螞蟻的信息素更新策略采用式(7)。

τij(t+1)=(1-ρ)τij(t)+pm·Δτij,pm≤p0(7)

式中，pm為迭代的質(zhì)量值；Δτij則根據(jù)上述內(nèi)容先判斷該螞蟻是尋優(yōu)蟻還是偵察蟻。

在這種機制下，算法初期過于發(fā)散的搜尋結(jié)果將不會留下過濃的信息素，而其中接近最優(yōu)路徑的螞蟻則根據(jù)尋優(yōu)蟻余留更多信息素的特點，將較優(yōu)路徑先行區(qū)分開來，到達算法后期，一次迭代中大部分螞蟻都是接近最優(yōu)路徑后，則使用式(4)進行信息素更新，使結(jié)果收斂于最優(yōu)路徑。

綜上所述，改進型蟻群算法信息素更新滿足以下規(guī)則。

(8)

2.5 算法流程

將蜂巢柵格和改進的蟻群信息素更新規(guī)則融入傳統(tǒng)蟻群算法，得到的基于蜂巢柵格的改良蟻群算法如下(見圖5):

圖5 改進蟻群算法流程

(1)全局初始化，將環(huán)境矩陣鄰接化得到鄰接矩陣，得到初始螞蟻總數(shù)，迭代總數(shù)，起點終點位置。

(2)螞蟻根據(jù)概率公式(1)對路徑節(jié)點進行選擇。

(3)判斷螞蟻是否到達終點，若是，記錄此路徑長度并對該螞蟻的屬性進行評估，當(dāng)所有螞蟻執(zhí)行完此步，迭代數(shù)加1。若不是則重復(fù)步驟(2)。

(4)當(dāng)所有螞蟻完成步驟(3),對迭代質(zhì)量進行評估。

(5)根據(jù)螞蟻屬性和迭代質(zhì)量，對信息素進行區(qū)別更新。

(6)判斷是否到達最大迭代數(shù)，若是，則輸出最優(yōu)路徑，算法結(jié)束；若不是，則重復(fù)步驟(2)～(5)，直到算法結(jié)束。

3 仿真分析

使用MATLAB軟件對傳統(tǒng)蟻群算法和改進型蟻群算法進行仿真。前文已經(jīng)論述了蜂巢柵格的優(yōu)點，所以兩種算法都在25×25的蜂巢柵格的背景下進行計算。各個參數(shù)設(shè)置為：α=1,β=7,ρ=0.3,Q=1螞蟻數(shù)K=100，迭代數(shù)M=150。算法性能從算法的收斂性、路徑多樣性進行證明。

3.1 算法收斂性證明

圖6為根據(jù)改進型蟻群算法所得出的最短路徑圖。圖7為兩種算法的最短路徑長度的曲線收斂圖。從圖7的對比中可以看出，改進型算法在前期效果并非十分明顯，因為要保證初期路徑的多樣性，而到了算法中后期，進行有針對地尋找最優(yōu)路徑時，改進型蟻群算法能體現(xiàn)出良好的收斂性。

圖6 最優(yōu)路徑圖

為了證明算法的穩(wěn)定性，并和傳統(tǒng)算法進行對比，將兩種算法各運行10次并統(tǒng)計數(shù)據(jù)結(jié)果，如表1所示。

表1 算法結(jié)果對比

從表中可知，傳統(tǒng)算法下搜得最短路徑長度為36，而改進型算法下搜得最短路徑為35，并且根據(jù)10次運算的平均值和標(biāo)準(zhǔn)差可以看出，傳統(tǒng)的算法搜得最終結(jié)果差別較大，相比之下改進型蟻群算法出現(xiàn)此類問題的次數(shù)會少很多，根據(jù)收斂代數(shù)也可以看出，改進型蟻群算法由于信息素更新與傳統(tǒng)蟻群有區(qū)別，所以算法后期收斂性更強。

3.2 路徑多樣性證明

為了證明改進型蟻群算法在路徑多樣性方面的優(yōu)越性，和王槐彬等人提出的動態(tài)分級蟻群算法[15]進行了實驗數(shù)據(jù)結(jié)果對比。

在同時采用蜂巢柵格的基礎(chǔ)上，改進型蟻群算法和動態(tài)分級蟻群算法在路徑多樣性方面的對比如圖8所示。實驗設(shè)計150次迭代，在前半段迭代中，由于迭代質(zhì)量不佳，螞蟻殘留的信息素濃度根據(jù)更新規(guī)則會相應(yīng)減少，可以看到改進型蟻群算法的路徑多樣性要高于動態(tài)分級蟻群算法，達到避免進入局部最優(yōu)的效果，證明了改進型蟻群算法在路徑多樣性方面的優(yōu)越性。并且在算法后半段，迭代質(zhì)量提升，螞蟻逐漸向整體最優(yōu)路徑靠攏，根據(jù)信息素更新規(guī)則留下的信息素會增加使得蟻群準(zhǔn)確地找到最優(yōu)解。在圖中可以看出，最后改進型蟻群算法能夠使大部分螞蟻都找到最優(yōu)解，也證明了改進型蟻群算法的收斂性要優(yōu)于動態(tài)分級蟻群算法。

圖8 路徑種類對比

從每一次迭代結(jié)果的路徑長度標(biāo)準(zhǔn)差分析，如圖9所示，動態(tài)分級蟻群算法整體上能實現(xiàn)算法前期避免進入局部最優(yōu)，后期結(jié)果實現(xiàn)收斂，但是通過比較可以看出改進型蟻群算法在前期的發(fā)散程度和后期的收斂程度都要高于動態(tài)分級蟻群算法。如果考慮標(biāo)準(zhǔn)差到達一個閾值可以認為蟻群已經(jīng)找到整體最優(yōu)解，那么改進型蟻群算法相比于動態(tài)分級蟻群算法能夠更快得到結(jié)果，解決算法效率低的問題，證明改進型蟻群算法整體上優(yōu)于動態(tài)分級蟻群算法。

圖9 路徑長度標(biāo)準(zhǔn)差對比

4 結(jié)束語

對于AGV的路徑規(guī)劃問題，在傳統(tǒng)的柵格模型上進行改變，使用轉(zhuǎn)向角度小，避險路徑和原路徑比值小的蜂巢柵格對AGV行駛環(huán)境進行模型建立。在算法方面，由于傳統(tǒng)蟻群算法效率低，根據(jù)螞蟻和迭代的評估值對其進行信息素區(qū)別更新。在新的更新規(guī)則下，根據(jù)仿真結(jié)果可以得出，相比于傳統(tǒng)算法，改進型算法在前期的路徑多樣性，后期的算法收斂性方面都更加優(yōu)良，并且最終結(jié)果的準(zhǔn)確性、穩(wěn)定性也要優(yōu)于傳統(tǒng)的蟻群算法，證明了改進型蟻群算法整體優(yōu)于傳統(tǒng)蟻群算法。