朱啟航　周　杰　張文舉

(武漢理工大學(xué)資源與環(huán)境學(xué)院)

?

基于蟻群算法和Petri網(wǎng)的井下有軌運輸調(diào)度優(yōu)化

朱啟航周杰張文舉

(武漢理工大學(xué)資源與環(huán)境學(xué)院)

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

調(diào)度優(yōu)化井下運輸賦時Petri網(wǎng)蟻群優(yōu)化

在地下礦山中，礦石運輸是采礦工程中非常重要的一環(huán)。目前，有軌運輸仍然是主要運輸方式。有軌運輸調(diào)度的合理與否，不僅關(guān)系到礦山的經(jīng)濟效益，還涉及到礦山的安全問題。不合理的運輸調(diào)度不僅浪費礦山資源，還很可能發(fā)生相撞等安全事故。然而，傳統(tǒng)礦山較少關(guān)注井下運輸調(diào)度優(yōu)化，特別是有軌運輸?shù)恼{(diào)度優(yōu)化，相關(guān)研究也不多。

根據(jù)礦山地下有軌運輸?shù)奶攸c，采用基于蟻群優(yōu)化的賦時Petri網(wǎng)對運輸調(diào)度系統(tǒng)建模，用改進的蟻群算法進行優(yōu)化。引入時間戳狀態(tài)類思想[1]，將蟻群算法中的螞蟻信息素引入到Petri網(wǎng)的變遷中，設(shè)置信息素與變遷輸出庫所的時延相關(guān)聯(lián)，將蟻群算法的尋優(yōu)規(guī)則融合進Petri網(wǎng)的進化規(guī)則中。運算時設(shè)置螞蟻令牌，根據(jù)進化規(guī)則運行多次，便可逐步找到最優(yōu)路徑，即可確定最優(yōu)調(diào)度方案。

1　基于蟻群算法優(yōu)化的時間Petri網(wǎng)模型

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

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

(1)

(2)

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

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

(3)

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

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

(4)

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

與信息素相同，啟發(fā)式因子也與狀態(tài)類相關(guān)，同樣建立啟發(fā)式因子值矩陣ηij。

2　進化規(guī)則

2.1變遷發(fā)生的條件

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

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

2.2激發(fā)變遷的選擇

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

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

(5)

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

當(dāng)q≥q0時，使用賭輪法選擇激發(fā)的變遷，變遷tj激發(fā)的概率為：

(6)

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

2.3變遷的激發(fā)

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

2.4信息素更新

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

(7)

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

(8)

式中，ρ為從0到1的參數(shù)，代表信息素?fù)]發(fā)的速度;Lop為到目前為止找到的最優(yōu)路徑運行的總時間。

其他狀態(tài)下按照不在全局最優(yōu)路徑上的公式進行更新。通過全局更新，最優(yōu)路徑上的變遷信息素增多，在后面的迭代中，最優(yōu)路徑被選擇的幾率變大。而其他路徑的信息素?fù)]發(fā)則將變淡。

3　優(yōu)化計算步驟

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

(2)設(shè)置初始時間戳為當(dāng)前狀態(tài)類。

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

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

(5)激發(fā)變遷。按照變遷的激發(fā)規(guī)則激發(fā)變遷，如果當(dāng)前狀態(tài)類不在狀態(tài)類庫中，將當(dāng)前狀態(tài)類放入狀態(tài)類庫，之后轉(zhuǎn)至第(3)步。

(6)判斷是否達到目標(biāo)標(biāo)識，達到目標(biāo)標(biāo)識轉(zhuǎn)第(8)步，否則運行第(7)步。

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

(8)記當(dāng)前狀態(tài)類時間戳為此次循環(huán)運行時間，第一次循環(huán)時，直接將此次循環(huán)時間記為最優(yōu)時間，此次循環(huán)中變遷激發(fā)的狀態(tài)類編號記為最優(yōu)順序。后面的循環(huán)與此前的最優(yōu)時間相比，若此次循環(huán)時間小于最優(yōu)時間，記此次循環(huán)時間為最優(yōu)時間，并將此次循環(huán)變遷激發(fā)的狀態(tài)類編號記為最優(yōu)順序；若此次循環(huán)時間大于當(dāng)前最優(yōu)時間，最優(yōu)時間與最優(yōu)順序不變。

(9)全局信息素更新。

(10)如果當(dāng)前循環(huán)次數(shù)小于規(guī)定的循環(huán)次數(shù)，循環(huán)次數(shù)加1，轉(zhuǎn)至第(2)步；如果當(dāng)前循環(huán)次數(shù)達到規(guī)定的循環(huán)次數(shù)，輸出當(dāng)前最優(yōu)時間，最優(yōu)狀態(tài)類順序。

通過以上過程的多次循環(huán)，便可找出最優(yōu)或者較優(yōu)的運行路徑，輸出作為優(yōu)化結(jié)果。

4　計算實例

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

圖1　巷道運輸簡圖

圖1中CH為井底車場，CH1，CH2，CH3分別為1#、2#、3#采場車場，電機車在井底車場與采場車場之間運行，將采場的礦石運至井底車場。記前往1#采場運輸?shù)碾姍C車為電機車(Ⅰ)，前往2#采場的電機車為電機車(Ⅱ)，前往3#采場的電機車為電機車(Ⅲ)。采場車場只能同時容納一列電機車。前往3#采場處的電機車行駛路徑為2、4、8、11，到達3#采場裝載礦石后由12、9、4、1路徑返回井底車場，卸載礦石后，礦車變?yōu)榭臻e狀態(tài)，等待下一次運輸命令。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返回。

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

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

5　結(jié)　語

結(jié)合Petri網(wǎng)理論，建立了基于蟻群算法和Petri網(wǎng)的礦山地下有軌運輸調(diào)度優(yōu)化模型。為了使模型能更好地適應(yīng)于礦山地下有軌運輸與時間和狀態(tài)密切相關(guān)的特性，引入了時間戳狀態(tài)類的方法，將蟻群算法中的信息素和啟發(fā)式因子與時間戳狀態(tài)類相關(guān)聯(lián)。并且在其基礎(chǔ)上建立了詳細(xì)運行規(guī)則，包括變遷發(fā)生的條件、激發(fā)規(guī)則、信息素更新等。

圖2　Petri網(wǎng)模型

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

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

[2]袁崇義.petri網(wǎng)的原理與應(yīng)用[M].北京：電子工業(yè)出版社,2005.

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

[4]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004.

[5]潘理，鄭紅，郭觀七，等.基于蟻群優(yōu)化的時間Petri網(wǎng)及其在柔性制造系統(tǒng)調(diào)度優(yōu)化中的應(yīng)用[J].電子學(xué)報,2014,42(8):1531-1537.

[6]方歡，陸陽，徐自軍，等.井下機車運輸調(diào)度的資源分配模型及無死鎖優(yōu)化調(diào)度[J].系統(tǒng)工程理論與實踐,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 湖北省武漢市。