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

第32卷第1期Vol. 32 , No.012013年1期Coal TechnologyJanuary ,2013基于蟻群算法的煤炭運輸優(yōu)化方法高攀,郭理(石河子大學(xué)信息科學(xué)與技術(shù)學(xué)院，新疆石河子832000)摘要:本文主要以蟻群算法 為基礎,求解煤礦運輸優(yōu)化方法,運算出實(shí)際生產(chǎn)中較優(yōu)生產(chǎn)模式。首先對蟻群算法做出了簡(jiǎn)單的介紹，然后比較仔細的闡述了煤礦問(wèn)題的數學(xué)模型,最后演示了蟻群算法在運輸優(yōu)化問(wèn)題中的應用。關(guān)鍵詞:蟻群算法;煤礦運輸;最短路徑;運輸優(yōu)化中圖分類(lèi)號:TP311文獻標識碼:A文章編號:1008 - 8725(2013)01 -0162 -03Coal Transportation Optimization MethodBased on Ant Colony AlgorithmGAO Pan,GUO Li( Information Science and Technology College , Shihezhi University , Shihezhi 832000 ,China)Abstract :This paper is to study the ant colony algorithm based, solving coal transport optimization meth-od, works out in practical production with excellent production mode. First this paper the ant colony algo-rithm made simply introduced, and then the more careful expounds the model of coal mine, finally dem-onstrates the ant colony algorithm of optimization problems in the application.Key Words:ant colony algorithm;Coal transport ;The shortest path; Transportation optimization徑上會(huì )留下一種稱(chēng)為信息素的揮發(fā)性分泌物,而且0前言該分泌物的濃度與路徑長(cháng)短成反比。螞蟻在選擇路蟻群算法主要是通過(guò)人工模擬螞蟻搜索食物的徑時(shí) ,對未走過(guò)的道路螞蟻會(huì )隨機的選擇-一條,在過(guò)程來(lái)求解在給定的運輸道路網(wǎng)中尋找出- -條從起行走的過(guò)程中釋放信息素,若該路徑過(guò)長(cháng)，螞蟻下次始點(diǎn)到目標點(diǎn)之間的最優(yōu)路徑的一種算法。 煤礦業(yè)就可以根據信息素 濃度判斷,繞過(guò)該條路。由于路的發(fā)展與人們的生產(chǎn)生活息息相關(guān)，而煤礦的運輸徑經(jīng)過(guò)的螞蟻越 多,路徑越短，信息素氣息就越濃問(wèn)題是煤礦產(chǎn)業(yè)中比較重要的環(huán)節，因此文中運用烈，螞蟻可以根 據氣息的濃郁程度，選擇最優(yōu)路徑。蟻群算法來(lái)求解煤礦運輸優(yōu)化問(wèn)題,在已知的約束這樣以信息素為媒介形成了一種信息反饋機制,導下,例如:交通工具的限定、荷載容量的限定以及經(jīng)致信息素越濃烈的路徑,螞蟻選擇的概率越大,這樣費的限定等,尋求達到煤礦運輸消耗最小的最優(yōu)路就形成了最短路徑。 而且由于信息素是隨著(zhù)時(shí)間的推移,會(huì )逐漸的變淡,所以當在已經(jīng)形成的最短路徑徑,提高煤礦業(yè)的運輸效率。上出現障礙物時(shí),螞蟻就不會(huì )再選擇該路徑,將會(huì )尋1蟻群算法簡(jiǎn)介找另外的路徑,原先路徑上的信息素將會(huì )逐漸消散。在尋路過(guò)程中,該作用機制必須依靠螞蟻群來(lái)完成，1.1蟻群算法的起源蟻群算法是一種隨機搜索算法,與遺傳算法、模單個(gè)螞蟻的能力是有限,但是在信息素的交流下,整擬退火算法等模擬進(jìn)化算法.-樣,主要是通過(guò)在已個(gè)蟻群可以交換路徑信息,共同完成最短路徑的選知的解組中尋求最優(yōu)解，是路徑規劃問(wèn)題的常用算擇。在蟻群算法中,多個(gè)主體之間相互合作,對信息進(jìn)行反饋,讓組合優(yōu)化問(wèn)題得到很好的解決。法之一。最早由意大利學(xué)者M(jìn) Dofipo等人提出，主13 蚊群算法流程及憂(yōu)點(diǎn)要是從螞蟻群體搜索食物的過(guò)程和旅行商問(wèn)題中得在蟻群算法中，主要的算法流程如圖1所示,首到啟發(fā),人們通過(guò)模擬螞蟻群搜索食物的過(guò)程來(lái)求先對蟻群進(jìn)行初始化,根據具體情況選擇目標函數;解最短路徑問(wèn)題，故稱(chēng)之為“人工蟻群算法”。隨著(zhù)將主體放置在初始區域,并標記出目標函數對每個(gè)時(shí)間的發(fā)展和對蟻群算法的深人研究,螞蟻算法也主體的適應度;將適應度轉換為信息素,放置在經(jīng)過(guò)被用于解決二次分配問(wèn)題Job shop 調度問(wèn)題網(wǎng)的路徑 上,其中適應度越高，信息索也越多:然后觀(guān)絡(luò )動(dòng)態(tài)路由優(yōu)化等問(wèn)題，并取得成功。察主體的行動(dòng)軌跡,根據信息素和自已的判斷選擇1.2 蟻群算法原理自然界中,螞蟻群在尋找食物時(shí)總能通過(guò)相互路徑,在這個(gè)過(guò)程中信息素會(huì )隨著(zhù)時(shí)間而消散。蟻群算法只需要對算法模型稍加修改就可以應間的合作找到食物與蟻穴間的最短路徑。蟻群算法用于多種求解問(wèn)題， 采用的分布式算法是一種種群的主要原理是模擬自然界螞蟻尋找路徑的方法。該算法,并且易與其他的方法進(jìn)行組合,組成混合算原理具體是螞蟻群尋找食物的過(guò)程中,在經(jīng)過(guò)的路法，改善算法的性能，提高計算的準確性和效率。這收稿日期:2012 -02 -15;修訂日期:2012-11-16中國煤化工基金項目:教育部社科研究基金( IJAZH001)作者簡(jiǎn)介:高攀(1981 -),男,安徽靈壁人,講師,碩士研究生,研究方向:數據結構與,MYHCNMH G .第1期高攀,等:基于蟻群算法的煤炭運輸優(yōu)化方法●163●時(shí)刻∞0城市i + 1之間之間所花費的費用,T.為兩城之間的運輸時(shí)間, Mr.為貨物在兩城之間的運輸方式參數,Y"為煤炭在城市i的m種運輸方式轉換為第1初始化4(1) |「 放置信息激種運輸方式間的轉換參數, D;"則為運輸方式轉換的螞蟻移動(dòng)”中轉費, wn為中轉時(shí)間,Q為需運煤炭的數量,T為評價(jià)40)信 息激素消散煤炭運輸過(guò)程中的時(shí)間限制,N為運輸途中所經(jīng)過(guò)的城市總數,G為運輸方式的種類(lèi),為了更加準確的反映結果的最優(yōu)性,設定U送達時(shí)間外的時(shí)間價(jià)值系數需滿(mǎn)足U > 0。則運輸過(guò)程中的時(shí)間成本為禁止集件L 1+1UEET. + EE二)。其中目標函數即為運輸成本即為時(shí)間成本及時(shí)間補償成本、[結束]中轉費用、運輸費用的和的最小值,表示為圖1蚊群算法流程圖minZ = C.M..E 2 ED"Y"+些特點(diǎn)讓蟻群算法與其他算法相比,具有更好的尋優(yōu)能力,利用的正反饋原理促進(jìn)了不同個(gè)體之間的U(Z 2+ 2二2叭)信息交流,提高了團體協(xié)作的工作效率。對運輸荷載的相關(guān)約束為需運的煤炭數量小于每次運輸方式的荷載性能,即2煤炭運輸問(wèn)題數學(xué)模型Ci.M;i+1≥Q(i= 1,2,..N-1,N;M = 1,2,2.1煤炭運輸問(wèn)題描述煤炭運輸問(wèn)題的求解是一個(gè)復 雜的組合優(yōu)化問(wèn)在題設中在任2個(gè)相鄰城市之間只能選擇1種題,需要考慮各行業(yè)、各部門(mén)的運輸條件和運輸成運輸方式,任- - 城市運輸方式只能轉換1次，則需要本。用常規的數學(xué)方法很難求解，這里主要是采用滿(mǎn)足模擬生物進(jìn)化的蟻群算法來(lái)解決。由于煤礦運輸問(wèn)SM =1(i= 1,2，N-1,N)題影響因素復雜,由目標可劃分為線(xiàn)性問(wèn)題與非線(xiàn)性問(wèn)題，單目標問(wèn)題和多目標問(wèn)題。以約束的類(lèi)型22 =1(i= .,.N-1,N)可分為二維問(wèn)題或三維問(wèn)題。這里主要是分析煤炭運輸問(wèn)題的容量的上下限和損耗費用之間的問(wèn)題。運輸時(shí)間成本小于限定時(shí)間假設煤礦從產(chǎn)地A地運到需求地B,中途經(jīng)過(guò)n個(gè)城市,任意兩個(gè)城市之間又有m種運輸方式，每種EEnm+ 2SEw≤r運輸方式的費用,承載容量和消耗時(shí)間是不同的,在運輸方式為0或是1,則整個(gè)煤炭運輸過(guò)程中,約束條件是,在不超過(guò)規定時(shí)M.= 1間的前提下,選用最優(yōu)的運輸組合方式,使得運輸成y?=1或是0本最小,將需要的煤炭量送達目的地。在該數據模型的基礎上對全局的可能解進(jìn)行試2.2數學(xué)模型的建立算,計算各種取值的目標函數,由于該類(lèi)計算的時(shí)間ASAR算法,即基于蟻群優(yōu)化的服務(wù)感知路由復雜度和迭算次數繁多的原因，-.般是采用MatLab算法,本算法系統中的螞蟻大致分為3類(lèi),每類(lèi)都是語(yǔ)言編制煤炭運輸的蟻群算法優(yōu)化計算程序進(jìn)行計和多媒體感知器網(wǎng)絡(luò )所提供的一種特定的服務(wù) 相對算,最優(yōu)路徑的輸出。應的,以對應服務(wù)QoS需求為依據,對信息素增量以及局部信息啟發(fā)因子進(jìn)行計算。3蟻群算法在運輸優(yōu)化中的應用在數學(xué)模型的建立中,前提假設為每個(gè)城市必在求解運輸優(yōu)化問(wèn)題中,要將問(wèn)題按照考慮要須經(jīng)過(guò)，任一個(gè)城市的運輸方式只能轉換1次,并且素簡(jiǎn)化為尋求最優(yōu)路徑的問(wèn)題，將起始條件與目標2個(gè)相鄰城市之間只能采用1種運輸方式，可以由中的過(guò)程轉化為路徑的組成點(diǎn)。這類(lèi)問(wèn)題屬于靜態(tài)簡(jiǎn)單的賦權網(wǎng)絡(luò )圖表示，如圖2所示,其中權數即為組合,主要是有n個(gè)節點(diǎn)，每個(gè)節點(diǎn)必須訪(fǎng)問(wèn)并且只每條路徑對目標函數的適應度。能訪(fǎng)問(wèn)1次,而且根據所給的條件放置信息要素,即.從一個(gè)城市轉移到另一個(gè)城市的概率，在文中的煤炭運輸求解問(wèn)題中，信息要素是由城市間轉化參數48、、3和運輸方式轉換參數來(lái)確定的。數學(xué)模式確定后，v1;， v20依照螞蟻尋找食物的過(guò)程,假定速度恒定的螞蟻群，3| 6/入3同時(shí)從起點(diǎn)出發(fā),模型中的每個(gè)節點(diǎn)都遍歷,當第1只螞蟻到達終點(diǎn)時(shí),則求解結束,該螞蟻的路徑即為一v最優(yōu)路徑。主要是利用了蟻群算法的以下特點(diǎn):(1)蟻群算法的并行性。在蟻群中,每只螞蟻都同時(shí)行動(dòng),在速中國煤化工付刻,螞蟻圖2賦權網(wǎng)絡(luò )圖所行走的路徑量CN M H C率的前提其中C...是選定第m種運輸方式,從城市i與下 ,即螞蟻選擇要足的路時(shí)院干定陽(yáng)凹的,由于特第32卷第1期煤炭技術(shù)Vol. 32 ,No.01.2013年1 期Coal TechnologyJanuary ,2013基于CAN總線(xiàn)的煤礦遠程監控謝青海,黃亮(河北機電職業(yè)技術(shù)學(xué)院，河北邢臺054048)摘.要:針對當前我國國內的煤礦監控系統中存在的不足,設計了-種基于CAN總線(xiàn)的煤礦遠程監控系統,并且，就該系統的具體設計方案、智能節點(diǎn)以及通訊接口做了較為詳細的闡述,通過(guò)實(shí)踐證明,本文構建的基于CAN總線(xiàn)的煤礦遠程監控能夠較好的監測煤礦生產(chǎn)的運行狀態(tài)。關(guān)鍵詞:CAN總線(xiàn);煤礦;遠程監控中圖分類(lèi)號:TP274文獻標識碼:A文章編號:1008 - 8725(2013)01 -0164 -03Based on CAN Bus Coal Mine Remote MonitoringXIE Qing - hai , HUANG Liang( Hebei Institute of Machinery Eletricity , Xingtai 054048 , China)Abstract:The article in view of the current domestic coal mine of the monitor system of deficiency, design a kind of based on CAN bus coal mine remote monitoring system, and the system is the specific de-sign scheme, intelligence and communication interface node, a detailed elaboration , through the practiceof proof, this paper constructed based on CAN bus remote monitoring to better coal mine monitoring inthe process of coal mine production operation.Key Words :CAN bus ;coal mine ;remote monitoring性無(wú)法得到保證等各方面的問(wèn)題。針對當前煤礦遠0引言程監控系統之中存在的上述問(wèn)題,文中提出了一種當前,為了提升我國煤礦的安全生產(chǎn)管理能力,基于CAN總線(xiàn)的煤礦遠程監控系統的構建方法,能我國的許多煤礦都構建了自身的監控系統，但是在夠較為 直觀(guān)的監控并且記錄進(jìn)行的工作實(shí)際情況，傳輸的過(guò)程中，由于大部分都是選擇的串行通信總同時(shí)也能夠實(shí)現瓦斯等環(huán)境安全數據的共享,充分線(xiàn),造成了多主冗余系統無(wú)法構建，通訊方式無(wú)法選的滿(mǎn)足煤礦 安全生產(chǎn)管理的實(shí)際需求”。擇,以及缺乏統一的規范與通信協(xié)議,可靠性與實(shí)時(shí)殊的正反饋機制,不可走的路徑和已走過(guò)的路徑不尋優(yōu)性較強且具有發(fā)展前景的仿生優(yōu)化算法,被廣重復選,防止尋徑問(wèn)題無(wú)解。泛的運用于組合優(yōu)化求解問(wèn)題中。但是由于其算法(2)速度--定原理。蟻群算法采用:速度一定本身的局限性,算法的時(shí)間復雜度高，迭換次數繁時(shí),路程與時(shí)間成正比的基本定理。在規定螞蟻的多,比較不容易得到全局解,容易陷入局部最優(yōu)解速度時(shí)，引進(jìn)離散單位時(shí)間量即是算法中進(jìn)行-一次中， 即尋找的最優(yōu)解不是全局的最優(yōu)解。所以在組迭代所代表的時(shí)間。在此理論的支撐下，可以得到合優(yōu)化問(wèn)題的研究中 ,蟻群算法可以與其他的算法第-一個(gè)到達目的地的螞蟻所走的是最優(yōu)路徑?；旌?例如遺傳算法等,產(chǎn)生越來(lái)越多的新型算法，(3)對螞蟻狀態(tài)的判斷,所有的螞蟻都是從起在花 費較少時(shí)間的基礎上,尋求最優(yōu)的路徑,以實(shí)現點(diǎn)開(kāi)始,經(jīng)過(guò)一定的時(shí)間后,螞蟻的狀態(tài)是確定的，資 源配置的最優(yōu)化。沒(méi)有達到路徑節點(diǎn)的螞蟻繼續在該路徑上前進(jìn)，而參考 文獻:達到路徑節點(diǎn)的螞蟻則是開(kāi)始以- -定的概率對下一[1周勇.“遺傳- -蟻群” 混合算法及其在水量調度中的應用[ D].華公個(gè)達到節點(diǎn)的路徑進(jìn)行選擇。(4)信息相關(guān)性。在蟻群算法中,螞蟻對路徑[2] 杜艷平,尹曉峰 ,劉春煌.采用蟻群算法求解鐵路空車(chē)調整間題[J1.中國鐵道科學(xué)2061)19-122的信息是共享的，只要保證至少有- .只螞蟻選擇了[3] 王豐元，。潘福全，張麗霞等定,等.基于交通限制的路網(wǎng)最優(yōu)路徑算最短路行進(jìn)就能得到最短的路徑的全局解。所以在法[J]. 交通運輸工程學(xué)報,2005(1):92 -95.運輸問(wèn)題求解過(guò)程中,要保證足夠多的運算，以求到[4] 王旭，張江，崔平遠。 一種基于蟻群算法求解路徑規劃問(wèn)題的新方法[A]. 2003年中國智能自動(dòng)化會(huì )議論文集(下冊)[C].全局解。(5)影響因素較為單一,蟻群算法的時(shí)間復雜(責任編輯張欣)度只跟螞蟻群的數量和最短路徑的長(cháng)度有關(guān)。4結語(yǔ)在求解煤炭運輸優(yōu)化問(wèn)題中，蟻群算法是一種中國煤化工收稿日期:2012 -02 - 15;修訂日期:2012-11-06MHCNMH G .作者簡(jiǎn)介:謝青海( 1980 -),男,河北邢臺人,講師,本科學(xué)歷,研究方向:遠程監控。