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

朱啟航　周　杰　張文舉

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

?

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

朱啟航周杰張文舉

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

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

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

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

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

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

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

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

(1)

(2)

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

初始時(shí)所有變遷上的信息素值相同，計(jì)算式如下：

(3)

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

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

(4)

式中,di為變遷之后操作庫(kù)所中的延時(shí)時(shí)間。

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

2　進(jìn)化規(guī)則

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

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

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

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

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

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

(5)

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

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

(6)

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

2.3變遷的激發(fā)

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

2.4信息素更新

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

(7)

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

(8)

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

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

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

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

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

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

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

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

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

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

(8)記當(dāng)前狀態(tài)類時(shí)間戳為此次循環(huán)運(yùn)行時(shí)間，第一次循環(huán)時(shí)，直接將此次循環(huán)時(shí)間記為最優(yōu)時(shí)間，此次循環(huán)中變遷激發(fā)的狀態(tài)類編號(hào)記為最優(yōu)順序。后面的循環(huán)與此前的最優(yōu)時(shí)間相比，若此次循環(huán)時(shí)間小于最優(yōu)時(shí)間，記此次循環(huán)時(shí)間為最優(yōu)時(shí)間，并將此次循環(huán)變遷激發(fā)的狀態(tài)類編號(hào)記為最優(yōu)順序；若此次循環(huán)時(shí)間大于當(dāng)前最優(yōu)時(shí)間，最優(yōu)時(shí)間與最優(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ù)達(dá)到規(guī)定的循環(huán)次數(shù)，輸出當(dāng)前最優(yōu)時(shí)間，最優(yōu)狀態(tài)類順序。

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

4　計(jì)算實(shí)例

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

圖1　巷道運(yùn)輸簡(jiǎn)圖

圖1中CH為井底車場(chǎng)，CH1，CH2，CH3分別為1#、2#、3#采場(chǎng)車場(chǎng)，電機(jī)車在井底車場(chǎng)與采場(chǎng)車場(chǎng)之間運(yùn)行，將采場(chǎng)的礦石運(yùn)至井底車場(chǎng)。記前往1#采場(chǎng)運(yùn)輸?shù)碾姍C(jī)車為電機(jī)車(Ⅰ)，前往2#采場(chǎng)的電機(jī)車為電機(jī)車(Ⅱ)，前往3#采場(chǎng)的電機(jī)車為電機(jī)車(Ⅲ)。采場(chǎng)車場(chǎng)只能同時(shí)容納一列電機(jī)車。前往3#采場(chǎng)處的電機(jī)車行駛路徑為2、4、8、11，到達(dá)3#采場(chǎng)裝載礦石后由12、9、4、1路徑返回井底車場(chǎng)，卸載礦石后，礦車變?yōu)榭臻e狀態(tài)，等待下一次運(yùn)輸命令。1#采場(chǎng)的運(yùn)輸路線為由2、5、6到達(dá)，7、5、1返回；到達(dá)2#采場(chǎng)有兩條路徑，從井底車場(chǎng)到采場(chǎng)可以走2、4、8、13或者2、5、6、14，1，裝載礦石后可以由13、9、4、1或者14、7、5、1返回。

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

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

5　結(jié)　語(yǔ)

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

圖2　Petri網(wǎng)模型

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

[1]潘理，李文軍，劉顯明.擴(kuò)展時(shí)間戳狀態(tài)類[J].系統(tǒng)仿真學(xué)報(bào),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)化的時(shí)間Petri網(wǎng)及其在柔性制造系統(tǒng)調(diào)度優(yōu)化中的應(yīng)用[J].電子學(xué)報(bào),2014,42(8):1531-1537.

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