用蟻群算法實(shí)現(xiàn)自動(dòng)化倉(cāng)庫(kù)路徑優(yōu)化

1、用蟻群算法實(shí)現(xiàn)自動(dòng)化倉(cāng)庫(kù)揀選路徑的優(yōu)化林家恒賀慶(山東大學(xué)濟(jì)南， 250061)摘要 蟻群算法是一種解決 TSP問(wèn)題的良好方法，算法的主要特點(diǎn)是：正反饋、分布式計(jì)算、與某種啟 發(fā)式算法相結(jié)合。該算法共有三種形式。本文通過(guò)對(duì)比試驗(yàn)，選擇了一種應(yīng)用到解決自動(dòng)化倉(cāng)庫(kù)的路徑優(yōu) 化問(wèn)題中。計(jì)算機(jī)仿真結(jié)果表明了該算法的有效性。關(guān)鍵詞 蟻群算法，自動(dòng)化倉(cāng)庫(kù)，固定貨架，路徑優(yōu)化1引言自動(dòng)化立體倉(cāng)庫(kù)是現(xiàn)代物資存取技術(shù)與自動(dòng)化技術(shù)相結(jié)合的高新技術(shù)產(chǎn)物，是物流自動(dòng)化的顯著標(biāo)志，它一般由多排立體的固定貨架及堆垛機(jī)系統(tǒng)、輸送系統(tǒng)、分揀系統(tǒng)、計(jì)算機(jī)管理與監(jiān)控系統(tǒng)等部分組成，一般具有單元出(入)庫(kù)、揀選出(入)庫(kù)、盤(pán)庫(kù)和倒

2、庫(kù)等多 種作業(yè)方式。在各種作業(yè)方式中，揀選出(入)庫(kù)作業(yè)是一類(lèi)重要的作業(yè)方式。揀選入(出)庫(kù)是指 堆垛機(jī)從巷道口出發(fā)，一次存取若干個(gè)貨位，然后返回巷道口，并將貨箱送到出貨臺(tái)。這就存在一個(gè)優(yōu)化問(wèn)題：如何選擇作業(yè)排序可使堆垛機(jī)走過(guò)的路徑或作業(yè)時(shí)間最短？這個(gè)問(wèn)題是 提高倉(cāng)庫(kù)效率的關(guān)鍵。目前針對(duì)它已有許多解法，如窮舉搜索法(Exhaustive Search Method),貪心法(Greedy Method),動(dòng)態(tài)規(guī)劃法( Dynamic Programming Method)分支界定法(Branch-And-Bound )，遺傳算法(Genetic Agorithm )等。本文使用了一種新的算法一

3、蟻群 算法，該算法是一種新型的模擬進(jìn)化算法，該算法比較容易實(shí)現(xiàn)，而且比較靈活，經(jīng)過(guò)仿真試驗(yàn)，證明是一種有效的方法。2優(yōu)化問(wèn)題的建模倉(cāng)庫(kù)貨架主要分為固定貨架和旋轉(zhuǎn)貨架。固定貨架以其占用空間少、存儲(chǔ)容量大而廣 泛應(yīng)用于自動(dòng)化立體倉(cāng)庫(kù)中。本文以固定貨架為例說(shuō)明問(wèn)題。 口 口 口口口 口冒 門(mén)呂 口呂口口 口口 口出貨臺(tái)貨架側(cè)視圖D-出貨臺(tái) 口 口口 口口貨架俯觀圖圖1具有4層12列的固定貨架如上圖所示，每個(gè)單元貨位中放一種貨物，在揀選入(出)庫(kù)作業(yè)時(shí)，由管理計(jì)算機(jī)控制堆垛機(jī)從出貨臺(tái)出發(fā)，根據(jù)計(jì)算機(jī)中的貨單要求去存取M個(gè)貨位，再回到出貨臺(tái)待命。因?yàn)槎讯鈾C(jī)可同時(shí)在水平、垂直兩個(gè)方向運(yùn)行，所以堆垛機(jī)從貨位

4、i運(yùn)行到貨位j所需要得時(shí)間是：d ij = max(Xi-Xj/Vx, yi-yj/Vy)其中X ,yi ), (Xj, yj)為i , j兩點(diǎn)的坐標(biāo)，Vx,Vy為堆垛機(jī)的水平、垂直速度?？梢?jiàn)堆垛機(jī)所需最短時(shí)間問(wèn)題，可轉(zhuǎn)化為包括出貨臺(tái)在內(nèi)的點(diǎn)數(shù)為N = M + 1的旅行商問(wèn)題。3算法原理仿生學(xué)家經(jīng)過(guò)大量細(xì)致觀察研蟻群算法是受到對(duì)真實(shí)的蟻群行為的研究啟發(fā)而提出的。究發(fā)現(xiàn)，螞蟻個(gè)體之間是通過(guò)一種稱為外激素的物質(zhì)進(jìn)行信息傳遞的，螞蟻在運(yùn)動(dòng)過(guò)程中， 能夠在它所經(jīng)過(guò)的路徑上留下外激素，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并且以此指導(dǎo)自己的運(yùn)動(dòng)方向， 所以，大量的螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息

5、正反饋現(xiàn) 象。我們并不想完全模擬蟻群，而是對(duì)使用人工蟻群方法來(lái)解決優(yōu)化問(wèn)題感興趣因此，我們的蟻群與實(shí)際的蟻群有三個(gè)主要的區(qū)別：?人工蟻群具有記憶性，?人工蟻群不是完全盲目的，D?人工蟻群處在離散的時(shí)間環(huán)境中。H C雖然有區(qū)別，我們?nèi)匀豢梢杂梦浵伻旱男袨閬?lái)形象地說(shuō)明人工蟻群 算法的原理。如圖 2所示，設(shè)DH = HB=1,DC = CB=0.5。我們假定在每個(gè)離散的等時(shí)間間隔：t = 0,1,2,有3 0個(gè) 螞蟻從A到達(dá)B,同時(shí)有3 0個(gè)螞蟻從E到D,每只螞蟻的速度為 1/S，并且，每有一只螞蟻經(jīng)過(guò)時(shí)，在時(shí)間t留下信息素密度為1。螞蟻在選擇路徑時(shí)，那些有更多螞蟻曾經(jīng)選擇過(guò)的路徑(也就是具有更高信

6、息素密度的路徑)，被再次選中的可能性最大。當(dāng)t = 0時(shí)，沒(méi)有信息素，有30只螞蟻分別在B和D。 螞蟻?zhàn)吣臈l道路是完全隨機(jī)的。 因此，在每個(gè)點(diǎn)上螞蟻將有15只經(jīng)過(guò)H,另外15只經(jīng)過(guò)C。當(dāng)t = 1時(shí)有30只螞蟻從A到B,它們發(fā)現(xiàn)指向H道路上的信息素密度是15,是由從B出發(fā)的螞蟻留下的；指向C道路上的信息素密度是30,其中15是由B出發(fā)螞蟻留下，另外15是從D出發(fā)經(jīng)過(guò)C已經(jīng)到達(dá)B的螞蟻留下。因此，選擇經(jīng)過(guò)C到D的可能性就更大，從E出發(fā)到D的30只螞蟻也面臨著同樣的選擇，由此產(chǎn)生一個(gè)正反饋過(guò)程， 選擇經(jīng)過(guò)C的螞蟻越來(lái)越多，直到所有的螞蟻都選擇這條較近的道路。蟻群算法就是利用螞蟻的這一特性, 解決最

7、優(yōu)化問(wèn)題。4蟻群算法的實(shí)現(xiàn)運(yùn)用蟻群算法。設(shè)dm為堆垛機(jī)從貨位i運(yùn)動(dòng)到j(luò)所耗費(fèi)的時(shí)間， d耳=max ( 乂 一 x j / V x， y - y m / Vy)。設(shè)b比)表示t時(shí)刻位于貨位i的螞蟻的個(gè)數(shù)，n螞蟻總數(shù)m= a b t，* ij t表示t時(shí)刻在i j連線上殘留的信息量，初始時(shí)刻各條路徑i =1上的信息量為 ij 0 =C(C為常數(shù))。用參數(shù)'表示信息量的保留度，則經(jīng)過(guò)n個(gè)時(shí)刻 后，路徑i j上的信息量根據(jù)下式作調(diào)整： j (t ' n)j(t)耳m.:.八 皆ijj二芻：表示第k只螞蟻在本次循環(huán)中留在路徑i j上的信息量，二？ j表示本次循環(huán)所有經(jīng)過(guò)的螞蟻留在i j

8、上的信息量。0當(dāng)?shù)趉只螞蟻經(jīng)過(guò)當(dāng)不經(jīng)過(guò)時(shí)kPij表示在t時(shí)。螞蟻 k（k=l,定義 =1/ij刻螞蟻k由位置i轉(zhuǎn)移到位置j的概率:du2,，m ）在運(yùn)動(dòng)過(guò)程中，kPij =i Z T； | s Wallowd k0ijj j't n-Tj allowed k其他00我們用tabu,k =1,2,m）記錄螞蟻k目前已經(jīng)走過(guò)的貨位集合，allow dk表示螞蟻k下一步允許選擇的貨位集合， 它等于全部的貨位集合除去第k只螞蟻已走過(guò)的集合tabuk。定義|_ k為第k只螞蟻在本次循環(huán)中耗費(fèi)的時(shí)間和。用蟻群算法解決存取路徑問(wèn)題是一個(gè)遞推過(guò)程，當(dāng)t = 0時(shí)，將螞蟻放在各貨位，設(shè)定每條路徑上的信息

9、量初值.jj 0 =C，每只螞蟻根據(jù)公式?jīng)Q定的概率從貨位i到貨位j。弋耳（t）表示曾經(jīng)有多少螞蟻經(jīng)過(guò)路徑（i , j ）； n ,說(shuō)明較近的貨位有更大的可能性被 選中。a , B用來(lái)控制兩者對(duì)螞蟻選擇的影響力程度。經(jīng)過(guò)一個(gè)循環(huán)后，根據(jù)公式計(jì) 算更新每條路徑的信息量 .耳t。將所有的tabuMk =1,2，,m）復(fù)原，最后求出本次循環(huán) 的所耗費(fèi)的最短時(shí)間minL k。這個(gè)過(guò)程不斷重復(fù)，直到所有的螞蟻都選擇同樣的路徑，或者循環(huán)次數(shù)達(dá)到預(yù)先設(shè)定的最高次數(shù)NC 。max根據(jù)貨單要求，存取 n個(gè)貨物算法設(shè)計(jì)如下：1初始化：設(shè)定t = 0,循環(huán)計(jì)數(shù)器NC=0, 對(duì)每條路徑設(shè)定初始信息量 .” 0 = C,

10、 = 耳=0 將m只螞蟻放在n個(gè)貨位上（為了使問(wèn)題簡(jiǎn)化，設(shè)定m=n）。2 .設(shè)定tabu集合的索引s = 1, 對(duì)k從1到m,把第k只螞蟻放在起始位置，對(duì)應(yīng)的設(shè)定集合tabu k s3 .重復(fù)下面的步驟，直到集合tabu滿為止（這一步將重復(fù)n 1次）：設(shè)定s = s + 1;對(duì)k從1到m,根據(jù)公式確定的概率，選擇下一步移動(dòng)的目標(biāo)貨位j 在時(shí)間t時(shí)，第k只螞蟻所在的貨位是i = tabuk s-1 ；將第k只螞蟻移到j(luò);把j加入到集合tabuks中。4.對(duì)艮從1到m:將第k只螞蟻從tabuk n移動(dòng)到tabuk1 ；計(jì)算第k只螞蟻所耗費(fèi)的時(shí)間和L k，并更新最小時(shí)間和minLk ；對(duì)每條路徑（i

11、, j ）： iTiJk =丿Q當(dāng)?shù)趉只螞蟻經(jīng)過(guò)Lki j時(shí)0當(dāng)不經(jīng)過(guò)時(shí)& II沁弋 ii +"i：；5 對(duì)每條路徑（i , j ）根據(jù),.（t n）=.耳（t） ?耳計(jì)算.ij t n ；設(shè)定t = t + n;設(shè)定NC=NC+1;對(duì)每條路徑（i, j），設(shè)定A孔=0o6 .如果NCVNCmax，則清空所有的集合tabu轉(zhuǎn)到第二步；否則，得出最優(yōu)的路徑。在這兒我們介紹的是ant-cycle 算法，這種算法，每當(dāng)結(jié)束一個(gè)循環(huán)后，根據(jù)公式計(jì)算 ： °另外還有兩種蟻群算法，不需要等到循環(huán)結(jié)束，每一步都更新，一種稱為an t-de nsity,k Q 在時(shí)間t到t+仲當(dāng)?shù)?/p>

12、k只螞蟻經(jīng)過(guò)路徑i j時(shí)公式：也5 =ij 0不經(jīng)過(guò)時(shí)另一種稱為an t-qua ntity,公式：_i： =在時(shí)間t到t - 1中當(dāng)?shù)趉只螞蟻經(jīng)過(guò)路徑i j時(shí)不經(jīng)過(guò)時(shí)5實(shí)驗(yàn)結(jié)果及分析我們分別采用 ant-cycle、ant-quantity、ant-density算法，以存取 30個(gè)貨位為例，使用Visual C+6.0 在pentium550pc機(jī)上運(yùn)行通過(guò)，我們對(duì)各參數(shù)分別設(shè)如下值進(jìn)行仿真a 0 , 0.5,1,2,5,3 0,1,2,5, p 0.3,0.5,0.8,0.9, NCmax C 100,1000,2000 ,3000 ,Q 1, 100, 1000°取有代表性的

13、結(jié)果列表如下:表1三種蟻群算法的優(yōu)化結(jié)果對(duì)比表算法a3PQNC max最優(yōu)路徑耗 時(shí)(秒)an t-cycle120.5101000193.437an t-qua ntity120.5101000199.569an t-de nsity120.5101000208.758表2不同的參數(shù)所得優(yōu)化結(jié)果對(duì)比表a3PQNC max最優(yōu)路徑 耗時(shí)(秒)000.31500653.4810.520.51200262.7940.520.510200262.8840.520.5100200261.766150.5100200232.196150.5100500226.652150.51001000193.941

14、通過(guò)大量的實(shí)驗(yàn)我們得出如下結(jié)論：(1) ant-cycle 算法與另外兩種算法相比，具有更好的優(yōu)化效果；(2) a決定信息量對(duì)路徑選擇的影響程度，B決定從i運(yùn)行到j(luò)所耗時(shí)間對(duì)選擇的影響程 度。經(jīng)過(guò)試驗(yàn)發(fā)現(xiàn)當(dāng) a = 1, B 1,2,5時(shí)可以取得較好解；(3 )Q的值對(duì)結(jié)果并沒(méi)有多大的影響；(4)循環(huán)次數(shù)越多，最優(yōu)化結(jié)果越好，但是達(dá)到1 0 0 0次以后，在提高循環(huán)次數(shù)就沒(méi)有 太明顯的影響。當(dāng)a =1, 3 =5,如下圖所示，圖3為最優(yōu)化結(jié)果隨循環(huán)次數(shù)下降曲線，圖4為NCmax =100°時(shí)，所得出的最優(yōu)路徑曲線:圖3最優(yōu)化結(jié)果進(jìn)化曲線6結(jié)論自動(dòng)化立體倉(cāng)庫(kù)的路徑優(yōu)化問(wèn)題一直阻礙存取貨

15、物效率的提高。蟻群算法具有全局優(yōu)化特性，是解決TSP問(wèn)題的有效算法。本文將這一算法應(yīng)用到立體倉(cāng)庫(kù)的路徑優(yōu)化中，通過(guò)對(duì)比試驗(yàn)，選擇了其中的ant-cycle 算法；找到了一組效果較好的參數(shù)。仿真實(shí)驗(yàn)說(shuō)明了算法 的有效性。參考文獻(xiàn)1 Colorni A,Dorigo M.Maniezzo V.Distributed optimization by ant colonies.Proc 1st Europen conf artificial life.Pans,France:Elsevier,1991:134-1422 Colorni A,Dorigo M,Maniezzo V.Aninvestiga

16、tion of some properties of an ant algorithm.Proc PPSN'92:509 -5203 Marco Dorigo,Vittorio Maniezzo,Alberto Colorni.Ant system:optimization by a colony of cooperating agents.IEEE Transactions on Systems,Man,and Cybernetics-Part B: Cybernetics,Vol.26,NO.1,February 1996:29-414 G.D.Caro,M.Dorigo, ” A

17、ntNet:A Mobile Agents Approach to Adaptive Routing ” ,Technical Report IRIDLA 97-125 林家恒 . 雙伺服機(jī)分層旋轉(zhuǎn)貨架揀選路徑優(yōu)化的兩級(jí)遺傳算法 . 控制與決策， 1997，4： 332 336Order Picking Path Optimization for Automatic Warehouseby Ant AlgorithmsLin jiaheng He qing(Shandong University)Abstract Ant algorithm is a good method to solve

18、TSP problem.The main characteristics of this algorithm are positive feedback,distributed computation,and the use of a constructive greedy heuristic.The algorithm have three models.Through the contrast experiment,we choose one of them and used it to solve the path optimization of automatic warehouse.The resul