基于蟻群算法的煤炭運輸優(yōu)化方法

第25卷,第3期中國鐵道科學(xué)Vol.25 No.30022004年6月CHINA RAILWAY SCIENCEJune, 2004文章編號: 1001-4632 (2004) 03-0126-04基于蟻群算法的煤炭運輸優(yōu)化方法李智(武漢工業(yè)學(xué)院電氣信息工程系，湖北武漢430023)摘要: 蟻群算法是指通過(guò)人工模擬螞蟻搜索食物的過(guò)程來(lái)求解運輸優(yōu)化問(wèn)題的一種算法。給出蟻群算法模型及算法步驟。研究- -種帶容限制和考慮損耗的煤炭運輸數學(xué)模型的優(yōu)化計算，并給出算法步驟。運用蟻群算法對某- -鋼鐵企業(yè)煤埃運輸問(wèn)題進(jìn)行優(yōu)化計算,計算結果符合實(shí)際生產(chǎn)情況。關(guān)鍵詞:鐵路運輸組織;煤炭運輸;蟻群算法;優(yōu)化計算中圈分類(lèi)號: U294.15: TP18文獻標識碼: A力，不僅利用了正反饋原理，在一定程度上加快了1引言進(jìn)程的速度，而且是一種本質(zhì)并行的算法，不同個(gè)體之間不斷進(jìn)行著(zhù)信息交流和傳遞，從而能夠相互人工螞蟻算法是受到人們對自然界中真實(shí)螞蟻協(xié)作,有利于發(fā)現較好的解。群體行為的研究成果的啟發(fā)而提出的一種基于種群的模擬進(jìn)化算法，屬于隨機搜索算法的-種。最早2蟻群算法由意大利學(xué)者M(jìn).Dorigo 等人提出，在充分利用螞蟻群體搜索食物的過(guò)程和著(zhù)名的旅行商問(wèn)題2.1 蚊群算法原理”(TSP)之間的相似性，通過(guò)人工模擬螞蟻搜索食自然界螞蟻群體協(xié)作行為主要包括:在沒(méi)有任物的過(guò)程求解TSP問(wèn)題，獲得了成功，故稱(chēng)之為何外界指導信息的情況下，螞蟻群體總是能找到從“人工蟻群算法”，簡(jiǎn)稱(chēng)“蟻群算法”1。在隨后的食物源到巢穴的最短路徑;蟻群中個(gè)體從事不同的研究中，又成功地將螞蟻算法應用于二次分配問(wèn)勞動(dòng)，群體可以很好地完成個(gè)體的勞動(dòng)分工;蟻群題[2]、Job-shop調度問(wèn)題[3]、網(wǎng)絡(luò )動(dòng)態(tài)路由優(yōu)化4]、中死去螞蟻的個(gè)體可以聚集在一-起,形成相對較大信帶頻率分配問(wèn)題[fs!等的求解。的墳墓。受這些螞蟻群體行為的啟迪，Dorigo 等人蟻群算法是一種隨機搜索算法，與遺傳算法、提出了幾類(lèi)不同的螞蟻算法模型。其中，對螞蟻群模擬退火算法等模擬進(jìn)化算法-樣，通過(guò)候選解組體總是能找到從食物源到巢穴的最短路徑這種情況成的群體在進(jìn)化過(guò)程來(lái)尋求最優(yōu)解6),具有以下特而抽象建立的算法模型被稱(chēng)為螞蟻系統。理論和實(shí)點(diǎn)。踐上都證明這種算法模型對求解組合優(yōu)化問(wèn)題效果(1)較強的魯櫸性:對基本蟻群算法模型稍加良好，下面說(shuō)明螞蟻系統的生物原型一真實(shí)螞蟻修改，即可應用于其它問(wèn)題的求解。群體的工作原理。(2)分布式計算:蟻群算法是一種基于種群的研究表明，自然界螞蟻尋找到從巢穴到食物源算法，具有并行性。的最短路徑是通過(guò)一種正反饋的機制實(shí)現的，單個(gè)(3)易于與其它的方法相結合:蟻群算法很容螞蟻在自己行走的路徑下留下一種揮發(fā)性分泌物，易與其它的啟發(fā)式算法相結合,以改善算法的性稱(chēng)之為信息激素，后來(lái)的螞蟻根據前進(jìn)道路上信息能。數量的多少選擇前進(jìn)方向，在經(jīng)過(guò)一個(gè)長(cháng)的過(guò)程諸多研究表明，蟻群算法具有很強的尋優(yōu)能中國煤化工息激素的量變得較收稿日期: 2003-07-11作者簡(jiǎn)介:李智(1964-), 男，湖北武漢人，博士研究生,副教授。fYHCNMHG第3期基于蟻群算法的煤炭運輸優(yōu)化方法27大,而螞蟻越來(lái)越多地集中在信息激素量較大的路Or,= Q/L,(3)徑上，從而找到了- -條最短路徑。Ot,表示第j只在本次循環(huán)中吸引強度的增加;螞蟻行為的實(shí)質(zhì)是簡(jiǎn)單個(gè)體的自組織行為體現Q為正常數,其范圍0< Q< 10 000; L,表示本次出來(lái)的群體行為，每個(gè)螞蟻行為對環(huán)境產(chǎn)生影響，循環(huán)中f(x)的增量，定義為f(x+r)-f(x);0≤環(huán)境的改變進(jìn)而對蟻群行為產(chǎn)生控制壓力，影響其ρ≤1, 體現強度的持久性。于是，函數f(x)的尋他螞蟻的行為。通過(guò)這種機制，簡(jiǎn)單的螞蟻個(gè)體可優(yōu)就借助m個(gè)螞蟻的不斷移動(dòng)來(lái)進(jìn)行:當η≥0以相互影響，相互協(xié)作，完成- -些復雜的任務(wù)。時(shí),螞蟻i按概率p。從其鄰城i移至螞蟻j的鄰域;自組織使得螞蟻群體的行為趨向結構化，其原當η≤0時(shí),螞蟻i做鄰域搜索(搜索半徑或步長(cháng)為因就是包含了一個(gè)反饋的過(guò)程，這也是螞蟻算法最r),即每個(gè)螞蟻要么轉移至其他螞蟻處，要么進(jìn)行重要的特征。正反饋是系統演化發(fā)展的原因，這個(gè)鄰域搜索。過(guò)程利用了全局信息作為反饋，通過(guò)對系統演化過(guò)由此可見(jiàn)，當螞蟻的數量足夠多，搜索半徑足程中較優(yōu)解的自增強作用，使得問(wèn)題的解向著(zhù)全局夠小，這種尋優(yōu)方式相當于一群螞蟻對定義區間最優(yōu)的方向不斷進(jìn)化，最終能有效地獲得相對較優(yōu)[a, b]做窮盡的搜索，逐漸收斂到問(wèn)題的全局最的解。優(yōu)解。2.2蚊群算法模型及其實(shí)現上述函數優(yōu)化過(guò)程不受優(yōu)化函數是否連續、是Dorigo等人提出的螞蟻群體優(yōu)化的元啟發(fā)式規否可微等限制，較之經(jīng)典搜索方法具有明顯的優(yōu)越則較好地描述了蟻群算法的實(shí)現過(guò)程，其過(guò)程可以性和穩定性。表示如下。函數優(yōu)化問(wèn)題的蟻群算法步驟: .當沒(méi)有達到結束條件時(shí)，執行以下活動(dòng):(1) count←0 (count是迭代步數或搜索次數);(1)螞蟻的行為，即是螞蟻在-定的限制條件各τ,和Or,初始化;下尋找一條路徑;(2)將m個(gè)螞蟻置于各自的初始鄰域;每個(gè)(2)軌跡(即信息激素)濃度的揮發(fā);螞蟻按概率p。移動(dòng)或做鄰域搜索;(3)后臺程序，主要是完成單個(gè)螞蟻無(wú)法完成(3)計算各個(gè)螞蟻的目標函數Z;(k= 1.2.*，的任務(wù)，比如說(shuō)根據全局信息對信息激素濃度進(jìn)行m),記錄當前的最好解;更新;(4)按強度更新方程修正軌跡強度;達到條件，結束。(5) Ot,修正,count←count + 1;由于最初的蟻群算法思想起源于離散的網(wǎng)絡(luò )路(6)若count小于預定的迭代次數，則轉到步徑問(wèn)題，下面以- -維搜索為例，引申到n維空間的驟(2);函數求解。(7)輸出目前的最好解。在函數優(yōu)化問(wèn)題中,假定優(yōu)化函數為:在具體的算法過(guò)程中，鄰域設定可根據具體優(yōu)minZ = f(x) x∈[a,b]設m個(gè)人工螞蟻，剛開(kāi)始時(shí)位于區間[a, b]化問(wèn)題來(lái)定，比如一維問(wèn)題就是直線(xiàn)搜索，二維問(wèn)題可定義為圓等。搜索半徑的大小和所要得到的最的m等分處，螞蟻的轉移概率定義為:優(yōu)解的精度有關(guān)，若問(wèn)題的局部最優(yōu)點(diǎn)密集，全局pi =-法.(1)最優(yōu)解不易得到時(shí)， 則必須設置較小的r,螞蟻個(gè)數m則主要和搜索空間(定義域)有關(guān)，搜索空其中, P;表示螞蟻從位置i轉移到位置j的概間越大， 所需要的螞蟻個(gè)數越多。率; r,表示螞蟻j的鄰域吸引強度; η表示目標函數差異值，即η。= f,(x)- f;(x);參數a,β∈[1,3煤炭運輸問(wèn)題及數學(xué)模型5],該范圍的取值是-個(gè)經(jīng)驗值，目前尚無(wú)理論上中國煤化工+分復雜的過(guò)程，的依據。C N MH G同，其數學(xué)模型強度更新方程:MH=叫+ 20r,(2)的表達方式也不一-樣， 有的甚至是組合優(yōu)化問(wèn)題，在數學(xué)上屬于典型的NP難解問(wèn)題。這類(lèi)問(wèn)題如采128中國鐵道科學(xué)第25卷用傳統的數學(xué)方法很難求出其優(yōu)化解，而蟻群算法炭產(chǎn)地， 5個(gè)需求地的情況，從i產(chǎn)地(i = 1,2,3)這一建立在現代優(yōu)化理論基礎上的生物進(jìn)化算法，到j(luò )需求地(j = 1,2,3,4,5) 的運價(jià)Cj、損耗費用卻能有效地解決此類(lèi)問(wèn)題。hj及運輸量上限d;分別如表1、表2和表3所示，煤炭運輸問(wèn)題根據目標的類(lèi)型，可以將問(wèn)題分運輸量的最小限制取0。為線(xiàn)性問(wèn)題與非線(xiàn)性問(wèn)題;單目標問(wèn)題和多目標問(wèn)衰1運價(jià)題。根據約束的類(lèi)型又可將問(wèn)題分為二維問(wèn)題或三產(chǎn)地BB2B需求地/萬(wàn)元(萬(wàn))-1B. Bs發(fā)送量/萬(wàn)t維問(wèn)題，以及平衡問(wèn)題和非平衡問(wèn)題。煤炭運輸問(wèn)題往往都帶有容量的上下限和損耗費用。Al10A2本文主要討論--種帶容量限制和考慮損耗的煤As200炭運輸數學(xué)模型的優(yōu)化計算。需求量設由產(chǎn)地A;運送煤炭到需求地B,，且損失費用為hj (元),運量的下限為f,(個(gè)單位),運量的上表2運輸損耗費用限為dy(個(gè)單位),并設由A;地運送到B,的煤炭量需求地萬(wàn)元BB2 BBB為x;, (個(gè)單位),則帶有容量和損耗費用的平衡煤炭A9運輸數學(xué)模型可描述為:33 10A:minz =(4)_需求量 3_ 5_ 4s.t.=a;i=1,2,,m(5)衰3運輸量上限之工需求地萬(wàn)=b, j= 1,2,",n(6)B。 Bf;≤x≤d; i = 1,2,",m;j = 1,2,"",n(7)8[1，xg>0為e =0，x; =0(8)采用MatLab語(yǔ)言編制煤炭運輸的蟻群算法優(yōu)i = 1,2,",m;化計算程序，仿真程序在CPU1133MHz,j = 1,2,,n(9)RAM256MB的PC機上運行，仿真計算結果如表4所示。.xi≥0 Vi,j(10)褻4運輸優(yōu)化結果式(4) ~ (10) 中，諸常數均非負，在編制需求地/萬(wàn)程序時(shí)，將下界限制fo≤xg經(jīng)變量替換x'; =B2 B:B。 B.xj -f,,可以化為非負限制。目標函數式(4) 中的第- -項是總的煤炭運輸價(jià);第二項是總的運輸損耗費用。式(5)、式(6)是煤炭產(chǎn)地生產(chǎn)量、需求地min2=296 (萬(wàn)元)需求量的約束;式(7)是容量約束;式(8)是當選擇某條線(xiàn)路時(shí)，就有損耗費用產(chǎn)生的條件約束，目標函數最優(yōu)值296萬(wàn)元，即合計總費用296當y。=1時(shí)，該線(xiàn)路有損失費用產(chǎn)生，反之,無(wú)損元, 其中煤炭運輸價(jià)244萬(wàn)元,損耗費用52萬(wàn)失費用產(chǎn)生;式(9)是平衡條件約束;式(10)元。是決策變量的非負約束。中國煤化工4實(shí)例仿真MHCNMHG本文通過(guò)采用蟻群算法對含有容量限制和損耗以某鋼鐵運輸企業(yè)的實(shí)際運輸為例。有3個(gè)煤費用的煤炭運輸問(wèn)題進(jìn)行 了求解，計算結果表明結第3期基于蟻群算法的煤炭運輸優(yōu)化方法129論是正確的。工程上的普及應用。仿真過(guò)程還表明，蟻群算法求解此類(lèi)問(wèn)題，不相信隨著(zhù)蟻群算法等基于生物學(xué)原理發(fā)展起來(lái)需要技術(shù)人員具有過(guò)多、過(guò)深的數學(xué)知識，也不論的優(yōu)化計算 方法研究的不斷深人和發(fā)展，其應用領(lǐng)優(yōu)化對象的數學(xué)模型是否具有可導、連續等特點(diǎn)，域也會(huì )越來(lái)越廣 泛，各行業(yè)的一些復雜難解的工程都能夠正確地進(jìn)行求解，因此，特別適合各行各業(yè)實(shí)際問(wèn)題的求解 會(huì )變得更加容易。參文獻[1] Dorigo M, Bocabeau E, Therala G. Ant Agorthns and Stigmergy [J]. Future Generation Computer System, 2000,16: 851-871.[2] Manieo V, Colomi A. The Ant Systen Applied to the Quadratic Asigmnent Problem [J]. IEEE Trans on Knowledgeand Data Engineering, 199，1 (5): 769-778.[3] Colomi A, Dorigo M, Maniezo V, Trbian M. Ant System for Job-shop Scheduling [J]. Belgian Joumal Operations Re-search Statistic Computation Science, 1994, 34: 39- -53.[4]張素兵， 劉澤民.基于螞蟻算法的分級QOS路由調度方法[J]. 北京郵電大學(xué)學(xué)報, 2000, 23 (4): 11-15.[5]Maniezzo V, Carbonaro A. An Ants Heuristic for the Frequency Assignment Problem []. Future Generation ComputerSystem, 2000，16: 927- -935.[6]馬良. 來(lái)自昆蟲(chóng)世界的尋優(yōu)策略一螞蟻算法[J].自然雜志，199, 21 (30): 161- -163.[7] 魏平,熊偉清.用于-般函數優(yōu)化的蚊群算法[J]. 寧波大學(xué)學(xué)報，2001, 14 (4): 52--55.[8]李致中,史峰,孫焰, 等.鐵道運輸管理的數學(xué)模型及算法[M]. 武漢:華中理工大學(xué)出版社，1995.[9] 謝政,多磊,湯澤澄.帶容量限制和手續費用的運輸問(wèn)題[J]. 系統工程, 1998, 16 (5): 25- -30.Optimization Model of Coal TransportationBased on Ant Colony AlgorithmLI Zhi(Department of Electric and Information Enineering, Wuhan Polytechnic University, Wuhan Hubei 430023, China)Abstract: The main idea of Ant Colony Algorithms is to rifially simulate the process of ants seeking food tofind optimal solutions to the transportation problem at hand. Ant Colony Algorithms Model and concrete stepsare introduced in the optimization of a mathematical model of c∞oal transportation problems with volume restric-tion and consideration of loss. Simulation result shows that optimization of coal transportation problems for oneiron & steel enterprise c∞onforms to production reality.Key words: Railway taffic organization; Coal transportation; Ant colony algorithm; Optimization calculation(責任編輯劉衛華)中國煤化工MYHCNMHG