基于改進(jìn)螢火蟲(chóng)算法的礦井水害避災(zāi)路徑規(guī)劃

王 鵬，朱希安，王占剛，劉德民

(1.北京信息科技大學(xué)信息與通信工程學(xué)院，北京 100101；2.華北科技學(xué)院安全工程學(xué)院，北京 101601)

在煤礦生產(chǎn)過(guò)程中，從業(yè)人員在巷道中隨時(shí)面臨著礦井突水等自然災(zāi)害的威脅。當(dāng)突水災(zāi)害發(fā)生時(shí)，如何使受困人員盡快擺脫險(xiǎn)境，是一個(gè)值得考慮的問(wèn)題。地下井巷道交錯(cuò)復(fù)雜，從事故發(fā)生地到安全區(qū)域通常會(huì)有很多條路徑，在諸多路徑中選擇一條最優(yōu)路徑符合從業(yè)人員的安全利益[1-2]。

有學(xué)者對(duì)礦井突水逃生路徑規(guī)劃問(wèn)題進(jìn)行了研究。苑亞南等[3]通過(guò)綜合考慮突水點(diǎn)處流體力學(xué)特性、巷道基本信息，提出了基于改進(jìn)的D-K路徑搜索算法的多路徑逃生模型；蔡明杰等[4]通過(guò)重新設(shè)計(jì)遺傳算子，引入新的交叉、變異算子，較好地提高了遺傳算法在規(guī)劃路徑時(shí)的收斂速度和可靠性；劉夢(mèng)杰等[5]通過(guò)將傳統(tǒng)A*算法單向搜索方式改為雙向搜索并改進(jìn)評(píng)估函數(shù)的定義，使得每一步搜索都根據(jù)評(píng)估函數(shù)朝著某個(gè)方向搜索。隨著計(jì)算機(jī)運(yùn)算能力的加強(qiáng)，蟻群算法等元啟發(fā)式算法逐漸成為路徑規(guī)劃的主流算法。但是，上述算法都存在以下缺點(diǎn)中的一個(gè)或多個(gè)：易陷入局部最優(yōu)、收斂效果不佳、無(wú)效計(jì)算過(guò)多等。鑒于上述背景，本文通過(guò)引入巷道當(dāng)量長(zhǎng)度以調(diào)整螢火蟲(chóng)的初始化方式，改變螢火蟲(chóng)的間距、最大亮度和相對(duì)亮度等要素的定義，結(jié)合王家?guī)X礦實(shí)例實(shí)現(xiàn)對(duì)避災(zāi)路徑的最優(yōu)規(guī)劃。

1 巷道當(dāng)量長(zhǎng)度

考慮到受困人員的身體狀況以及每條巷道的客觀干擾因素，諸如風(fēng)速風(fēng)向、巷道坡度、局部障礙物類型、有毒有害氣體濃度等都會(huì)對(duì)逃生巷道的安全性產(chǎn)生影響，所以不能簡(jiǎn)單地求解線路的最短距離并以此充當(dāng)最優(yōu)路徑。因此，本文將當(dāng)量長(zhǎng)度的概念引入避災(zāi)路徑的規(guī)劃中，通過(guò)綜合評(píng)價(jià)巷道中對(duì)逃生安全有重要影響的因素，計(jì)算巷道的當(dāng)量長(zhǎng)度[6]，并將該值作為巷道網(wǎng)絡(luò)結(jié)構(gòu)的權(quán)重。

1.1 影響系數(shù)的定義

通過(guò)對(duì)巷道實(shí)際情況的研判，本文重點(diǎn)的干擾因素為風(fēng)速(含風(fēng)向)、巷道坡度、局部障礙物類型、巷道類型，對(duì)應(yīng)的影響系數(shù)[7]分別為δ1、δ2、δ3、δ4，干擾因素的影響系數(shù)見(jiàn)表1。 設(shè)不受某項(xiàng)因素影響時(shí)通過(guò)巷道Rij的速度為V0，受某項(xiàng)因素影響時(shí)通過(guò)巷道Rij的速度為V，則影響系數(shù)的表達(dá)式為式(1)。

表1 巷道干擾因素及影響系數(shù)Table 1 Disturbance factors and influence coefficients of roadway

(1)

1.2 巷道當(dāng)量長(zhǎng)度的求解

將各巷道影響系數(shù)加權(quán)到對(duì)應(yīng)的巷道實(shí)際長(zhǎng)度即可得巷道當(dāng)量長(zhǎng)度。設(shè)定節(jié)點(diǎn)i和節(jié)點(diǎn)j(i，j須為可直接相連的兩點(diǎn))之間的巷道實(shí)際長(zhǎng)度為lij，δ1，δ2，δ3，…，δn為該巷道干擾因素的影響系數(shù)，巷道Rij的當(dāng)量長(zhǎng)度wij定義見(jiàn)式(2)。

wij=[1+δ1+δ2+δ3+…+δn]lij

(2)

若有一條從突水點(diǎn)至安全點(diǎn)的路徑U，包含p段巷道，第q條巷道的當(dāng)量長(zhǎng)度用wq表示，則路徑U的當(dāng)量長(zhǎng)度WU可表示為式(3)。

(3)

當(dāng)量長(zhǎng)度表示通過(guò)該逃生路徑的難易程度，路徑的當(dāng)量長(zhǎng)度值越大，代表該路徑越難以通過(guò)；路徑的當(dāng)量長(zhǎng)度值越小，代表該路徑越容易通過(guò)?？蓪⒏倪M(jìn)后的螢火蟲(chóng)算法中的目標(biāo)函數(shù)用當(dāng)量長(zhǎng)度表示，巷道當(dāng)量長(zhǎng)度越小則目標(biāo)函數(shù)越優(yōu)，反之則越差。

2 標(biāo)準(zhǔn)螢火蟲(chóng)算法

2.1 標(biāo)準(zhǔn)螢火蟲(chóng)算法基本原理

螢火蟲(chóng)算法(firefly algorithm，F(xiàn)A)是一種基于螢火蟲(chóng)的發(fā)光模式和運(yùn)動(dòng)模式的元啟發(fā)式算法。其原理是螢火蟲(chóng)隨機(jī)地分布在特定的場(chǎng)域中，亮度較小的螢火蟲(chóng)會(huì)飛向亮度較大的螢火蟲(chóng)，隨著移動(dòng)的過(guò)程在亮度較大的螢火蟲(chóng)處聚集。螢火蟲(chóng)算法是通過(guò)其運(yùn)動(dòng)、更新位置的過(guò)程來(lái)探尋最優(yōu)解的過(guò)程[8]。

螢火蟲(chóng)相對(duì)亮度的表達(dá)式見(jiàn)式(4)。

(4)

式中：I0為螢火蟲(chóng)距離為零時(shí)的亮度，即最大亮度；γ為光吸收系數(shù)；Rij為螢火蟲(chóng)i和j的間距。

螢火蟲(chóng)吸引度表達(dá)式見(jiàn)式(5)。

(5)

式中：β0為兩只螢火蟲(chóng)距離為零時(shí)的吸引力大小，即最大吸引力；γ、Rij含義同式(4)。

任意兩只螢火蟲(chóng)的間距通過(guò)笛卡爾距離定義，表達(dá)式見(jiàn)式(6)。

(6)

式中：xi、xj為螢火蟲(chóng)i、j在場(chǎng)域中的位置；d為解空間的總維度。

螢火蟲(chóng)移動(dòng)后位置的表達(dá)式見(jiàn)式(7)。

xi(t+1)=xi(t)+β(Rij)(xj(t)-xi(t))+αεi

(7)

式中：xi(t)、xj(t)為螢火蟲(chóng)i、j在第t次迭代所處位置；α為隨機(jī)化參數(shù)，α∈[0,1]；εi為搜索精度，εi∈[-0.5,0.5]。

2.2 標(biāo)準(zhǔn)螢火蟲(chóng)算法描述

在尋優(yōu)問(wèn)題中，目標(biāo)函數(shù)表示為螢火蟲(chóng)的亮度，亮度越大代表該螢火蟲(chóng)所處的空間解越好。螢火蟲(chóng)算法首先設(shè)定一些基本參數(shù)，通過(guò)循環(huán)迭代螢火蟲(chóng)的亮度并更新螢火蟲(chóng)的亮度和位置，直至滿足終止條件[9]。標(biāo)準(zhǔn)螢火蟲(chóng)算法步驟如下所述。①設(shè)定基本參數(shù)：β0、γ、α、N(螢火蟲(chóng)數(shù)量)、T(最大迭代次數(shù))；②隨機(jī)初始化螢火蟲(chóng)位置，根據(jù)目標(biāo)函數(shù)計(jì)算其亮度；③計(jì)算螢火蟲(chóng)的亮度和吸引度，確定螢火蟲(chóng)的移動(dòng)方向；④確定螢火蟲(chóng)更新移動(dòng)后的位置，對(duì)其亮度進(jìn)行重新計(jì)算；⑤若達(dá)到最大迭代次數(shù)則結(jié)束算法，否則返回到第②步繼續(xù)搜索；⑥輸出結(jié)果，算法程序結(jié)束。標(biāo)準(zhǔn)螢火蟲(chóng)算法流程圖如圖1所示。

圖1 標(biāo)準(zhǔn)螢火蟲(chóng)算法流程圖Fig.1 Flow chart of standard firefly algorithm

標(biāo)準(zhǔn)螢火蟲(chóng)算法雖然具有參數(shù)少、操作性強(qiáng)等優(yōu)點(diǎn)，但也具有易陷入局部最優(yōu)的缺點(diǎn)。螢火蟲(chóng)都是飛向比自己亮度更大的螢火蟲(chóng)，但當(dāng)螢火蟲(chóng)個(gè)體全都集中于場(chǎng)域中的某一個(gè)或某幾個(gè)位置時(shí)，其搜索能力顯著下降。本文通過(guò)改進(jìn)螢火蟲(chóng)基本要素的定義及搜索策略，將螢火蟲(chóng)算法應(yīng)用于礦井突水逃生路徑規(guī)劃的研究。

3 改進(jìn)的螢火蟲(chóng)算法

3.1 改進(jìn)的螢火蟲(chóng)算法描述

設(shè)定在某場(chǎng)域中有N只螢火蟲(chóng)，M個(gè)離散點(diǎn)(巷道節(jié)點(diǎn))，針對(duì)礦井逃生路徑，令每只螢火蟲(chóng)代表一條完整的從突水點(diǎn)至安全點(diǎn)的路徑。首先，對(duì)螢火蟲(chóng)進(jìn)行初始化可得N條逃生路徑，計(jì)算每條路徑的當(dāng)量長(zhǎng)度，保留當(dāng)量長(zhǎng)度最小的路徑，定義其為全局最優(yōu)路徑。此處，將螢火蟲(chóng)最大亮度定義為該條路徑當(dāng)量長(zhǎng)度的倒數(shù)。其次，比較螢火蟲(chóng)的最大亮度值和種群最大亮度平均值，舍棄最大亮度值低于種群平均亮度值的路徑，保留大于等于種群平均亮度值的路徑，對(duì)舍棄的路徑重新初始化。最后，計(jì)算螢火蟲(chóng)之間的相對(duì)亮度，以確定螢火蟲(chóng)的移動(dòng)方向并進(jìn)行移動(dòng)。將移動(dòng)后的路徑當(dāng)量長(zhǎng)度與當(dāng)前全局最優(yōu)路徑對(duì)比，若移動(dòng)后有路徑的當(dāng)量長(zhǎng)度小于當(dāng)前全局最優(yōu)路徑，則保留該路徑的當(dāng)量長(zhǎng)度并將其記為全局最優(yōu)路徑；反之則不變。通過(guò)數(shù)次迭代即可得到全局最優(yōu)路徑，該路徑可滿足礦井水害避災(zāi)路徑規(guī)劃的需求。

3.2 改進(jìn)的螢火蟲(chóng)算法具體步驟

1) 初始化螢火蟲(chóng)。如圖2所示，設(shè)定節(jié)點(diǎn)a0有n個(gè)與之直接相連的節(jié)點(diǎn)序列a={a1，a2，a3，…，an}，本文通過(guò)輪盤賭結(jié)合路徑權(quán)重的方法初始化螢火蟲(chóng)。若ap為節(jié)點(diǎn)序列a中的一點(diǎn)，則節(jié)點(diǎn)a0選擇ap為下一節(jié)點(diǎn)的概率計(jì)算見(jiàn)式(8)。

圖2 螢火蟲(chóng)初始化的選擇概率Fig.2 Selection probability of firefly initialization

(8)

式中：k∈{1,2，…，n}；w0p為節(jié)點(diǎn)a0與ap相連路徑的權(quán)重；w0k定義同理。若兩節(jié)點(diǎn)不相連，則兩節(jié)點(diǎn)互相選擇的概率均為0。

為選擇一條從突水點(diǎn)至安全點(diǎn)的有效路徑，必須保證已選擇的點(diǎn)不會(huì)再被選擇，故建立相鄰點(diǎn)矩陣和移動(dòng)選擇矩陣。相鄰點(diǎn)矩陣通過(guò)設(shè)定任意兩點(diǎn)的關(guān)系為1或0來(lái)判斷是否直接相連，若節(jié)點(diǎn)a0和a1直接相連，則表示為Con(a0，a1)=1；若節(jié)點(diǎn)a0和b0不直接相連，則表示為Con(a0，b0)=0。移動(dòng)選擇矩陣中的值表示為任意一點(diǎn)選擇另一直接相連點(diǎn)的概率，若節(jié)點(diǎn)a0選擇到了a1為其下一節(jié)點(diǎn)，則Con(a0，a1)=1，并修改a1對(duì)a0的移動(dòng)概率為P(a0，a1)=0，可保證節(jié)點(diǎn)a1不會(huì)再選擇到節(jié)點(diǎn)a0。以突水點(diǎn)為起點(diǎn)進(jìn)行初始化直至選擇到安全點(diǎn)為止，即可得到一條完整路徑。

2) 舍棄劣質(zhì)螢火蟲(chóng)路徑。通過(guò)求得初始化后螢火蟲(chóng)路徑的最大亮度平均值，逐個(gè)將螢火蟲(chóng)的最大亮度值與最大亮度平均值進(jìn)行比較，當(dāng)某螢火蟲(chóng)亮度值大于或等于亮度平均值時(shí)，則保留該條路徑；反之，則不予保留。并返回步驟1)重新初始化舍棄掉的螢火蟲(chóng)路徑。

3) 最大亮度。由于螢火蟲(chóng)都是向比自己亮度大的螢火蟲(chóng)移動(dòng)，所以將螢火蟲(chóng)的最大亮度定義為目標(biāo)函數(shù)的倒數(shù)，即螢火蟲(chóng)將通過(guò)迭代移動(dòng)至目標(biāo)函數(shù)(當(dāng)量長(zhǎng)度值)比自己小的螢火蟲(chóng)個(gè)體。

4) 相對(duì)亮度和吸引度。由于螢火蟲(chóng)序列中節(jié)點(diǎn)數(shù)可能不一致，所以對(duì)螢火蟲(chóng)的節(jié)點(diǎn)序列進(jìn)行補(bǔ)0操作。設(shè)某螢火蟲(chóng)i包含n個(gè)節(jié)點(diǎn)，記為Xi={xi1，xi2，…，xin}；某螢火蟲(chóng)j包含m個(gè)節(jié)點(diǎn)，記為Xj={xj1，xj2，…，xjm}，在螢火蟲(chóng)i序列的終點(diǎn)xin前補(bǔ)(M-n)個(gè)0，在螢火蟲(chóng)j序列的終點(diǎn)xjn前補(bǔ)(M-m)個(gè)0，使每個(gè)序列中節(jié)點(diǎn)個(gè)數(shù)均為節(jié)點(diǎn)總數(shù)。螢火蟲(chóng)i到螢火蟲(chóng)j的距離表示為式(9)。

(9)

式中，xik、xjk為螢火蟲(chóng)i、j的第k個(gè)節(jié)點(diǎn)。

5) 移動(dòng)。從兩條路徑中選擇任意一個(gè)公共點(diǎn)，將公共點(diǎn)后的一段路徑進(jìn)行替換以完成移動(dòng)。如螢火蟲(chóng)i的路徑序列為Xi={xi1，xi2，…，xiM}；某螢火蟲(chóng)j的路徑序列為Xj={xj1，xj2，…，xjM}，選擇一公共點(diǎn)(不考慮終點(diǎn))xia=xjb，若螢火蟲(chóng)i移動(dòng)至j，則將xjb后長(zhǎng)度小于等于μ的一段路徑取代xia后長(zhǎng)度小于等于μ的一段路徑，如果替換后螢火蟲(chóng)i仍為從起點(diǎn)到終點(diǎn)的完整路徑，則結(jié)束移動(dòng)；反之，則隨機(jī)另找一公共點(diǎn)進(jìn)行上述操作，直至找到一條可行路線。若沒(méi)有找到可行路線，則重新移動(dòng)。移動(dòng)后對(duì)螢火蟲(chóng)的最大亮度、相對(duì)亮度、吸引度更新，若更新后的值小于全局最優(yōu)解的值，則將全局最優(yōu)解替換為更新后的值。

6) 終止迭代。若達(dá)到最大迭代次數(shù)，則終止循環(huán)，輸出全局最優(yōu)解。反之，則返回步驟2)繼續(xù)循環(huán)。改進(jìn)的螢火蟲(chóng)算法流程圖如圖3所示。

圖3 改進(jìn)的螢火蟲(chóng)算法流程圖Fig.3 Flow chart of improved firefly algorithm

4 改進(jìn)的螢火蟲(chóng)算法在王家?guī)X礦的實(shí)現(xiàn)

本文選取王家?guī)X部分巷道構(gòu)建了如圖4所示的無(wú)向網(wǎng)絡(luò)結(jié)構(gòu)圖，圖中的圓圈表示巷道節(jié)點(diǎn)，線段表示巷道，圖中未等比例構(gòu)建。統(tǒng)計(jì)的巷道干擾因素、影響系數(shù)及巷道當(dāng)量長(zhǎng)度見(jiàn)表2。通過(guò)使用改進(jìn)的螢火蟲(chóng)算法和A*算法規(guī)劃逃生路徑，比較和分析兩個(gè)算法規(guī)劃的路徑結(jié)果。

圖4 巷道簡(jiǎn)化架構(gòu)圖Fig.4 Simplified architecture diagram of roadway

表2 王家?guī)X局部巷道實(shí)際長(zhǎng)度及干擾因素信息Table 2 Information on actual length and interference factors of local roadways in Wangjialing

為驗(yàn)證算法在路徑規(guī)劃中的可行性，本文基于MATLAB環(huán)境進(jìn)行仿真。因算法采用輪盤賭的方式進(jìn)行節(jié)點(diǎn)選擇，路徑規(guī)劃結(jié)果會(huì)受到隨機(jī)因素的影響，為了減小隨機(jī)因素所帶來(lái)的差異，本文設(shè)置多組突水點(diǎn)和安全點(diǎn)以提高實(shí)驗(yàn)的可靠性。改進(jìn)的螢火蟲(chóng)算法參數(shù)取值為：巷道節(jié)點(diǎn)數(shù)M=16，螢火蟲(chóng)個(gè)數(shù)N=40，最大迭代次數(shù)T=40，光吸收系數(shù)γ=1.0，替換長(zhǎng)度數(shù)μ=600。改進(jìn)后的螢火蟲(chóng)算法和A*算法路徑規(guī)劃的測(cè)試結(jié)果見(jiàn)表3和表4。

通過(guò)分析表3和表4的實(shí)驗(yàn)結(jié)果可知，改進(jìn)的螢火蟲(chóng)算法所規(guī)劃路徑的實(shí)際長(zhǎng)度和當(dāng)量長(zhǎng)度比A*算法求得的長(zhǎng)度都短，表明改進(jìn)的螢火蟲(chóng)算法更易找到最優(yōu)解。因?yàn)楸疚目紤]了巷道中的干擾因素，故本算法規(guī)劃的逃生路徑能更好地滿足受困人員的安全利益，在礦井事故應(yīng)急救援應(yīng)用中具有較大的價(jià)值。

表3 優(yōu)化算法與A*算法規(guī)劃路徑線路對(duì)比Table 3 Comparison of optimization algorithm and A* algorithm for planning route routes

表4 優(yōu)化算法與A*算法規(guī)劃路徑長(zhǎng)度對(duì)比Table 4 Comparison of optimization algorithm and A* algorithm planning path length

5 結(jié) 論

1) 提出了改進(jìn)的螢火蟲(chóng)算法，重新規(guī)劃螢火蟲(chóng)算法的初始化方式、螢火蟲(chóng)之間的距離等要素，改變搜索策略，改進(jìn)后的算法具有全局優(yōu)化能力強(qiáng)、穩(wěn)定性強(qiáng)、收斂效果佳等優(yōu)點(diǎn)。

2) 考慮了影響巷道通行的諸多不利因素，并以當(dāng)量長(zhǎng)度的形式數(shù)值化地表示通過(guò)巷道的難易程度，該改進(jìn)算法可規(guī)劃出滿足受困人員安全利益的路徑。

3) 通過(guò)實(shí)例對(duì)比，改進(jìn)的螢火蟲(chóng)算法相比于A*算法規(guī)劃出的路徑實(shí)際長(zhǎng)度和當(dāng)量長(zhǎng)度均有減少。即螢火蟲(chóng)算法可以應(yīng)用于礦井水害避災(zāi)路徑規(guī)劃的場(chǎng)景中，有效降低受困人員的傷亡率。