基于改進(jìn)的蟻群算法(ACO)的混合多目標(biāo)AGV調(diào)度

姜德文

(1.沈陽(yáng)工學(xué)院 遼寧省數(shù)控機(jī)床信息物理融合與智能制造重點(diǎn)實(shí)驗(yàn)室, 遼寧 撫順 113122；2.沈陽(yáng)工學(xué)院 信息與控制學(xué)院，遼寧 撫順 113122)

0 引言

自動(dòng)導(dǎo)引車(chē)(automated guided vehicle， AGV)[1]屬于一種依靠電池進(jìn)行供電、配置有自動(dòng)引導(dǎo)系統(tǒng)的新型小型自動(dòng)化移動(dòng)機(jī)器人，它能按照預(yù)加載的行駛路線(xiàn)自主驅(qū)動(dòng)完成預(yù)設(shè)的搬運(yùn)目標(biāo)。

AGV多目標(biāo)優(yōu)化問(wèn)題屬于典型的性能優(yōu)化問(wèn)題,在實(shí)際工作中操作十分困難，傳統(tǒng)方法的一個(gè)缺點(diǎn)就是對(duì)目標(biāo)函數(shù)具有苛刻的形式要求。針對(duì)AGV多目標(biāo)優(yōu)化問(wèn)題的痛點(diǎn)和難點(diǎn)，大量研究學(xué)者提出了各自的優(yōu)化算法，其中比較經(jīng)典的有多目標(biāo)粒子群優(yōu)化算法[2],人工神經(jīng)網(wǎng)絡(luò)算法[3]，協(xié)同多目標(biāo)進(jìn)化算法[4]等。在1992年，Dorigo等人通過(guò)模擬自然界中螞蟻集體的尋路本能的行為首次提出了一種基于種群的啟發(fā)式仿生算法，即蟻群算法(ant colony optimization， ACO)。

本文研究了一種改進(jìn)信息交互機(jī)制的蟻群算法來(lái)求解多目標(biāo)調(diào)度問(wèn)題，對(duì)信息素的更新方式進(jìn)行了優(yōu)化，在一定程度上提高了螞蟻種群的多樣性，實(shí)驗(yàn)結(jié)果證明，改進(jìn)后的方法有效提高了傳統(tǒng)蟻群算法的尋優(yōu)能力。通過(guò)對(duì)AGV路徑優(yōu)化的關(guān)鍵技術(shù)進(jìn)行研究，可以有效的提高運(yùn)貨效率和節(jié)省運(yùn)送成本。

1 傳統(tǒng)蟻群算法求解AGV調(diào)度問(wèn)題

1.1 蟻群算法

在真實(shí)的蟻群當(dāng)中,大量個(gè)體所組成的蟻群卻展現(xiàn)出相當(dāng)復(fù)雜的群體結(jié)構(gòu)和群體行為。蟻群算法模擬了真實(shí)的螞蟻之間的相互協(xié)助尋找食物的過(guò)程。在候選的解空間中，單只螞蟻需要獨(dú)立地進(jìn)行路線(xiàn)搜尋，生物學(xué)家通過(guò)眾多對(duì)比實(shí)驗(yàn)探究得到，螞蟻個(gè)體間通過(guò)一種具有一定揮發(fā)時(shí)間的外激素進(jìn)行不同個(gè)體間的信息交互。

單個(gè)螞蟻在每個(gè)搜尋的路徑上留存一定濃度信息素，路徑上保留的信息素越多意味著路徑的候選概率也越大。隨著時(shí)間的逐漸推移，如果信息素的揮發(fā)度較大，則某些長(zhǎng)時(shí)間沒(méi)有螞蟻搜索的路徑上的信息素會(huì)逐漸消失；相反，當(dāng)揮發(fā)度較小時(shí)，已經(jīng)被搜索過(guò)的線(xiàn)路會(huì)以較大的概率被重新選擇，因此所設(shè)定的揮發(fā)因子會(huì)對(duì)算法的最優(yōu)解產(chǎn)生一定的影響。

通過(guò)文獻(xiàn)[5-6]中的例子說(shuō)明蟻群系統(tǒng)的工作原理，如圖1所示，假設(shè)A是螞蟻巢穴，E是食物的位置，蟻巢與食物之間存在一個(gè)障礙物HC。

圖1 蟻群系統(tǒng)示意圖

由于障礙物的存在，當(dāng)A從E到的時(shí)候只能先經(jīng)過(guò)H或C?，F(xiàn)在假設(shè)每個(gè)時(shí)間單位有30只螞蟻初始從A端行進(jìn)到B端，同時(shí)有30只螞蟻初始從E端行進(jìn)到D端，單個(gè)個(gè)體經(jīng)過(guò)后產(chǎn)生單位為1的信息素，同時(shí)給定單個(gè)個(gè)體所留下的信息素存在時(shí)間同樣為1。

第一步：初始狀態(tài)。由于其余路徑各條路徑上均無(wú)信息素存在，則位于B點(diǎn)和E點(diǎn)的螞蟻會(huì)隨機(jī)選擇路徑。按照統(tǒng)計(jì)學(xué)的角度來(lái)看，螞蟻會(huì)以相同的概率選擇BH、BC、DH、DC四條路徑。

第二步：當(dāng)經(jīng)過(guò)了一個(gè)時(shí)間單位后，BCD上的信息素的累積量是BHD上信息素的一倍。當(dāng)t=1時(shí)，會(huì)有約為2/3的螞蟻從B和D到達(dá)C點(diǎn)，另外約1/3只螞蟻到達(dá)。隨信息素的積累，螞蟻將會(huì)以越來(lái)越大的概率選擇路徑BCD，最終后來(lái)的所有個(gè)體能夠確定出整個(gè)搜尋過(guò)程的最佳路徑，即找到了由起始位置到終點(diǎn)的最優(yōu)路徑BCD。因此對(duì)于整個(gè)過(guò)程來(lái)說(shuō)，螞蟻個(gè)體之間的信息交換是一個(gè)正反饋過(guò)程。

1.2 針對(duì)AGV多目標(biāo)調(diào)度的蟻群算法建模

蟻群算法應(yīng)用于AGV多目標(biāo)調(diào)度問(wèn)題[7]，可以概括為通過(guò)預(yù)先給定出所有的需求點(diǎn)，最終AGV回到初始位置，使得付出的運(yùn)輸路徑成本最小。假設(shè)AGV需要到達(dá)的裝載點(diǎn)的個(gè)數(shù)為n，初始出m個(gè)個(gè)體探索整個(gè)調(diào)度過(guò)程的最優(yōu)路線(xiàn)。

當(dāng)時(shí)間為t時(shí)，第k個(gè)個(gè)體從第i號(hào)裝載點(diǎn)到第j號(hào)裝載點(diǎn)進(jìn)行轉(zhuǎn)移，轉(zhuǎn)移概率P能夠用下式進(jìn)行表示。

在進(jìn)行路徑探索時(shí)，依據(jù)每條路徑上信息素的濃度，目標(biāo)可以確定下一時(shí)刻的方向，并且當(dāng)選擇了下一方向時(shí)，會(huì)在當(dāng)前路徑上留下信息素來(lái)標(biāo)定已經(jīng)走過(guò)當(dāng)前路線(xiàn)，由于傳統(tǒng)算法中的解容易陷入局部最優(yōu)值，因此為了到達(dá)表現(xiàn)結(jié)果更好的全局最優(yōu)值，可以按照下列方式調(diào)整信息素的濃度，從而控制其揮發(fā)過(guò)程。

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

1.3 求解多目標(biāo)問(wèn)題的基本模型

對(duì)于多目標(biāo)優(yōu)化問(wèn)題，考慮到?jīng)Q策變量為可以采用如下算法進(jìn)行描述[8]。假設(shè)是維歐幾里得空間中的非空集合:

f(x)=(f1(x),f2(x), …，fm(x))T

是n維空間中的m維向量函數(shù)，并且有:

g(x)=(g1(x),g2(x),…，gm(x))T

h(x)=(h1(x),h2(x),…，hm(x))T

分別是S上的p維和q維向量函數(shù)，則在約束條件：

gi(x)≤0 (i=1,2,3，…，p)

hi(x)=0 (j=1,2,3，…，q)

下，以f1(x),f2(x), …，fm(x)為目標(biāo)函數(shù)的有限m維多目標(biāo)優(yōu)化問(wèn)題可以記作：

min/maxf(x)=F(x)=(f1(x),f2(x),…，fm(x) )T,

m=1,2,3，…，k

s.t.gi(x)≤0,i=1,2,3，…，p;hj(x)=0,j=1,2,3，…，q

f(x)是與目標(biāo)函數(shù)有關(guān)的函數(shù)，最終轉(zhuǎn)化為求解f(x)的最大值或最小值問(wèn)題，根據(jù)上式尋找滿(mǎn)足條件的矢量解。

AGV作業(yè)調(diào)度的本質(zhì)就是利用多個(gè)AGV去實(shí)現(xiàn)多個(gè)任務(wù)的合理分配過(guò)程，因此最終目的是為了優(yōu)化整個(gè)調(diào)度過(guò)程，尋求完成大量作業(yè)的最佳解決方案和先后順序，并保證在完成給定作業(yè)的前提下，總的執(zhí)行路徑最短。

2 改進(jìn)的求解多目標(biāo)優(yōu)化問(wèn)題蟻群算法

2.1 全局最優(yōu)的尋優(yōu)方式

多個(gè)目標(biāo)之間往往是相互約束、相互排斥的，其中某些目標(biāo)的改善往往會(huì)造成另一些目標(biāo)的惡化，因此各個(gè)目標(biāo)很難同時(shí)達(dá)到最優(yōu)[9]。而在實(shí)際問(wèn)題當(dāng)中，多目標(biāo)問(wèn)題的解的優(yōu)劣往往是相對(duì)的，難以達(dá)到所謂的絕對(duì)最優(yōu)，只能達(dá)到相對(duì)最優(yōu)值。求解這類(lèi)問(wèn)題往往只能得到一組最優(yōu)解集，解集內(nèi)部無(wú)法進(jìn)一步比較，這樣的解集一般稱(chēng)為Pareto最優(yōu)解。實(shí)際求解當(dāng)中，要求得到的解集具有較好的均勻性。

為了更好地指導(dǎo)目標(biāo)進(jìn)行搜索，定義一個(gè)集合A(t)來(lái)保存整個(gè)蟻群經(jīng)過(guò)多次迭代后得到的所有Pareto解集。假設(shè)當(dāng)前集合A(t)中有p個(gè)不可支配的解x，

x=(x1,x2,……,xp)

若有：

i∈A(t)

則個(gè)體目前所在的區(qū)域不能被群體所支配，需要適當(dāng)增大當(dāng)前個(gè)體所釋放的信息素的量，使得其他螞蟻會(huì)更加關(guān)注第i個(gè)個(gè)體所在的位置區(qū)域; 相反的，如果第i個(gè)個(gè)體不屬于集合A(t)，那就應(yīng)當(dāng)減小信息素的濃度。

當(dāng)多個(gè)螞蟻同時(shí)進(jìn)入A(t)時(shí)，可以利用最新進(jìn)入A(t)的個(gè)體與之前集合中所求出的目標(biāo)函數(shù)值之間的最小距離作為第i個(gè)個(gè)體所在的區(qū)域，同時(shí)在此區(qū)域內(nèi)釋放更多信息素，實(shí)現(xiàn)對(duì)單個(gè)個(gè)體的信息素增量的區(qū)分。在上述過(guò)程中，可以用下式進(jìn)行表示最小距離：

因此，可以重新定義蟻群算法的信息素：

其中：ρ為揮發(fā)系數(shù)。

在解決全局優(yōu)化的問(wèn)題時(shí)，一般無(wú)法在解空間的分布信息中得到全局的最優(yōu)解，因此最好的情況是螞蟻在解空間中的分布是相對(duì)均勻的，蟻群分布越均勻則越有利于后續(xù)的算法在實(shí)現(xiàn)中均勻地掃描解空間，從而得到最優(yōu)解。一個(gè)有效的方法是首先將解空間劃分為許多個(gè)子區(qū)域，在每個(gè)子區(qū)域中按照一定比例分配初始螞蟻，螞蟻?zhàn)畛踔辉诋?dāng)前的子區(qū)域中進(jìn)行搜索，當(dāng)局部搜索完成后，每個(gè)螞蟻按照當(dāng)前的信息素信息對(duì)全局進(jìn)行移動(dòng)搜索，當(dāng)每次完成循環(huán)后，重新對(duì)信息素的濃度進(jìn)行更新，最終達(dá)到迭代終止條件。

2.2 改進(jìn)的轉(zhuǎn)移概率和新型學(xué)習(xí)機(jī)制

在多目標(biāo)優(yōu)化算法中，最優(yōu)解會(huì)與每只螞蟻的信息素留存直接相關(guān)，不同方向的信息素留存量會(huì)直接影響到第i個(gè)個(gè)體的下一步移動(dòng)區(qū)域[10-11]，往往距離短和濃度高的區(qū)域會(huì)被以更高概率所選擇，此時(shí)的移動(dòng)概率可以表示為：

dij=f(xi)-f(xj)

在上述公式中，α和β作為一項(xiàng)權(quán)值，表明了節(jié)點(diǎn)上信息素重視程度和根據(jù)兩點(diǎn)距離因素得到的啟發(fā)式信息受重視程度。上述公式表明，第i只螞蟻盡可能地向更好的領(lǐng)域移動(dòng)，如果沒(méi)有更好的區(qū)域進(jìn)行移動(dòng)，螞蟻則會(huì)盡可能地依舊停留在原處，作為下一次移動(dòng)的初始位置。

通過(guò)以上的分析可以看出，進(jìn)行信息素的更新可以在一定程度上增強(qiáng)選擇出的最優(yōu)個(gè)體的路徑搜索能力，從而使得螞蟻可以更快速有效地搜索出最佳的路徑。但是，盡管最優(yōu)個(gè)體的搜索能力得到了提升，如果僅僅靠最優(yōu)個(gè)體去尋找最佳路徑，則搜索能力仍然有所局限，為了進(jìn)一步加強(qiáng)其他所有普通個(gè)體的搜尋能力，可以采用一定的信息交互機(jī)制，使得除最優(yōu)個(gè)體之外的個(gè)體也能實(shí)時(shí)更新信息素。

這項(xiàng)研究模擬了群體內(nèi)的不同個(gè)體相互利用彼此的觸角實(shí)現(xiàn)信息的傳遞和分享的能力，從只提升單個(gè)最優(yōu)個(gè)體路徑搜索能力到對(duì)整個(gè)蟻群路徑搜索能力的提高，將這種特殊的信息交互機(jī)制所定義的信息素濃度的更新規(guī)則用如下公式表示。

τ(i)=ρτ(i)+ητ(j)

通過(guò)上述公式可以看出，在每次進(jìn)行全局最優(yōu)解的搜索后，不僅局限于得到最優(yōu)解的個(gè)體，還會(huì)隨機(jī)選擇某一其他個(gè)體i來(lái)實(shí)現(xiàn)對(duì)信息素的更新。在上式中，η代表了個(gè)體i向最優(yōu)個(gè)體j學(xué)習(xí)的能力，定義為學(xué)習(xí)因子。ρ為揮發(fā)的系數(shù)，意味著信息的持久性。當(dāng)學(xué)習(xí)因子越高時(shí)，意味著當(dāng)前個(gè)體越可能按照之前的最優(yōu)解進(jìn)行移動(dòng)，從而使得每個(gè)普通個(gè)體都從最優(yōu)個(gè)體處得到一定的收益；而當(dāng)揮發(fā)系數(shù)越高時(shí)，則代表信息素會(huì)以更快的速度消散，導(dǎo)致該處所吸引的螞蟻的能力降低，因此在實(shí)際應(yīng)用中，應(yīng)合理地選擇信息交互機(jī)制中的參數(shù)。

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

3.1 實(shí)驗(yàn)描述

實(shí)際AGV工作過(guò)程中，整個(gè)AGV調(diào)度系統(tǒng)通過(guò)中央調(diào)度系統(tǒng)配置服務(wù)器對(duì)AGV進(jìn)行任務(wù)分配，AGV調(diào)度系統(tǒng)架構(gòu)如圖2所示。在本次實(shí)驗(yàn)過(guò)程中采用Matlab進(jìn)行仿真和測(cè)試。

圖2 AGV調(diào)度系統(tǒng)架構(gòu)圖

為了進(jìn)行驗(yàn)證改進(jìn)后的算法是否能夠盡快收斂到求解多目標(biāo)優(yōu)化問(wèn)題的最優(yōu)解，分別設(shè)置傳統(tǒng)蟻群算法和改進(jìn)后的蟻群算法進(jìn)行對(duì)比。在連續(xù)空間的優(yōu)化問(wèn)題中，可以適當(dāng)提高螞蟻的數(shù)量。

對(duì)于實(shí)驗(yàn)中的其他各項(xiàng)參數(shù)，設(shè)置M為60，對(duì)于改進(jìn)后的直接通信方式中，設(shè)置其交叉概率設(shè)置為0.95，變異概率設(shè)置為0.05,對(duì)于信息素的揮發(fā)程度給定參數(shù)為0.2。為了進(jìn)行公平的對(duì)比，在進(jìn)行實(shí)驗(yàn)仿真時(shí)采用相同的群體規(guī)模。同時(shí)，對(duì)于不同配送點(diǎn)之間的轉(zhuǎn)移概率，通過(guò)輪盤(pán)賭的方式進(jìn)行配送點(diǎn)轉(zhuǎn)移選擇，選擇這種方法可以更有效地通過(guò)概率進(jìn)行優(yōu)化轉(zhuǎn)移。初始各配送點(diǎn)的坐標(biāo)如圖3所示。

圖3 不同配送點(diǎn)位置坐標(biāo)

3.2 實(shí)驗(yàn)結(jié)果

將蟻群算法和改進(jìn)后的蟻群算法比較，由于算法本身為隨機(jī)優(yōu)化算法，因此選擇進(jìn)行多次優(yōu)化，每次優(yōu)化迭代設(shè)置相同的迭代次數(shù)400次。得到結(jié)果如圖4～5所示，可以看出隨著迭代次數(shù)的增加，整個(gè)過(guò)程中算法具有較快的收斂速度，僅僅在50次迭代后，最短距離就已經(jīng)基本不在變化。

圖4 傳統(tǒng)算法最優(yōu)路徑規(guī)劃

圖5 改進(jìn)算法最優(yōu)路徑規(guī)劃

圖4和圖5為傳統(tǒng)蟻群算法和改進(jìn)后的蟻群算法分別求解最優(yōu)路徑的結(jié)果，從左圖中可以直觀看出，對(duì)于傳統(tǒng)算法，進(jìn)行AGV調(diào)度時(shí),路徑選擇更加復(fù)雜，產(chǎn)生不穩(wěn)定的結(jié)果，容易陷入局部最優(yōu)解，導(dǎo)致花費(fèi)更多的運(yùn)輸成本，降低了整個(gè)調(diào)度的效率。而從改進(jìn)后的算法可以看出，此時(shí)的規(guī)劃路徑更加清晰，總調(diào)度距離明顯要優(yōu)于傳統(tǒng)算法。之后進(jìn)行各代最短距離和平均距離的對(duì)比，如圖6和圖7所示。

圖6 平均距離隨迭代次數(shù)的變化對(duì)比(傳統(tǒng)算法)

圖7 平均距離隨迭代次數(shù)的變化對(duì)比(改進(jìn)算法)

從圖中可以看出，傳統(tǒng)算法需要100次迭代后逐漸趨于穩(wěn)定值，而改進(jìn)算法僅需要約50代便可收斂，具有較好的收斂速度和收斂精度，在達(dá)到最終迭代效果后，可以看出，改進(jìn)后算法平均距離要小于傳統(tǒng)算法，能夠有效地提高AGV調(diào)度的效率，降低運(yùn)送成本。

4 結(jié)論

針對(duì)AGV調(diào)度優(yōu)化中常出現(xiàn)的陷入局部最優(yōu)的問(wèn)題，本文研究了一種采用知識(shí)性信息素更新方法和改進(jìn)轉(zhuǎn)移概率與直接學(xué)習(xí)機(jī)制的蟻群算法。利用AGV調(diào)度來(lái)模擬螞蟻交流信息的過(guò)程，從而實(shí)現(xiàn)AGV的直接通信學(xué)習(xí)機(jī)制，通過(guò)這種方法更新后的信息素可以更好地維持整個(gè)群體的多樣性，最終實(shí)現(xiàn)AGV調(diào)度優(yōu)化問(wèn)題中的最優(yōu)解。

本文以AGV多目標(biāo)優(yōu)化調(diào)度為模型，對(duì)運(yùn)貨車(chē)的配送調(diào)度問(wèn)題進(jìn)行了分析和探討，建立了簡(jiǎn)潔的數(shù)學(xué)模型對(duì)復(fù)雜的問(wèn)題進(jìn)行簡(jiǎn)化和分析。在實(shí)驗(yàn)中，除了對(duì)局部最優(yōu)解進(jìn)行信息素更新，也利用了其他非最優(yōu)解間的直接通信學(xué)習(xí)機(jī)制，這種學(xué)習(xí)機(jī)制能夠有效提高種群的持久性，從而選擇出更優(yōu)秀的個(gè)體，趨近于最優(yōu)解。通過(guò)實(shí)際實(shí)驗(yàn)對(duì)比，設(shè)置在相同的參數(shù)條件下，改進(jìn)后的蟻群算法具有更好的性能表現(xiàn)，是一個(gè)能更有效地解決車(chē)輛調(diào)度路徑優(yōu)化問(wèn)題的算法。

采用直接通信機(jī)制的蟻群算法可以有效地解決AGV任務(wù)作業(yè)調(diào)度問(wèn)題，這種方法不僅提高了運(yùn)貨效率，并且節(jié)省了運(yùn)送成本，對(duì)AGV調(diào)度管理有很好的指導(dǎo)意義，本文中所實(shí)現(xiàn)的改進(jìn)后的蟻群算法算法是一種有效地最優(yōu)化問(wèn)題解決方案，值得進(jìn)一步研究。