基于改進差分進化算法的煤礦井下逃生路徑優化

趙海軍

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

基于改進差分進化算法的煤礦井下逃生路徑優化

趙海軍

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

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

優化; 逃生;巷道;差分進化

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

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

差分進化算法(DE)[5]作為一種隨機性算法,是進化算法中最簡單而高效的算法。DE算法通過模仿生物群體內個體間的合作產生的群體智能實現對優化問題的求解,具有能夠記憶個體最優解,種群內信息共享及易于其他算法結合的特點[6],在電力系統、化學工程、公交調度及生物信息學等領域得到了廣泛應用[7],尤其對大規模網絡最優路徑優化問題極其有效。

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

1 巷道權值計算模型

1.1 巷道當量長度計算

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

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

(1)

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

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

1)巷道類型影響系數

地下巷道通常分為工作面、運輸膠帶巷、聯絡巷、鐵路巷、漏風分支和通風井,其中,漏風分支和通風井無法通過。這些都影響著人員的逃生速度,例如,在鐵路巷中,逃生速度則與交通速度有關。巷道類型的影響系數:

(2)

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

2) 風速影響系數

采礦網絡本身就是一個完整的通風系統,一般總回流車道的風速很大,風速可能影響人員的逃生速度。風速的影響程度通常與道路的實際長度成正比。假設人員的行走能力為P0,則逆風行走時

P0=Fv0=(F+Fw)v.

(3)

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

假設人為一個長方形的物體,則

(4)

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

(5)

則逆風行走時的風速影響系數為

(6)

同理可得,順風行駛時的風速影響系數為

(7)

但當風速很大時,式(7)不適用。

3) 巷道坡度影響系數

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

P0=Fv0=mgvsinθicosθi.

(8)

式中：m為人體的標準質量,kg;g為重力加速度,m/s2;θi為當前巷道的坡度角,°; 假設人員通過斜坡巷道時的速度始終為v0,則上坡時的影響系數為

(9)

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

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

kvi=(1+αh+Lr).

(10)

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

表1 αh取值

表2 Lr取值

5)巷道擁擠度影響系數

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

(11)

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

6) 其他與礦難相關的特殊因素影響系數

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

1.2 巷道權值規范化

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

(12)

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

通過上述的權值規范化,可以根據所提的改進差分進化算法來尋找最優逃生路徑。

2 基于改進差分進化算法的逃生路徑優化

本文提出一種通過改進差分進化算法的變異策略及加入參數自適應機制來提高算法的搜索效率,從而快速有效的求出最優逃生路徑及其他次最優路徑。

2.1 基本差分進化算法

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

1) 初始化

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

2) 變異

).

(13)

(14)

3) 交叉

4) 選擇

(16)

式中：f為目標函數。

2.2 改進變異策略

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

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

(17)

式中：randi為[0,1]之間的隨機數。

2.3 參數自適應策略

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

(18)

式中：N(0.5,0.1)為均值為0.5,標準誤差為0.1的正態分布隨機數。式(18)表明,如果當前的CR能夠產生較優的新個體,則在下一代時繼續保值不變,否則重新生成CR。

對于參數F,根據均值為0.5,標準誤差為0.3的正態分布隨機數生成,即N(0.5,0.3)。

3 實驗

為了驗證模型和所提算法的有效性,通過文獻[9]的實例來進行求解分析,圖2給出了礦井的網絡拓撲圖。實驗中,模型中的參數設置如3所示。算法參數設置為CR=0.5,F=0.5。表4給出了地下巷道網絡(圖1)的部分數據和權重值。

表3 基本參數設置

通過所提出的改進差分進化算法,對圖1所示的礦井網絡拓撲進行優化求取最優路線及次優路線。表5給出了算法5次獨立運行中得出的最優路線和兩條次優可選路線。從表中可以看出,最優路線在節點82和節點1之間,最優路線在5次運行中均為(83,84,82,80,77,76,74,63,57,55,45,1),比較穩定,其他兩條次優可選路線不穩定,在5次算法運行中得出的結果不同。圖1中繪制出了算法第一次運行的結果,其中紅色路線為最優路線,綠色為次優路線1,藍色為次優路線2。

表4 地下巷道網絡的部分數據和權重值

表5 算法5次獨立運行的結果

圖1 地下礦井網絡拓撲Fig.1 Network topology of underground mine

4 結束語

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

[1] 楊大明.煤礦井下緊急避險系統的建設與發展[J].煤炭科學技術,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] 李舒伶.井下最佳避災路線確定[J].遼寧工程技術大學學報，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] 侯運炳,夏興,閆旭.基于礦井地理網絡模型的最短路徑改進算法[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] 周曉根,張貴軍,郝小虎.局部抽象凸區域剖分差分進化算法[J].自動化學報,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-),男,山西陽泉人,大學本科,工程師,從事礦井通風安全研究。

TP18

A

(編輯：薄小玲)