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

姜德文

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

0 引言

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

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

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

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

1.1 蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

對于多目標(biāo)優(yōu)化問題，考慮到?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)化問題可以記作：

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)的最大值或最小值問題，根據(jù)上式尋找滿足條件的矢量解。

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

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

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

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

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

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

若有：

i∈A(t)

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

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

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

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

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

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

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

dij=f(xi)-f(xj)

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

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

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

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

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

3 實驗仿真及結(jié)果

3.1 實驗描述

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

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

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

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

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

3.2 實驗結(jié)果

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

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

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

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

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

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

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

4 結(jié)論

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

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

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