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