基于蟻群算法和Petri網的井下有軌運輸調度優化

朱啟航　周　杰　張文舉

(武漢理工大學資源與環境學院)

?

基于蟻群算法和Petri網的井下有軌運輸調度優化

朱啟航周杰張文舉

(武漢理工大學資源與環境學院)

為解決地下礦山有軌運輸調度問題，將Petri網理論引入礦山井下有軌運輸調度優化中，結合蟻群算法思想，建立基于蟻群算法的賦時Petri網模型，并將蟻群系統算法機制改進后用于Petri網模型的分析，在模型中加入了根據地下礦山有軌運輸系統改進過的時間戳狀態類，使模型能夠更好地處理運行過程中信息素、啟發式因子等，優化參數與時間、狀態之間的關系，建立了優化計算的詳細步驟，簡化了計算。并用計算實例驗證了優化方法的有效性。

調度優化井下運輸賦時Petri網蟻群優化

在地下礦山中，礦石運輸是采礦工程中非常重要的一環。目前，有軌運輸仍然是主要運輸方式。有軌運輸調度的合理與否，不僅關系到礦山的經濟效益，還涉及到礦山的安全問題。不合理的運輸調度不僅浪費礦山資源，還很可能發生相撞等安全事故。然而，傳統礦山較少關注井下運輸調度優化，特別是有軌運輸的調度優化，相關研究也不多。

根據礦山地下有軌運輸的特點，采用基于蟻群優化的賦時Petri網對運輸調度系統建模，用改進的蟻群算法進行優化。引入時間戳狀態類思想[1]，將蟻群算法中的螞蟻信息素引入到Petri網的變遷中，設置信息素與變遷輸出庫所的時延相關聯，將蟻群算法的尋優規則融合進Petri網的進化規則中。運算時設置螞蟻令牌，根據進化規則運行多次，便可逐步找到最優路徑，即可確定最優調度方案。

1　基于蟻群算法優化的時間Petri網模型

在Petri網中，將系統抽象為活動(事件)、狀態及其之間的關系，組成三元結構。一般用庫所P(Place)表示狀態，用遷移T(Transition)表示活動[2]。庫所能夠決定遷移是否發生，而遷移可以改變庫所狀態，他們之間的相互依賴關系用輸入函數和輸出函數來表示。

結合蟻群算法，根據礦山地下有軌運輸特點，建立賦時Petri模型：

(1)

(2)

式中，P={p1， p2，…，pn}為有限位置的集合，n為庫所數量，n>0；T={t1，t2，…，tm}為有限遷移的集合，m為變遷數量，m>0(P與T需滿足以下關系：P∩T=φ，P∪T≠φ，保證位置與變遷是兩種不同類型的元素，同時網中至少有一個元素)；I：P×T→N是輸入函數，定義從庫所P到變遷T有向弧的權的集合，這里N={0，1，…}為非負整數集；O：T×P→N是輸出函數，定義從變遷T到庫所P有向弧的權的集合；M為Petri網的令牌(token)，為一列向量，其中第i個元素表示第i個庫所中的令牌數目，采用賦時庫所Petri網；D={d1，d2，…,dn}為所有操作庫所的時延集，其中di表示庫所Pi的時延大小;S為時間戳狀態類[3]；K為前n項中所有操作庫所中令牌數不為零的庫所號，即電機車所在位置，在本調度系統中n為電機車數量，K為n項的數列，K={Pi，Pj，…,Pn};N為采場所需礦車數量資源庫所中的令牌數量，為每個采場需要的礦車數量；SI為時間戳狀態類的時間戳，為全局時間區間，正表示網從最初狀態S0運行到Si的全局時間，只有當變遷發生時，時間戳狀態類才會發生改變，每次變遷發生后，如果狀態類在狀態類庫中不存在，則將當前狀態類放入狀態類庫，狀態類庫中儲存著所有出現過的狀態類；τ為變遷的信息素映射函數，τ(t)為變遷上的信息素數量，初始時，計算所有庫所延時之和，取其倒數，并平均分配到每一個變遷上，作為每個變遷初始時的信息素值τ0(ti)[4]。

初始時所有變遷上的信息素值相同，計算式如下：

(3)

由于調度系統與系統狀態相關，同一個變遷可能在不同的狀態下發生，變遷每次發生的重要性不同，變遷中的信息素值也應該不同，將信息素值與系統狀態相關聯，建立與狀態類相關的信息素矩陣τij(i為變遷編號，j為狀態類編號)，τij中包含了所有狀態所有變遷的信息素的值。為簡化計算程序，用同一個狀態信息τi0表示每個變遷所有未出現過的狀態信息素值。

η為變遷的啟發式因子映射函數，η(t)為變遷上的啟發式因子，計算時將變遷之后庫所的延時時間的倒數作為變遷初始的啟發式因子，由于部分庫所的延時為零，為了避免分母部分為零，在分母部分加1[5]，計算式如下：

(4)

式中,di為變遷之后操作庫所中的延時時間。

與信息素相同，啟發式因子也與狀態類相關，同樣建立啟發式因子值矩陣ηij。

2　進化規則

2.1變遷發生的條件

變遷發生必須同時滿足兩個條件：變遷必須是使能的，輸入庫所中的令牌必須是有效的。

I(tj)表示輸入函數中到變遷ti的所有權值，如果I(t)≤M，那么變遷ti是使能的。判斷變遷能否發生還需判斷輸入操作庫所中的令牌是否有效。變遷發生時的狀態類時間戳為SI(i)，判斷SI(i)與令牌變為有效的時間集D中D(j)的大小，如果SI(i)≥D(j)，那么狀態類K中第j個庫所中令牌為有效的。由于狀態集K中記有當前電機車所在位置信息，即庫所編號，所有可能使能的變遷必定以有電機車在的庫所為輸入庫所，所以判斷時，只需判斷有機車在的庫所為輸入庫所的變遷是否使能，即只需判斷當前狀態類中K中庫所對應的變遷即可，大大減少了優化時的計算量。記狀態為k時所有可以發生的變遷記為Fr(k)。

2.2激發變遷的選擇

將當前發生的變遷視作蟻群算法中螞蟻當前所在的城市，下一個激發的變遷即為螞蟻將要前往的城市，變遷是否發生，參照蟻群算法中選擇下一個城市的方法確定。引入在區間[0，1]均勻分布的隨機變量q，q0是一個偽隨機比例參數(0≤q0≤1)。通過比較q與q0的大小，確定選擇變遷的方式。

當q≤q0時，按照先驗知識選擇路徑，用以下公式選擇激發的變遷：

(5)

式中，τk(t)為變遷t在狀態k時的信息素值；ηk(t)為變遷t在狀態k時的啟發式信息值。在可以發生的變遷中選擇括號中值最大的變遷tj激發。

當q≥q0時，使用賭輪法選擇激發的變遷，變遷tj激發的概率為：

(6)

以上兩個公式中，為調整路徑長度與信息素之間的相對重要程度參數，這種選擇規則稱為偽隨機比例規則，傾向于選擇路徑較短且信息素濃度較大的路徑前行。利用先驗知識與探索新的路徑之間的相對重要程度由參數q0的大小來決定。q0較大時，傾向于使用先驗知識選擇，選擇已經走過的路徑中最好的，這樣能更快收斂，但容易陷入局部最優解中；q0較小時，進行概率式搜索，更容易探索新的路徑。

2.3變遷的激發

在確定要激發的變遷之后，對變遷實施激發操作，變遷的激發將導致狀態類的改變。變遷發生時，首先進行庫所令牌的更新，減去對應輸入資源庫所中的令牌，同時在輸出庫所中放入令牌：?p∈·t：m′(p)= m(p)-I(p，t)；?p∈t·：m′(p)=m(p)+O(t，p)。接著更新時間戳狀態類，當激發狀態類中第i個庫所對應的變遷時，將時間戳狀態類中的K(i)中的庫所號由激發變遷的輸入庫所改為輸出庫所，并記錄當前時間戳加上輸出庫所時延值的大小到D(i)中。

2.4信息素更新

在變遷發生之后，馬上對此刻該變遷的信息素進行更新，稱為局部更新。通過局部更新，增加有螞蟻經過的變遷的信息素值。如果在狀態k時，變遷ti激發，那么該狀態下局部信息素利用以下公式進行更新：

(7)

當一次迭代中所有螞蟻都完成了運行，在所有路徑中選取從初始標識到最終標識的最優路徑，對于最優路徑上的所有變遷應用下式對信息素進行更新：

(8)

式中，ρ為從0到1的參數，代表信息素揮發的速度;Lop為到目前為止找到的最優路徑運行的總時間。

其他狀態下按照不在全局最優路徑上的公式進行更新。通過全局更新，最優路徑上的變遷信息素增多，在后面的迭代中，最優路徑被選擇的幾率變大。而其他路徑的信息素揮發則將變淡。

3　優化計算步驟

(1)初始化參數。設置循環次數，初始標識下每個庫所中的令牌數量為m，變遷輸入函數I(P，T)，變遷輸出函數O(P，T)，操作庫所的時延值大小D，每個變遷上的初始信息素值τk(t)和啟發式因子ηk(t)，建立數列N用于記錄變遷發生時的狀態類編號。建立狀態類庫，狀態類庫中開始時只儲存初始狀態類。

(2)設置初始時間戳為當前狀態類。

(3)尋找使能的變遷。根據變遷發生的條件，找出所有使能變遷，若沒有轉至第(7)步。

(4)按照變遷的選擇規則選擇出激發的變遷。

(5)激發變遷。按照變遷的激發規則激發變遷，如果當前狀態類不在狀態類庫中，將當前狀態類放入狀態類庫，之后轉至第(3)步。

(6)判斷是否達到目標標識，達到目標標識轉第(8)步，否則運行第(7)步。

(7)增加全局時間(本例中為10s)，即增加當前狀態類時間戳。之后判斷時間戳是否到達最大時間，沒有到達轉至第(3)步，達到轉至第(8)步。

(8)記當前狀態類時間戳為此次循環運行時間，第一次循環時，直接將此次循環時間記為最優時間，此次循環中變遷激發的狀態類編號記為最優順序。后面的循環與此前的最優時間相比，若此次循環時間小于最優時間，記此次循環時間為最優時間，并將此次循環變遷激發的狀態類編號記為最優順序；若此次循環時間大于當前最優時間，最優時間與最優順序不變。

(9)全局信息素更新。

(10)如果當前循環次數小于規定的循環次數，循環次數加1，轉至第(2)步；如果當前循環次數達到規定的循環次數，輸出當前最優時間，最優狀態類順序。

通過以上過程的多次循環，便可找出最優或者較優的運行路徑，輸出作為優化結果。

4　計算實例

圖1為一巷道運輸簡圖[6]。應用蟻群優化的賦時庫所Petri網對這一運輸系統進行建模，并且進行優化，再用其他優化方法對比，以驗證效果。

圖1　巷道運輸簡圖

圖1中CH為井底車場，CH1，CH2，CH3分別為1#、2#、3#采場車場，電機車在井底車場與采場車場之間運行，將采場的礦石運至井底車場。記前往1#采場運輸的電機車為電機車(Ⅰ)，前往2#采場的電機車為電機車(Ⅱ)，前往3#采場的電機車為電機車(Ⅲ)。采場車場只能同時容納一列電機車。前往3#采場處的電機車行駛路徑為2、4、8、11，到達3#采場裝載礦石后由12、9、4、1路徑返回井底車場，卸載礦石后，礦車變為空閑狀態，等待下一次運輸命令。1#采場的運輸路線為由2、5、6到達，7、5、1返回；到達2#采場有兩條路徑，從井底車場到采場可以走2、4、8、13或者2、5、6、14，1，裝載礦石后可以由13、9、4、1或者14、7、5、1返回。

用變遷表示電機車每次狀態的改變，包括出發、卸載以及進出某段進路等，用資源庫所表示電機車對資源的占用情況，操作庫所表示電機車的狀態，建立如圖2所示Petri網模型。

用計算機進行編程計算，按前文所述方法對此模型進行優化。計算時，每組參數進行10次運算。循環次數為100次，信息素更新規則參數ξ、ρ取0.1，偽隨機比例參數q0取0.4，β取8時，運算效果較好，10次計算中有9次獲得了相同的最優解5 270s，說明此方法是有效的。

5　結　語

結合Petri網理論，建立了基于蟻群算法和Petri網的礦山地下有軌運輸調度優化模型。為了使模型能更好地適應于礦山地下有軌運輸與時間和狀態密切相關的特性，引入了時間戳狀態類的方法，將蟻群算法中的信息素和啟發式因子與時間戳狀態類相關聯。并且在其基礎上建立了詳細運行規則，包括變遷發生的條件、激發規則、信息素更新等。

圖2　Petri網模型

參照蟻群算法的步驟，設計了優化計算的具體步驟，包括單次運行流程以及循環方法。通過多次循環計算，得出所需的優化結果，最后利用計算機編程進行具體實例的優化計算。結果表明，此算法快速有效，可以得出優化結果。

[1]潘理，李文軍，劉顯明.擴展時間戳狀態類[J].系統仿真學報,2005,17(S1):73-77,81.

[2]袁崇義.petri網的原理與應用[M].北京：電子工業出版社,2005.

[3]WangJ,DengY,XuG.Reachabilityanalysisofreal-timesystemsusingtimePetrinets[J].IEEETransSystManCybernBCybern, 2000,30(5):725-736.

[4]李士勇.蟻群算法及其應用[M].哈爾濱:哈爾濱工業大學出版社,2004.

[5]潘理，鄭紅，郭觀七，等.基于蟻群優化的時間Petri網及其在柔性制造系統調度優化中的應用[J].電子學報,2014,42(8):1531-1537.

[6]方歡，陸陽，徐自軍，等.井下機車運輸調度的資源分配模型及無死鎖優化調度[J].系統工程理論與實踐,2013(8):2087-2096.

OptimizationoftheUndergroundLocomotiveTransportationDispatchBasedonAntColonyAlgorithmandPetriNet

ZhuQihangZhouJieZhangWenju

(SchoolofResourcesandEnvironmentalEngineering,WuhanUniversityofTechnology)

Inordertosolvetheproblemofundergroundlocomotivetransportationdispatch,thePrtrinettheoryisintroducedtotheoptimizationofundergroundlocomotivetransportationdispatch,combingwiththebasicprincipleofantcolonyalgorithm,thetimedPetrinetmodelbasedonantcolonyalgorithmisestablished.Theantcolonyalgorithmmechanismisimproved,anditisusedtoanalyzethePetrinetmodel.Theclock-stampedstateclassimprovedbyundergroundlocomotivetransportationsystemisaddedtothePetrinetmodeltodealwiththerelationshipbetweentheoptimizationparametersofpheromoneandheuristicfactortotimeandstate,besidesthat,theoptimizationcalculationstepsareanalyzedandthecalculationprocessissimplified,theeffectivenessoftheaboveoptimizationmethodisverified.

Dispatchoptimization,Undergroundtransportation,TimedPetrinet,Antcolonyoptimization

2016-03-16)

朱啟航(1991—)，男，碩士研究生，430070 湖北省武漢市。