基于改進(jìn)差分進(jìn)化算法的煤礦井下逃生路徑優(yōu)化

趙海軍

(陽泉市南莊煤炭集團(tuán)有限責(zé)任公司,山西 陽泉 045001)

基于改進(jìn)差分進(jìn)化算法的煤礦井下逃生路徑優(yōu)化

趙海軍

(陽泉市南莊煤炭集團(tuán)有限責(zé)任公司,山西 陽泉 045001)

為了減少礦難中的損失,提高被困人員的幸存概率,基于改進(jìn)差分進(jìn)化算法,提出一種煤礦井下逃生路徑優(yōu)化方法。分析了影響逃生的六個(gè)影響因素,并根據(jù)這些因素建立了地下巷道權(quán)值計(jì)算模型。通過設(shè)計(jì)混合變異策略和參數(shù)自適應(yīng)機(jī)制來提高差分進(jìn)化算法的搜索效率,從而快速尋找最優(yōu)逃生路徑。實(shí)驗(yàn)結(jié)果表明,所提方法能夠有效的找到最優(yōu)逃生路徑及其他次優(yōu)可選路徑。

優(yōu)化; 逃生;巷道;差分進(jìn)化

在采礦中,水、火、瓦斯以及其他自然災(zāi)害經(jīng)常發(fā)生,災(zāi)害對礦山的安全生產(chǎn)有著重大影響。統(tǒng)計(jì)顯示,我國煤礦行業(yè)傷亡事故最為嚴(yán)重。從2001年到2010年就有86 000多人死于煤礦事故,占采礦事故死亡人數(shù)的85%。根據(jù)2006年到2008年的統(tǒng)計(jì)數(shù)據(jù)顯示,在我國高危行業(yè)中,煤礦事故率和死亡率分別占21.3%和28.5%,位列工礦業(yè)首位[1]。

當(dāng)?shù)V難發(fā)生后,如何確定一條最佳的避災(zāi)救援路線,指導(dǎo)受災(zāi)人員安全撤離,以及安排救援人員及時(shí)展開有效的救援,最大程度的降低事故影響至關(guān)重要。為了確定最佳逃生路徑,國內(nèi)外學(xué)者提出了很多算法。例如,文獻(xiàn)[2-4]使用的改進(jìn)Dijskstra算法,根據(jù)礦井巷道平面網(wǎng)絡(luò)的運(yùn)行效率,通過限制搜索方向和范圍在扇形區(qū)域內(nèi)尋找最優(yōu)路徑,并根據(jù)用戶給出的源點(diǎn)和目的點(diǎn),以及搜索的扇形角度尋找最優(yōu)路徑,從而提高效率。然而,Dijskstra算法具有三點(diǎn)不足之處:1)由于Dijskstra算法需要遍歷網(wǎng)絡(luò)中的所有節(jié)點(diǎn),所以需要很大的計(jì)算代價(jià);2)Dijskstra算法只能尋找到最優(yōu)路徑,但在很多情況下,需要得到多條符合要求的次優(yōu)路徑;3)Dijskstra算法為靜態(tài)算法,當(dāng)有狀態(tài)變化時(shí),算法需要重新計(jì)算[2-4]。

差分進(jìn)化算法(DE)[5]作為一種隨機(jī)性算法,是進(jìn)化算法中最簡單而高效的算法。DE算法通過模仿生物群體內(nèi)個(gè)體間的合作產(chǎn)生的群體智能實(shí)現(xiàn)對優(yōu)化問題的求解,具有能夠記憶個(gè)體最優(yōu)解,種群內(nèi)信息共享及易于其他算法結(jié)合的特點(diǎn)[6],在電力系統(tǒng)、化學(xué)工程、公交調(diào)度及生物信息學(xué)等領(lǐng)域得到了廣泛應(yīng)用[7],尤其對大規(guī)模網(wǎng)絡(luò)最優(yōu)路徑優(yōu)化問題極其有效。

本文分析人員逃生過程中巷道環(huán)境和安全性兩個(gè)方面的因素,并分析各個(gè)因素的影響權(quán)值,建立權(quán)值數(shù)學(xué)模型,并根據(jù)人員所在事故源點(diǎn)與設(shè)置的安全目標(biāo)點(diǎn),求取兩點(diǎn)間的所有連通路徑; 其次,對傳統(tǒng)差分進(jìn)化算法的變異策略和參數(shù)選擇機(jī)制進(jìn)行了改進(jìn),引入混合變異策略和參數(shù)自適應(yīng)機(jī)制,從而提高算法的搜索效率。最后利用所提出的改進(jìn)差分進(jìn)化算法決策出最優(yōu)逃生路徑和其他次優(yōu)可選路徑。

1 巷道權(quán)值計(jì)算模型

1.1 巷道當(dāng)量長度計(jì)算

影響人員通過巷道的因素通常有六類: 巷道類型、風(fēng)速、巷道坡度、顆粒濃度、擁擠度和其他與礦難相關(guān)的特殊因素。這些因素都影響著人員的逃生速度,他們可以加快或減緩逃生速度v。上述因素均可轉(zhuǎn)化為巷道當(dāng)量長度,且逃生速度v越小則當(dāng)量長度越長,這些當(dāng)量長度即為整個(gè)巷道網(wǎng)絡(luò)圖G的權(quán)值:

li=(kti·kwi·kgi·kvi·kmi·kdi)lri

(1)

式中:lri表示第i條巷道的實(shí)際長度,li表示第i條巷道的當(dāng)量長度;kti、kwi、kgi、kvi、kmi和kdi分別表示第i條巷道的巷道類型影響系數(shù)、風(fēng)速影響系數(shù)、巷道坡度影響系數(shù)、巷道顆粒濃度影響系數(shù)、巷道擁擠度影響系數(shù)和其他特殊情況的影響系數(shù)。

在巷道類型系數(shù)的影響下,人員的逃生速度v等于v0/kti,其中v0為人員正常步行速度。由于各權(quán)值系數(shù)各自獨(dú)立,因此在他們的共同影響下,逃生速度v為li/v。

1)巷道類型影響系數(shù)

地下巷道通常分為工作面、運(yùn)輸膠帶巷、聯(lián)絡(luò)巷、鐵路巷、漏風(fēng)分支和通風(fēng)井,其中,漏風(fēng)分支和通風(fēng)井無法通過。這些都影響著人員的逃生速度,例如,在鐵路巷中,逃生速度則與交通速度有關(guān)。巷道類型的影響系數(shù):

(2)

式中：vvehicle為交通工具的速度,m/s。

2) 風(fēng)速影響系數(shù)

采礦網(wǎng)絡(luò)本身就是一個(gè)完整的通風(fēng)系統(tǒng),一般總回流車道的風(fēng)速很大,風(fēng)速可能影響人員的逃生速度。風(fēng)速的影響程度通常與道路的實(shí)際長度成正比。假設(shè)人員的行走能力為P0,則逆風(fēng)行走時(shí)

P0=Fv0=(F+Fw)v.

(3)

式中：F為人行走所作的力,N;v0為人的正常行走速度,m/s;Fw為風(fēng)力,N;v為人受風(fēng)影響后的行走速度,m/s。

假設(shè)人為一個(gè)長方形的物體,則

(4)

式中:cd為阻力系數(shù),經(jīng)驗(yàn)表明其與雷諾數(shù)有關(guān);ρ為氣體密度,kg/m3;S為人體與風(fēng)的接觸面,m2;vw為此條路上的風(fēng)速,m/s。根據(jù)式(3)和(4)有

(5)

則逆風(fēng)行走時(shí)的風(fēng)速影響系數(shù)為

(6)

同理可得,順風(fēng)行駛時(shí)的風(fēng)速影響系數(shù)為

(7)

但當(dāng)風(fēng)速很大時(shí),式(7)不適用。

3) 巷道坡度影響系數(shù)

巷道的坡度影響人員的行走速度,坡度越大,阻力越大。由此可得上坡時(shí)

P0=Fv0=mgvsinθicosθi.

(8)

式中：m為人體的標(biāo)準(zhǔn)質(zhì)量,kg;g為重力加速度,m/s2;θi為當(dāng)前巷道的坡度角,°; 假設(shè)人員通過斜坡巷道時(shí)的速度始終為v0,則上坡時(shí)的影響系數(shù)為

(9)

4) 巷道顆粒濃度影響系數(shù)

巷道顆粒濃度主要包括巷道能見度和氣體臨界層與地面的高度,這些都嚴(yán)重影響著人員的逃生速度,其影響系數(shù)為

kvi=(1+αh+Lr).

(10)

式中：αh為氣體臨界層與地面的高度的影響系數(shù),Lr是能見度影響系數(shù)。αh和Lr經(jīng)驗(yàn)取值分別如表1和表2所示。

表1 αh取值

表2 Lr取值

5)巷道擁擠度影響系數(shù)

人群的密集度從某種程度上影響著行走速度。本文采用Thompson[8]提出的人群密集度影響的行走速度模型:

(11)

式中：d為人與人之間的距離,td表示表示移動約束區(qū)間的上限,b表示水平方向上行走的人數(shù)。

6) 其他與礦難相關(guān)的特殊因素影響系數(shù)

為了簡化各種巷道災(zāi)害的數(shù)學(xué)模型,本文使用kdi,kdi∈(1,+∞)表示其他特殊因素的影響系數(shù),其中1表示巷道正常,沒有發(fā)生礦難,+∞表示此巷道不可通過。例如,嚴(yán)重滑坡,高溫以及水淹沒了巷道等情況都導(dǎo)致巷道不可通過。

1.2 巷道權(quán)值規(guī)范化

根據(jù)2.1的分析,巷道的當(dāng)量長度范圍為[0,+∞),其中+∞表示巷道不可通過。為了方面數(shù)據(jù)處理,根據(jù)式(12)將所有數(shù)據(jù)映射到(0,1]中:

(12)

式中：min(l)表示所有巷道的最小當(dāng)量長度m,max(l)表示所有巷道的最大當(dāng)量長度m(不包括長度值+∞)。式(12)表明wi越接近于0,越容易通過。當(dāng)?shù)扔?時(shí),表明巷道不同通過。

通過上述的權(quán)值規(guī)范化,可以根據(jù)所提的改進(jìn)差分進(jìn)化算法來尋找最優(yōu)逃生路徑。

2 基于改進(jìn)差分進(jìn)化算法的逃生路徑優(yōu)化

本文提出一種通過改進(jìn)差分進(jìn)化算法的變異策略及加入?yún)?shù)自適應(yīng)機(jī)制來提高算法的搜索效率,從而快速有效的求出最優(yōu)逃生路徑及其他次最優(yōu)路徑。

2.1 基本差分進(jìn)化算法

DE算法通過種群內(nèi)個(gè)體間的合作與競爭來實(shí)現(xiàn)對優(yōu)化問題的求解,其本質(zhì)是一種基于實(shí)數(shù)編碼的具有保優(yōu)思想的貪婪遺傳算法。與其他進(jìn)化算法一樣,DE算法也包括初始化、變異、交叉和選擇四個(gè)操作。算法首先在定義域范圍內(nèi)隨機(jī)生成初始種群,然后通過變異和交叉操作產(chǎn)生新個(gè)體,最后通過選擇操作決定新個(gè)體是否能成功進(jìn)入下一代。假設(shè)目標(biāo)函數(shù)為f(x),x=(x1,x2,…,xN)∈RN,可行域?yàn)镈,則具體步驟如下:

1) 初始化

在目標(biāo)問題的可行解空間D中隨機(jī)初始化種群P=[x1,x2,…,xNp],Np為種群規(guī)模,xi=[xi,1,xi,2,…,xi,N]表示目標(biāo)問題的解,N為目標(biāo)問題的維數(shù)。

2) 變異

).

(13)

(14)

3) 交叉

4) 選擇

(16)

式中：f為目標(biāo)函數(shù)。

2.2 改進(jìn)變異策略

眾所周知,DE/best/1在求解過程中促使種群中的每個(gè)個(gè)體向當(dāng)前種群中的最優(yōu)個(gè)體收斂,因此對單模問題和一些簡單的多模問題求解時(shí)具有很快的收斂速度,但是對于一些高維多模問題,很容易陷入局部最優(yōu)而出現(xiàn)早熟收斂。DE/rand/1是一種最常用的變異策略,他能夠很好的維持種群的多樣性,全局搜索能力較強(qiáng),但是局部搜索能力較弱,導(dǎo)致后期收斂速度很慢。為了平衡DE算法的全局搜索能力和收斂速度,本文提出一種改進(jìn)變異策略,將DE/best/1和DE/rand/1混合使用。

在群體初始化過程中,將DE/best/1和DE/rand/1隨機(jī)分配給每個(gè)個(gè)體,且在整個(gè)進(jìn)化過程中保持不變,設(shè)Mi為個(gè)體Xi的變異策略,則

(17)

式中：randi為[0,1]之間的隨機(jī)數(shù)。

2.3 參數(shù)自適應(yīng)策略

相關(guān)文獻(xiàn)研究表明,DE算法的性能高度依賴于控制參數(shù)(如種群規(guī)模Np、增益常數(shù)F和交叉概率CR)[8]。由于不同的優(yōu)化問題有著不同的數(shù)學(xué)特性,不恰當(dāng)?shù)膮?shù)不僅會導(dǎo)致算法計(jì)算代價(jià)較大(如函數(shù)評價(jià)次數(shù))、收斂速度較慢,而且極易趨于早熟收斂而陷于局部最優(yōu)解。本文提出一種簡單的參數(shù)自適應(yīng)策略來動態(tài)調(diào)整參數(shù)F和CR。

(18)

式中：N(0.5,0.1)為均值為0.5,標(biāo)準(zhǔn)誤差為0.1的正態(tài)分布隨機(jī)數(shù)。式(18)表明,如果當(dāng)前的CR能夠產(chǎn)生較優(yōu)的新個(gè)體,則在下一代時(shí)繼續(xù)保值不變,否則重新生成CR。

對于參數(shù)F,根據(jù)均值為0.5,標(biāo)準(zhǔn)誤差為0.3的正態(tài)分布隨機(jī)數(shù)生成,即N(0.5,0.3)。

3 實(shí)驗(yàn)

為了驗(yàn)證模型和所提算法的有效性,通過文獻(xiàn)[9]的實(shí)例來進(jìn)行求解分析,圖2給出了礦井的網(wǎng)絡(luò)拓?fù)鋱D。實(shí)驗(yàn)中,模型中的參數(shù)設(shè)置如3所示。算法參數(shù)設(shè)置為CR=0.5,F=0.5。表4給出了地下巷道網(wǎng)絡(luò)(圖1)的部分?jǐn)?shù)據(jù)和權(quán)重值。

表3 基本參數(shù)設(shè)置

通過所提出的改進(jìn)差分進(jìn)化算法,對圖1所示的礦井網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化求取最優(yōu)路線及次優(yōu)路線。表5給出了算法5次獨(dú)立運(yùn)行中得出的最優(yōu)路線和兩條次優(yōu)可選路線。從表中可以看出,最優(yōu)路線在節(jié)點(diǎn)82和節(jié)點(diǎn)1之間,最優(yōu)路線在5次運(yùn)行中均為(83,84,82,80,77,76,74,63,57,55,45,1),比較穩(wěn)定,其他兩條次優(yōu)可選路線不穩(wěn)定,在5次算法運(yùn)行中得出的結(jié)果不同。圖1中繪制出了算法第一次運(yùn)行的結(jié)果,其中紅色路線為最優(yōu)路線,綠色為次優(yōu)路線1,藍(lán)色為次優(yōu)路線2。

表4 地下巷道網(wǎng)絡(luò)的部分?jǐn)?shù)據(jù)和權(quán)重值

表5 算法5次獨(dú)立運(yùn)行的結(jié)果

圖1 地下礦井網(wǎng)絡(luò)拓?fù)銯ig.1 Network topology of underground mine

4 結(jié)束語

本文首先通過對地下礦井逃生中的各種影響因素進(jìn)行了分析,建立了巷道權(quán)值模型。其次,提出一種改進(jìn)差分進(jìn)化算法快速有效的求解逃生路徑,在改進(jìn)差分進(jìn)化算法中,通過一種混合變異策略及參數(shù)自適應(yīng)機(jī)制來提高算法的搜索效率和收斂速度。最后通過一個(gè)實(shí)例來驗(yàn)證了所提算法的有效性,實(shí)驗(yàn)結(jié)果表明,所提算法能夠快速穩(wěn)定的求得最優(yōu)逃生路徑及其他次優(yōu)可選路徑。

[1] 楊大明.煤礦井下緊急避險(xiǎn)系統(tǒng)的建設(shè)與發(fā)展[J].煤炭科學(xué)技術(shù),2010,38(11):6-9.

YANG Daming.Construction and Development of Emergency Refuge System in Underground Mine[J].Coal Science and Technology,2010,38(11):6-9.

[2] 李舒伶.井下最佳避災(zāi)路線確定[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，1999，18(1)：27-29.

LI Shuling.The Confirmation of the Best Route for Evading Accident Under the Pit[J].Journal of Liao Ning Technical University,1999,18(1):27-29.

[3] 侯運(yùn)炳,夏興,閆旭.基于礦井地理網(wǎng)絡(luò)模型的最短路徑改進(jìn)算法[J].2011,39(2):103-105.

HOU Yunbing,XIA Xing,YAN Xu.Improved Shortest Path Algorithm Based on Mine Geographic Network Model[J].Coal Science and Technology,2011,39(2):103-105.

[4] Jalali S E,Noroozi M.Determination of the Optimal Escape Routes of Underground Mine Networks in Emergency Cases[J].Safety Science,2009,47(8):1077-1082.

[5] Storn R,Price K.Differential Evolution-A Simple and Efficient Heuristic for Global Optimization Over Continuous Spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[6] 周曉根,張貴軍,郝小虎.局部抽象凸區(qū)域剖分差分進(jìn)化算法[J].自動化學(xué)報(bào),2015,41(7):1315-1327.

ZHOU Xiagen,ZHANG Guijun,HAO Xiaohu.Differential Evolution Algorithm with Local Abstract Convex Region Partition[J].Acta Automatica Sinica,2015,41(7):1315-1327.

[7] Das S,Suganthan P N.Differential Evolution:a Survey of the State-of-the-art[J].IE Transactions on Evolutionary Computation,2011,15(1):4-31.

[8] Thompson P,Marehant E.A Computer Model for the Evacuation of Large Building Populations[J].Fire Safety Journal,1995,24(2):131-148.

[9] Stutzle T,Hoos H H.Max-Min Ant System[J].Future Generation Computer Systems,2000,16(8):889-914.

OptimizationofEscapeRouteinCoalMineBasedonImprovedDifferentialEvolutionAlgorithm

ZHAOHaijun

(YangquanNanzhuangCoalGroupCo.,Ltd.,Yangquan045001,China)

To reduce the loss and improve the surviving probability of trapped miners in mine disasters, a new escape route optimization method for mines is proposed with an improved differential evolution algorithm. Six influential factors are analyzed to build a weight calculation model. Then, a hybrid mutation strategy and parameter adaptive mechanism are used to improve the searching efficiency of the differential evolution algorithms in order to find the optimal escape route quickly.The results show that the proposed method could effectively find the optimal route and alternative routes.

optimization;escape;roadway;differential evolution

1672-5050(2017)01-0051-05

10.3919/j.cnki.issn1672-5050sxmt.2017.02.016

2016-05-19

趙海軍(1970-),男,山西陽泉人,大學(xué)本科,工程師,從事礦井通風(fēng)安全研究。

TP18

A

(編輯：薄小玲)