張志軍, 董學(xué)平, 甘 敏

(1.合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院,安徽 合肥 230009; 2.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福建 福州 350108)

0 引 言

自動(dòng)導(dǎo)引車(automated guided vehicle,AGV)是一種無人駕駛的運(yùn)輸車輛。由于近幾年我國倉儲(chǔ)物流行業(yè)的迅速發(fā)展以及人力成本的提高,傳統(tǒng)的倉儲(chǔ)物流運(yùn)輸方式越來越不適應(yīng)人們的需求[1]。AGV工作穩(wěn)定可靠,可以大大提高工作效率,節(jié)省人力成本,將人們從某些危險(xiǎn)的工作環(huán)境中解放出來,在倉儲(chǔ)物流運(yùn)輸中扮演著越來越重要的角色,因此高效的AGV路徑規(guī)劃已經(jīng)成為一個(gè)重要的研究課題。

對(duì)于AGV的路徑規(guī)劃問題,國內(nèi)外學(xué)者做了大量的研究工作,提出了多種AGV路徑規(guī)劃方法,其中智能路徑規(guī)劃方法有遺傳算法[2]、粒子群算法[3]、人工蜂群算法[4]以及蟻群算法[5]等。蟻群算法是意大利學(xué)者Dorigo受到自然界中真實(shí)螞蟻群體的覓食行為啟發(fā)而提出的一種元啟發(fā)式算法[6],它具有良好的正反饋性、并行性以及較高的魯棒性,具有全局搜索能力,在解決AGV路徑規(guī)劃問題上得到了廣泛的應(yīng)用[7-9]。文獻(xiàn)[10]將蟻群下一步可達(dá)節(jié)點(diǎn)的范圍擴(kuò)大到整個(gè)地圖空間,并且通過設(shè)置跳點(diǎn),使搜索到的蟻群最短路徑長度得到了優(yōu)化,但該方法運(yùn)行耗時(shí)比較長;文獻(xiàn)[11]在精英蟻群算法的基礎(chǔ)上引入了獨(dú)狼搜索機(jī)制,采用獨(dú)狼逃跑策略在螞蟻視場內(nèi)設(shè)定天敵,從而避免路徑上的信息素趨于穩(wěn)定,改善路徑停滯問題,使最短路徑解的質(zhì)量得到了提升,但該算法的收斂速度還需要進(jìn)一步改善;文獻(xiàn)[12]針對(duì)復(fù)雜凹形障礙環(huán)境下的路徑規(guī)劃問題,提出了雙蟻群完全交叉算法,將蟻群2的路徑解和蟻群1的路徑解相交,以優(yōu)化蟻群1的路徑解,從而得到高質(zhì)量的路徑,但該算法2個(gè)蟻群的迭代次數(shù)和迭代方式相同,內(nèi)存占用比較大且耗時(shí)較長。

本文針對(duì)上述問題,提出了一種優(yōu)化蟻群算法。首先,在基本蟻群算法中引入輔助蟻群,利用輔助蟻群的方向優(yōu)勢優(yōu)化主蟻群初始信息素的分配,使主蟻群前期路徑搜索更具有針對(duì)性,提高了搜索效率,且輔助蟻群和主蟻群的迭代次數(shù)和迭代方式有很大區(qū)別,因此優(yōu)化蟻群算法占用內(nèi)存較小且運(yùn)行耗時(shí)較短。其次,偽隨機(jī)狀態(tài)轉(zhuǎn)移策略的引入,增加了路徑選擇的多樣性,避免了算法早熟。最后利用蟻群的當(dāng)前最優(yōu)解、主蟻群一代蟻群中的最優(yōu)解、最差解對(duì)路徑上信息素進(jìn)行有區(qū)別地獎(jiǎng)懲,提高路徑搜索的質(zhì)量。仿真結(jié)果表明,優(yōu)化蟻群算法的收斂速度和最短路徑質(zhì)量均得到了提升。

1 環(huán)境建模

1.1 柵格環(huán)境

在對(duì)AGV的路徑規(guī)劃研究中,建立AGV的運(yùn)動(dòng)環(huán)境是一個(gè)很重要的步驟,常用的環(huán)境建模方法有可視圖法、柵格法和拓?fù)浞╗13]。本文采用柵格法作為環(huán)境建模方法,將運(yùn)動(dòng)環(huán)境抽象為由m×n個(gè)網(wǎng)格單元組成的二維平面環(huán)境地圖,使得AGV在該環(huán)境下的運(yùn)動(dòng)過程視作質(zhì)點(diǎn)運(yùn)動(dòng)[14]。一個(gè)5×5的柵格環(huán)境如圖1所示,以環(huán)境左下角為坐標(biāo)原點(diǎn),向上為Y軸正方向,向右為X軸正方向,建立平面直角坐標(biāo)系,選擇網(wǎng)格單元長度為1 cm。在柵格環(huán)境中,將環(huán)境中的障礙物在環(huán)境地圖中用陰影柵格表示,不足1個(gè)柵格的按1個(gè)柵格計(jì)算,可行柵格用白色柵格表示。

將柵格環(huán)境按從左到右、從上到下的順序標(biāo)示每個(gè)柵格的序號(hào),在m×m的柵格環(huán)境中,序號(hào)S與所在柵格的坐標(biāo)(x,y)一一對(duì)應(yīng)且對(duì)應(yīng)關(guān)系為:

(1)

其中:mod為求余運(yùn)算;ceil為向上取整運(yùn)算。因此,AGV的行走路線可以用一系列序號(hào)數(shù)組的形式表示出來[15]。

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

AGV運(yùn)動(dòng)方向如圖2所示,除邊緣柵格外,每個(gè)柵格一般有左上、上、右上、左、右、左下、下、右下8個(gè)運(yùn)動(dòng)方向,分別將它們用1、2、3、4、5、6、7、8數(shù)字進(jìn)行編號(hào)。

圖2 AGV運(yùn)動(dòng)方向圖

1.2 柵格環(huán)境處理

在柵格環(huán)境中,當(dāng)一個(gè)可行柵格的上、下、左、右4個(gè)方向中至少有3個(gè)方向有障礙柵格存在時(shí),就構(gòu)成了一個(gè)凹形障礙物。本文針對(duì)此類凹形障礙物中的可行柵格做了優(yōu)化處理,這是因?yàn)檫@類可行柵格不但會(huì)增加不必要的路徑,而且還有可能導(dǎo)致螞蟻在搜索路徑的過程中無路可走而無法到達(dá)終點(diǎn),即發(fā)生死鎖現(xiàn)象,降低了蟻群路徑搜索質(zhì)量。柵格環(huán)境處理前后地圖如圖3所示。從圖3a可以看出,由網(wǎng)格14到網(wǎng)格16處,經(jīng)過網(wǎng)格9的長度比網(wǎng)格15的路徑長度長;由網(wǎng)格24到網(wǎng)格36處,經(jīng)過網(wǎng)格29的長度比網(wǎng)格30的路徑長度長,而且在網(wǎng)格29處螞蟻如果向網(wǎng)格28、27移動(dòng),那么會(huì)造成死鎖。本文算法會(huì)檢測可行柵格上、下、左、右4個(gè)方向柵格的可行狀態(tài),若出現(xiàn)3個(gè)及3個(gè)以上的柵格不可行時(shí),則會(huì)把該柵格標(biāo)記為障礙柵格,整個(gè)柵格持續(xù)重復(fù)檢測標(biāo)記,直到障礙柵格的數(shù)目不再增加為止,實(shí)現(xiàn)效果如圖3b所示。

圖3 柵格環(huán)境處理前后地圖

2 基本蟻群算法

基本蟻群算法中,人工螞蟻在尋找路徑時(shí),和真實(shí)螞蟻相似,會(huì)根據(jù)路徑上信息素的濃度選擇運(yùn)動(dòng)方向,濃度越高,選擇該運(yùn)動(dòng)方向的概率就越大。假設(shè)螞蟻k在t時(shí)刻從節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑上的信息素為τij(t),則從節(jié)點(diǎn)i到j(luò)的轉(zhuǎn)移概率為:

(2)

其中:α反映了信息素在路徑選擇時(shí)的重要程度,α越大,螞蟻就更傾向于選擇高信息素濃度的節(jié)點(diǎn);啟發(fā)值ηij=1/djG,表示為從節(jié)點(diǎn)j到終點(diǎn)G的歐式距離的倒數(shù);β反映了啟發(fā)信息在路徑選擇時(shí)的重要性,β越大,螞蟻就更傾向于選擇距離終點(diǎn)較近的柵格節(jié)點(diǎn);D為節(jié)點(diǎn)i可選的下一個(gè)可達(dá)節(jié)點(diǎn)的集合。

基本蟻群算法中,螞蟻利用信息素尋找路徑的同時(shí),也會(huì)在路徑上釋放信息素,當(dāng)一代螞蟻中所有的螞蟻都完成了路徑搜尋,全局信息素更新方式為:

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

(3)

(4)

(5)

3 優(yōu)化蟻群算法

3.1 優(yōu)化信息素的初始分配

基本蟻群算法初始信息素的設(shè)置都是相同的量,會(huì)導(dǎo)致算法在初期搜索時(shí)具有一定的盲目性,增加了搜索路徑的時(shí)間成本。本文中的優(yōu)化蟻群算法提出了一種使用輔助蟻群來協(xié)助主蟻群進(jìn)行初始信息素分配的方法。輔助蟻群利用其在搜索路徑上的方向優(yōu)勢,這種方向優(yōu)勢可以讓輔助蟻群較基本蟻群快速規(guī)劃出可行的較優(yōu)路徑。輔助蟻群工作原理如圖4所示，假設(shè)起點(diǎn)在序號(hào)為1的柵格處,記為B;終點(diǎn)在序號(hào)為25的柵格處,記為G,由于從B到G有一定的方向性,最優(yōu)路徑一般會(huì)出現(xiàn)在AGV由右、右下、下3個(gè)運(yùn)動(dòng)方向到達(dá)的節(jié)點(diǎn)組成的路徑中。因此在輔助蟻群中,規(guī)定螞蟻k在節(jié)點(diǎn)i處最多只有3個(gè)轉(zhuǎn)移方向,即右、下和右下,從節(jié)點(diǎn)i到可轉(zhuǎn)移節(jié)點(diǎn)j的轉(zhuǎn)移概率為:

(6)

其中:jx、jy分別為節(jié)點(diǎn)j的橫、縱坐標(biāo)值;ix、iy分別為節(jié)點(diǎn)i的橫、縱坐標(biāo)值;D′為節(jié)點(diǎn)i在右、下、右下3個(gè)方向可達(dá)節(jié)點(diǎn)的集合。由(6)式可知,螞蟻在右、下、右下方向的轉(zhuǎn)移概率分別為1/4、1/4、1/2,因此輔助蟻群更偏向于往右下方向移動(dòng),有利于減少搜索路徑長度。

圖4 輔助蟻群工作原理

輔助蟻群的每一代螞蟻中,只對(duì)找出該代中最短路徑的螞蟻的信息素進(jìn)行更新,全局信息素更新方式為:

(7)

(8)

其中:n為一代中最優(yōu)路徑上的螞蟻數(shù);Lbest′為該代中的最優(yōu)路徑長度;路徑(i,j)為該代最優(yōu)路徑。為避免某一路徑較其他路徑上的信息素濃度過高,造成主蟻群過早收斂,引入最大最小螞蟻系統(tǒng),利用下式對(duì)輔助蟻群迭代完成后的信息素進(jìn)行限制，即

(9)

其中:τmax′、τmin′分別為設(shè)置的輔助蟻群信息素的最大值和最小值。

設(shè)置輔助蟻群的初始信息素,待蟻群迭代完成后,將輔助蟻群信息素傳遞給主蟻群,作為主蟻群的初始信息素。由于輔助蟻群每代最優(yōu)路徑上的信息素較其他路徑多,能夠引導(dǎo)主蟻群沿著這些路徑移動(dòng),從而提高主蟻群前期搜索的路徑質(zhì)量;將輔助蟻群當(dāng)前搜索到的最優(yōu)路徑傳遞給主蟻群,幫助主蟻群優(yōu)化搜索策略。此外,輔助蟻群在類似于圖1的環(huán)境中會(huì)找不到從起點(diǎn)到終點(diǎn)的通路,此時(shí)輔助蟻群路徑上的初始信息素只會(huì)隨著迭代而揮發(fā),而沒有信息素的增量。迭代結(jié)束后,輔助蟻群將揮發(fā)后的信息素傳遞給主蟻群,同時(shí)將當(dāng)前最優(yōu)路徑長度設(shè)置為無窮大,此時(shí)主蟻群仍然能正常工作。

3.2 優(yōu)化的狀態(tài)轉(zhuǎn)移策略

對(duì)于主蟻群,針對(duì)基本蟻群算法中螞蟻從一個(gè)節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移為單獨(dú)的輪盤賭方式,很容易造成螞蟻較快集中到某一路徑而導(dǎo)致搜索到的最優(yōu)路徑不為全局最優(yōu)的情況,提出了一種偽隨機(jī)狀態(tài)轉(zhuǎn)移策略為:

(10)

其中:j1為i節(jié)點(diǎn)處隨機(jī)選擇的下一個(gè)可達(dá)節(jié)點(diǎn);j2為采用(2)式選擇的下一節(jié)點(diǎn);q為0～1之間的隨機(jī)數(shù);q0為偽隨機(jī)轉(zhuǎn)移策略選擇的切換值,q0=1/(N+1),為自適應(yīng)動(dòng)態(tài)變量,隨著迭代次數(shù)的增加而減少;N為優(yōu)化蟻群算法主蟻群的迭代次數(shù)。前期q0能取到較大的值,增加搜索路徑的多樣性;后期q0較小,螞蟻將會(huì)集中在信息素較多的路徑上,加快收斂速度。

3.3 優(yōu)化的信息素更新策略

本文采用全局信息素更新策略,即當(dāng)一代螞蟻中所有個(gè)體都完成了路徑搜索后才更新路徑信息素。

將輔助蟻群更新后的信息素和當(dāng)前搜索到的最優(yōu)路徑傳遞給主蟻群,幫助主蟻群完成路徑規(guī)劃。主蟻群每代螞蟻搜索完路徑后,根據(jù)主蟻群一代螞蟻中最差路徑Lworst、一代螞蟻中最優(yōu)路徑Lbest及當(dāng)前主蟻群和輔助蟻群所找到的最優(yōu)路徑LbestALL,利用(3)式、(4)式、(11)式更新全局信息素,即

(11)

懲罰一代中的最差路徑可以減少后代蟻群在該路徑上的數(shù)目,對(duì)當(dāng)前路徑上的信息素進(jìn)行有差別的獎(jiǎng)勵(lì),使螞蟻集中在較優(yōu)路徑附近,提高螞蟻搜索路徑解的質(zhì)量,加快收斂速度。

在路徑搜索過程中,可能會(huì)出現(xiàn)某代螞蟻中出現(xiàn)了當(dāng)前最優(yōu)路徑,但由于路徑上的信息素比較低而在后代螞蟻中丟失的現(xiàn)象,降低了找到全局最優(yōu)解的概率。為了確保當(dāng)前最優(yōu)路徑不會(huì)丟失,若Lbest和LbestALL在一代螞蟻中不相等,即該代螞蟻沒有搜索到LbestALL所在路徑時(shí),在該代螞蟻路徑信息素更新完畢后,則根據(jù)(3)式、(12)式增加當(dāng)前最優(yōu)路徑LbestALL的信息素為:

(12)

為了避免由于某一路徑上信息素濃度過高導(dǎo)致算法的停滯,對(duì)路徑上的信息素進(jìn)行限制，即

(13)

其中:τmax為限制的信息素的最大值;τmin為限制的信息素的最小值。

3.4 優(yōu)化蟻群算法的實(shí)現(xiàn)步驟

優(yōu)化蟻群算法的路徑尋優(yōu)流程圖如圖5所示。

具體實(shí)現(xiàn)步驟如下:

(2) 柵格環(huán)境處理。當(dāng)一個(gè)可行柵格的上、下、左、右4個(gè)方向中至少3個(gè)方向有障礙柵格存在,將該柵格標(biāo)記為障礙柵格。

(3) 輔助蟻群利用其方向優(yōu)勢尋找路徑,迭代完成后將當(dāng)前最優(yōu)路徑和更新后的信息素傳遞給主蟻群作為初始信息素。

(4) 主螞蟻k通過主蟻群狀態(tài)轉(zhuǎn)移策略選擇移動(dòng)到下一地址。

(5) 判斷螞蟻k是否陷入死鎖,若陷入,則丟棄該只螞蟻,并立刻啟動(dòng)下一螞蟻,轉(zhuǎn)步驟(4)。

(6) 判斷螞蟻k是否到達(dá)終點(diǎn),若到達(dá),則記錄該路徑并啟動(dòng)下一螞蟻,轉(zhuǎn)步驟(4)。

(7) 判斷一代中m只螞蟻是否都完成了路徑搜索;若是,則對(duì)該代中的螞蟻根據(jù)主蟻群信息素更新策略、更新信息素,迭代次數(shù)加1;否則轉(zhuǎn)步驟(4)。

(8) 重復(fù)步驟(4)～步驟(7),直到達(dá)到主蟻群最大迭代次數(shù)。

(9) 輸出最優(yōu)路徑,程序結(jié)束。

圖5 優(yōu)化蟻群算法路徑尋優(yōu)流程圖

4 仿真實(shí)驗(yàn)及結(jié)果

對(duì)2種算法均進(jìn)行20次獨(dú)立實(shí)驗(yàn),仿真后的統(tǒng)計(jì)數(shù)據(jù)見表1所列。

圖6 文獻(xiàn)[16]蟻群算法最優(yōu)路徑軌跡及仿真結(jié)果

圖7 優(yōu)化蟻群算法最優(yōu)路徑軌跡及仿真結(jié)果

表1 2種算法2次運(yùn)行結(jié)果統(tǒng)計(jì)數(shù)據(jù)

從圖6、圖7可以看出,本文的優(yōu)化蟻群算法和文獻(xiàn)[16]蟻群算法的最優(yōu)路徑相同,但是由表1可知,本文算法20次仿真實(shí)驗(yàn)中的最優(yōu)路徑都為全局最優(yōu)路徑,而文獻(xiàn)[16]算法有一定概率搜索到的最優(yōu)路徑為全局次優(yōu)路徑,同時(shí)本文算法達(dá)到最優(yōu)路徑的平均迭代次數(shù)相比文獻(xiàn)[16]算法有了顯著提高。

以上實(shí)驗(yàn)結(jié)果表明,相較于文獻(xiàn)[16]算法,本文算法通過引入輔助蟻群,使主蟻群前期路徑搜索時(shí)更具有針對(duì)性;通過引入偽隨機(jī)狀態(tài)轉(zhuǎn)移策略,增加了搜索過程中路徑的多樣性;通過優(yōu)化信息素更新策略,保證了路徑解的質(zhì)量,從而提高了蟻群算法的搜索效率,加快了蟻群算法的收斂速度,提升了最優(yōu)路徑解的質(zhì)量,表明了本文算法的優(yōu)越性。

5 結(jié) 論

在基本蟻群算法的基礎(chǔ)上,本文提出了一種優(yōu)化蟻群算法,對(duì)柵格環(huán)境做了優(yōu)化處理,利用輔助蟻群設(shè)置主蟻群的初始信息素,減少前期主蟻群搜索路徑的盲目性,并且對(duì)基本蟻群算法的狀態(tài)轉(zhuǎn)移策略以及信息素的更新策略做了相應(yīng)優(yōu)化。

MATLAB仿真結(jié)果表明,該優(yōu)化蟻群算法提高了蟻群搜索效率,加快了收斂速度,提升了最優(yōu)解的質(zhì)量,表明該優(yōu)化蟻群算法在AGV路徑規(guī)劃尋優(yōu)問題上是行之有效的。