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