張雪英， 李智勇， 李鳳蓮， 陳桂軍

(太原理工大學(xué) 信息工程學(xué)院， 山西 晉中 030600)

用于求解井下最短逃生路徑問題的離散螢火蟲算法

張雪英， 李智勇， 李鳳蓮， 陳桂軍

(太原理工大學(xué) 信息工程學(xué)院， 山西 晉中 030600)

針對煤礦井下避災(zāi)路線最短路徑求解問題，提出了一種新的離散螢火蟲算法。該算法通過采用轉(zhuǎn)移概率方法初始化螢火蟲個(gè)體，并提出一種新的有效編碼和解碼方式，重新定義螢火蟲的空間距離、最大熒光亮度和相對熒光亮度等，使得螢火蟲個(gè)體的狀態(tài)可表示為一條從起點(diǎn)到目標(biāo)點(diǎn)的有效路徑。為增加解的多樣性及防止計(jì)算結(jié)果陷入局部最優(yōu)解，以一定概率對螢火蟲代表的路徑執(zhí)行擾動(dòng)操作，經(jīng)過多次迭代計(jì)算后，可得到所要求解的最短路徑。實(shí)驗(yàn)結(jié)果表明，該算法在種群規(guī)模較小、迭代次數(shù)較少的情況下可以收斂到最優(yōu)解，具有較強(qiáng)的收斂性和靈活性，可用于求解任何實(shí)際的最短路徑問題。

井下避災(zāi)； 最短路徑； 離散螢火蟲算法； 編碼； 解碼； 擾動(dòng)

0 引言

求解最短路徑是煤礦井下避災(zāi)[1-2]和智能車輛導(dǎo)航系統(tǒng)[3-4]等領(lǐng)域一個(gè)亟需解決的問題。在求解最短路徑的算法中，學(xué)界目前高度認(rèn)可的算法有經(jīng)典的Dijkstra算法[5-6]和Floyd算法，但這2種算法在搜索路徑時(shí)具有盲目性，且時(shí)間復(fù)雜度是它們的瓶頸。隨著群智能優(yōu)化算法的深入研究，一些新的算法不斷被提出，包括遺傳算法[7]、蟻群算法[8]及人工魚群算法[9]等。雖然遺傳算法和蟻群算法都能夠求解結(jié)構(gòu)較為復(fù)雜且維數(shù)較高情況下的最短路徑問題，但是它們也存在搜索效率低、計(jì)算結(jié)果都容易陷入局部最優(yōu)等缺點(diǎn)；人工魚群算法雖然可以在一定程度上避免陷入局部最優(yōu)，但是該算法收斂速度較慢，且隨著維數(shù)的增加，算法也容易陷入局部最優(yōu)。

在自然界的昆蟲類中，螢火蟲是通過發(fā)出一種熒光來求偶或覓食的。螢火蟲能夠發(fā)出熒光的原理：螢火蟲具有發(fā)光的細(xì)胞，細(xì)胞中含有化學(xué)物質(zhì)熒光素，這種化學(xué)物質(zhì)通過反應(yīng)可以發(fā)出亮光。螢火蟲發(fā)出的亮光越大，則它對別的個(gè)體的吸引力越大，別的地方的螢火蟲開始向這個(gè)地方靠近，慢慢地，原先分離的大部分螢火蟲個(gè)體都聚集到了一個(gè)(或多個(gè))位置上。螢火蟲算法(Firefly Algorithm，F(xiàn)A)正是根據(jù)這種群體行為的啟發(fā)演變而來的[10]，通過模擬自然界中螢火蟲發(fā)出熒光來吸引伴侶和覓食的行為，最終實(shí)現(xiàn)了目標(biāo)函數(shù)解的尋優(yōu)過程。

為了求解井下最短路徑問題，筆者提出了一種新的離散螢火蟲算法(Discrete Firefly Algorithm，DFA)。該算法采用轉(zhuǎn)移概率初始化的方法初始化螢火蟲個(gè)體，定義了螢火蟲的最大熒光亮度和相對熒光亮度等，并給出了螢火蟲個(gè)體間距離的計(jì)算公式。為加快算法的收斂速度和跳出局部最優(yōu)，對螢火蟲的擾動(dòng)行為重新做出了定義。最后，通過VC平臺實(shí)現(xiàn)該算法，并對實(shí)際煤礦井下拓?fù)鋱D進(jìn)行仿真實(shí)驗(yàn)，得出了準(zhǔn)確的計(jì)算結(jié)果。仿真實(shí)驗(yàn)結(jié)果表明，該算法具有收斂速度快、能跳出局部最優(yōu)的優(yōu)點(diǎn)，可用于求解任何實(shí)際的最短路徑問題。

1 螢火蟲算法

1.1 算法的具體原理

螢火蟲算法與其他群智能算法相似，采用種群多點(diǎn)并行全局隨機(jī)搜索的策略[11-12]。螢火蟲種群中每一個(gè)螢火蟲個(gè)體本身都攜帶一定數(shù)量的熒光素，且熒光素是可以更新的。螢火蟲的移動(dòng)方向是朝著它感知決策半徑范圍內(nèi)相對熒光亮度最大的螢火蟲靠近；對螢火蟲的位置進(jìn)行更改后，重新計(jì)算它們的最大熒光亮度和相對熒光亮度，然后重復(fù)上述移動(dòng)過程，最終實(shí)現(xiàn)所有螢火蟲聚集到亮度最大的一個(gè)(或幾個(gè))螢火蟲所處的位置上。通過亮度和吸引度等的不斷更新，從而實(shí)現(xiàn)目標(biāo)優(yōu)化。

1.2 算法參數(shù)和公式

相對熒光亮度定義為

I=I0exp(-γrij)

(1)

式中：I0為螢火蟲個(gè)體的最大螢光亮度；γ為光吸收系數(shù)，通常設(shè)為大于零的常數(shù)，該參數(shù)用來描述熒光受距離及周圍環(huán)境的影響而發(fā)生動(dòng)態(tài)變化；rij為螢火蟲個(gè)體i與螢火蟲個(gè)體j之間的距離。

相對熒光亮度大小體現(xiàn)了螢火蟲個(gè)體所在位置(即它的狀態(tài))的優(yōu)劣并決定其移動(dòng)方向。

吸引度定義為

β=β0exp(-γrij)

(2)

式中β0為最大吸引度，吸引度的大小決定了螢火蟲個(gè)體移動(dòng)的距離。

假設(shè)螢火蟲j向螢火蟲i移動(dòng)，則螢火蟲j移動(dòng)位置計(jì)算公式為

xj=xj+β(xi-xj)+α(rand-1/2)

(3)

式中：xj和xi分別為螢火蟲j和螢火蟲i所處的空間位置；α為步長因子，取值范圍為0～1；rand為隨機(jī)數(shù)。

2 離散螢火蟲算法

2.1 煤礦巷道網(wǎng)拓?fù)浣Y(jié)構(gòu)

煤礦巷道網(wǎng)是一個(gè)復(fù)雜的網(wǎng)絡(luò)系統(tǒng)。巷道網(wǎng)有巷道路線、巷道交叉口等物理屬性，將其抽象為帶權(quán)無向圖，用節(jié)點(diǎn)來表示網(wǎng)中的交叉路口，連接兩節(jié)點(diǎn)之間的邊表示為路線，并將路線的長度、通行時(shí)間、路況等屬性表示為該邊的權(quán)值。圖1是一個(gè)抽象的巷道無向圖網(wǎng)絡(luò)，其中圓圈表示巷道的節(jié)點(diǎn)，節(jié)點(diǎn)與節(jié)點(diǎn)直接相連表示此路徑可行，且數(shù)值的大小可表示從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)所用的時(shí)間或者節(jié)點(diǎn)間路徑的長度等。離散螢火蟲算法的目的是求取從其中某個(gè)節(jié)點(diǎn)到另一個(gè)不直接相連的節(jié)點(diǎn)的最短路徑(如從節(jié)點(diǎn)1到節(jié)點(diǎn)20)。

圖1 煤礦巷道無向圖網(wǎng)絡(luò)

2.2 相關(guān)概念

路徑的權(quán)重w(p)即構(gòu)成該路徑p的所有邊的權(quán)重之和：

(4)

直接相連的2個(gè)節(jié)點(diǎn)互為鄰近點(diǎn)。如圖1中節(jié)點(diǎn)2和節(jié)點(diǎn)6互為鄰近點(diǎn)。

轉(zhuǎn)移概率：若節(jié)點(diǎn)j鄰近點(diǎn)有j1,j2,…,jl，則轉(zhuǎn)移概率可表示為

(5)

式中u∈{1,2,…,l}。

在j,j1,…,jl中，若2個(gè)點(diǎn)不為鄰近點(diǎn)，則轉(zhuǎn)移概率為0。

2.3 編碼和解碼

本文采用一種新的整數(shù)編碼方式。為了方便起見，規(guī)定節(jié)點(diǎn)0為虛擬節(jié)點(diǎn)，即不存在的節(jié)點(diǎn)。節(jié)點(diǎn)0具有如下特點(diǎn)：

(1) 節(jié)點(diǎn)0到所有節(jié)點(diǎn)的權(quán)值為0，包括到自身，即w(l,q)=0，l=0或者q=0。

從 “夏偉訴亞馬遜公司擅自刪除訂單”案的判決看出，該案的主要爭議點(diǎn)在于:亞馬遜公司提供的“格式條款”是否對夏偉形成了法律約束力。因此，本文將主要圍繞兩個(gè)問題進(jìn)行探討：第一，電商平臺提供的格式條款在形式和程序上需要受什么規(guī)則約束；第二，進(jìn)一步思考，假設(shè)本案中的格式條款訂入了合同，那格式條款的內(nèi)容本身是否會(huì)因?yàn)楦牧恕逗贤ā逢P(guān)于合同成立的規(guī)則而產(chǎn)生效力瑕疵？以下將具體展開分析。

(2) 節(jié)點(diǎn)0到其他所有節(jié)點(diǎn)的轉(zhuǎn)移概率為0，理論上不存在從0節(jié)點(diǎn)轉(zhuǎn)移到其他節(jié)點(diǎn)，同理，也不能有其他節(jié)點(diǎn)轉(zhuǎn)移到節(jié)點(diǎn)0，Pi(0)=0或者P0(i)=0。

以圖1為例，求取從節(jié)點(diǎn)1到節(jié)點(diǎn)20的最短路徑，若有一個(gè)路徑p為1→4→15→19→20，即編碼前路徑為X(p)={1,4,15,19,20}，則編碼后的路徑X′(p)={1,4,15,19,0,…,0,20}，起點(diǎn)和終點(diǎn)固定，路徑的有效位數(shù)不足時(shí)，補(bǔ)0。由于X′(p)為N維，且起始位和結(jié)束位固定，所以，在計(jì)算中也可以等效為{4,15,19,0,…,0}，即N-2維。

解碼為編碼的逆過程，即從N-2維還原為N維。

(6)

式中：i,j∈{1,2,…,M}；xik為螢火蟲i編碼后路徑的第k個(gè)點(diǎn)；xjk為螢火蟲j編碼后路徑的第k個(gè)點(diǎn)。

路徑的有效點(diǎn)、有效路徑和有效點(diǎn)個(gè)數(shù)：路徑p中除了虛擬點(diǎn)0之外的點(diǎn)均為有效點(diǎn)。例如X′(p)={1,4,15,19,0,…,0,20}中，有效點(diǎn)為1,4,15,19,20，有效路徑即為1→4→15→19→20。顯然，有效點(diǎn)個(gè)數(shù)為除了虛擬節(jié)點(diǎn)0之外，其他點(diǎn)的個(gè)數(shù)總和，即有效點(diǎn)個(gè)數(shù)為5。

2.4 算法的具體原理及實(shí)施步驟

離散螢火蟲算法的具體原理：為求解煤礦井下避災(zāi)路線最短路徑，假設(shè)螢火蟲數(shù)目為M，令每個(gè)螢火蟲個(gè)體代表一條從起點(diǎn)到終點(diǎn)的有效路徑。首先采用轉(zhuǎn)移概率的初始化方法[13]初始化所有螢火蟲，即可得到M條有效路徑，從中選擇出目標(biāo)函數(shù)(路徑權(quán)重)最優(yōu)的路徑，保存為全局最短路徑，并把每個(gè)螢火蟲的有效路徑權(quán)重倒數(shù)作為它們各自的最大熒光亮度值。其次，通過計(jì)算兩兩螢火蟲之間的相對亮度，確定每個(gè)螢火蟲移動(dòng)的具體方向，即螢火蟲個(gè)體都是朝著相對亮度最大的那個(gè)螢火蟲個(gè)體靠近。將移動(dòng)后產(chǎn)生的新路徑與此時(shí)的全局最短路徑進(jìn)行比較，如果新產(chǎn)生的路徑中有比全局最短路徑權(quán)重和更小的，則用該路徑替換掉全局最短路徑，否則不予替換。然后，為增加解的多樣性并防止計(jì)算結(jié)果陷入局部最優(yōu)，以一定的概率對每個(gè)螢火蟲編碼后的路徑進(jìn)行隨機(jī)擾動(dòng)。把擾動(dòng)后產(chǎn)生的新路徑與此時(shí)全局最短路徑的權(quán)重和進(jìn)行比較，若新產(chǎn)生的路徑中存在比全局最短路徑權(quán)重和更小的路徑，則用它替換全局最短路徑，否則不予替換。最后，重新計(jì)算每個(gè)螢火蟲的最大熒光亮度，一定迭代次數(shù)計(jì)算后得到的最終結(jié)果，即為所要求解的避災(zāi)路線最短路徑。

步驟1 構(gòu)建鄰近點(diǎn)矩陣和概率轉(zhuǎn)移矩陣。

(1) 構(gòu)建N×N維的鄰近點(diǎn)矩陣A，該矩陣存放的值為1或0，1表示對應(yīng)的點(diǎn)為鄰近點(diǎn)，0表示對應(yīng)的點(diǎn)不為鄰近點(diǎn)。如A(0,1)=1，表示節(jié)點(diǎn)2是節(jié)點(diǎn)1的鄰近點(diǎn)；A(1,8)=0，表示節(jié)點(diǎn)9不是節(jié)點(diǎn)2的鄰近點(diǎn)。

因?yàn)辄c(diǎn)的索引從1開始，所以在鄰近點(diǎn)矩陣中，索引0代表節(jié)點(diǎn)1，依此類推，索引N-1代表節(jié)點(diǎn)N。

(2) 構(gòu)建N×N維的轉(zhuǎn)移概率矩陣P，該矩陣存放著由式(5)計(jì)算的每2個(gè)點(diǎn)之間的轉(zhuǎn)移概率。顯然A(i,j)=1，可得P(i,j)>0。轉(zhuǎn)移概率矩陣P的索引和鄰近點(diǎn)矩陣的索引類似。

步驟2 初始化每個(gè)螢火蟲個(gè)體，使得每個(gè)螢火蟲代表一條從起點(diǎn)到目標(biāo)點(diǎn)的可行路徑。

以螢火蟲i為例，初始化過程：設(shè)起點(diǎn)xi1=1，通過鄰近點(diǎn)矩陣和轉(zhuǎn)移概率矩陣，采用輪盤賭法計(jì)算搜索得到下一個(gè)點(diǎn)xi2(因?yàn)檩啽P賭法具有隨機(jī)性，即可以保證每個(gè)螢火蟲選到的點(diǎn)不全相同)。將當(dāng)前點(diǎn)設(shè)為xi2，修改轉(zhuǎn)移概率矩陣P，即只要滿足A(l,q)=xi1，則令P(l,q)=0，l,q∈{1,2,…,N}。這樣可以避免一條路徑中出現(xiàn)重復(fù)的點(diǎn)。終止的條件：在輪盤賭法計(jì)算次數(shù)小于N的情況下，若搜索到終點(diǎn)，則初始化螢火蟲i完成，此時(shí)螢火蟲i代表一條從起點(diǎn)到終點(diǎn)的有效路徑。若不滿足終止條件，則重新開始初始化該螢火蟲。

采用上面的方法初始化所有螢火蟲，即可得到M條有效路徑(包含重復(fù)的)。

步驟3 計(jì)算各個(gè)螢火蟲的目標(biāo)值，并將目標(biāo)值的倒數(shù)作為各自的最大熒光亮度I0。

對于求解最短路徑的問題，目標(biāo)值可定義為螢火蟲所代表路徑的權(quán)重，顯然，目標(biāo)值越小，代表的路徑越短。由于螢火蟲朝著亮度更大的螢火蟲移動(dòng)，所以，本算法將路徑權(quán)重和的倒數(shù)作為螢火蟲各自的最大熒光亮度，即螢火蟲代表路徑越短，則它的最大熒光亮度越大。

步驟4 對每個(gè)螢火蟲的有效路徑進(jìn)行編碼，再由式(1)和式(2)計(jì)算螢火蟲兩兩之間的相對熒光亮度和吸引度。其中，rij可由式(6)計(jì)算得出。

步驟6 為了避免計(jì)算結(jié)果陷入局部最優(yōu)，以一定的概率Pr對每個(gè)螢火蟲進(jìn)行擾動(dòng)。

步驟7 更新螢火蟲的狀態(tài)。

對于螢火蟲i，比較它在移動(dòng)前后及擾動(dòng)后產(chǎn)生的r條路徑權(quán)重大小，將最優(yōu)的路徑作為該螢火蟲的路徑，并更新狀態(tài)。比較更新后所有螢火蟲的狀態(tài)，將最優(yōu)路徑保存為當(dāng)前全局最優(yōu)。

步驟8 判斷終止條件。

如果達(dá)到最大迭代次數(shù)，或者進(jìn)行若干次迭代后，全局最優(yōu)結(jié)果保持不變，則結(jié)束計(jì)算，否則，跳到步驟3。

步驟9 輸出最優(yōu)結(jié)果，即避災(zāi)路線的最短路徑。

離散螢火蟲算法流程如圖2所示。

圖2 離散螢火蟲算法流程

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)1

以圖1的無向圖網(wǎng)絡(luò)為例，通過實(shí)驗(yàn)1來驗(yàn)證離散螢火蟲算法的有效性，并與Dijkstra算法進(jìn)行對比。

3.1.1 參數(shù)的選擇

根據(jù)圖1及離散螢火蟲算法的特點(diǎn)，參數(shù)設(shè)置如下：離散點(diǎn)個(gè)數(shù)N=20，螢火蟲數(shù)目M=50，替換長度數(shù)χ=2，擾動(dòng)概率Pr=0.4，迭代總次數(shù)T=50，光吸收系數(shù)γ=1.0。

3.1.2 結(jié)果分析

經(jīng)過多次實(shí)驗(yàn)，算法能夠用較少的迭代次數(shù)得到最優(yōu)路徑，實(shí)驗(yàn)結(jié)果如圖3所示。從圖3可以看出，從節(jié)點(diǎn)1到節(jié)點(diǎn)20的最短逃生路徑為1→3→8→10→17→20，該最短路徑的權(quán)重和為14。與Dijkstra算法相比，雖然2種算法都可以求出從節(jié)點(diǎn)1到節(jié)點(diǎn)20之間的最短路徑，且所得到的最短路徑相同。但是，使用Dijkstra算法搜索時(shí)具有盲目性，而且隨著離散點(diǎn)數(shù)的增加，搜索效率會(huì)迅速下降。離散螢火蟲算法作為一種智能優(yōu)化算法，在搜索時(shí)采用概率搜索的策略，可以達(dá)到快速向最優(yōu)路徑靠近的效果。

圖3 圖1的實(shí)驗(yàn)結(jié)果

3.2 實(shí)驗(yàn)2

為了說明離散螢火蟲算法具有快速收斂性，這里以參考文獻(xiàn)[9]中的無向圖(圖4)為例，通過實(shí)驗(yàn)計(jì)算，并與基本人工魚群算法(AFSA)及改進(jìn)人工魚群算法(Im-AFSA)進(jìn)行對比，比較這3種算法的收斂速度。

圖4 參考文獻(xiàn)[9]中的無向圖網(wǎng)絡(luò)

3.2.1 參數(shù)的選擇

基本人工魚群算法和改進(jìn)人工魚群算法的參數(shù)設(shè)置如下[9]：人工魚群個(gè)數(shù)M=20，感知距離V=0.618，試探次數(shù)tN=20，擁擠度因子deta=6，最大閾值M_N=10，最大迭代次數(shù)T=50。離散螢火蟲算法的參數(shù)設(shè)置如下：螢火蟲數(shù)目M=20，替換長度數(shù)χ=2，擾動(dòng)概率Pr=0.4，光吸收系數(shù)γ=1.0，迭代總次數(shù)T=50。

3.2.2 結(jié)果分析

3種算法的收斂曲線對比如圖5所示，從圖5可以看出，離散螢火蟲算法具有更快的收斂速度。與其他人工智能算法相比，運(yùn)用本文提到的編碼、解碼及轉(zhuǎn)移概率初始化的方法，可以排除無效路徑并省去許多不必要的計(jì)算。另外，以一定的概率對螢火蟲的狀態(tài)進(jìn)行擾動(dòng)，不僅可以使計(jì)算的結(jié)果跳出局部最優(yōu)，而且也解決了對所有螢火蟲進(jìn)行擾動(dòng)帶來的計(jì)算量大的問題。

圖5 3種算法的收斂曲線對比

4 結(jié)語

針對煤礦井下尋求最短逃生路徑問題，提出了離散螢火蟲算法。仿真結(jié)果表明，該算法能夠通過較少的迭代次數(shù)得到最優(yōu)的解，具有較強(qiáng)的收斂性。該算法也可以用在車輛導(dǎo)航系統(tǒng)中，具有較強(qiáng)的實(shí)用性。

[1] 趙作鵬,宋國娟,宗元元,等.基于D-K算法的煤礦水災(zāi)多最優(yōu)路徑研究[J].煤炭學(xué)報(bào),2015,40(2):397-402.

[2] 李翠平,曹志國,李仲學(xué),等.地下礦火災(zāi)煙流蔓延的三維仿真構(gòu)模技術(shù)[J].煤炭學(xué)報(bào),2013,38(2):257-263.

[3] 徐雪松,楊勝杰,陳榮元.復(fù)雜環(huán)境移動(dòng)群機(jī)器人最優(yōu)路徑規(guī)劃方法[J].電子測量與儀器學(xué)報(bào),2016,30(2):274-282.

[4] 趙建偉,王洪燕,唐兵,等.基于移動(dòng)機(jī)器人的GPS軌跡生成及定位研究[J].工礦自動(dòng)化,2016,42(1):17-19.

[5] MUROTA K,SHIOURA A.Dijkstra's algorithm and L-concave function maximization[J].Mathematical Programming,2013,145(1):163-177.

[7] 郎茂祥.用單親遺傳算法求解配送車輛調(diào)度問題的研究[J].交通與計(jì)算機(jī),2006,24(1):119-122.

[8] 賈新果.基于蟻群算法的開采沉陷計(jì)算參數(shù)反演[J].工礦自動(dòng)化,2015,41(6):10-13.

[9] 孫茜茜,陸南.求解最短路徑問題的改進(jìn)人工魚群算法研究[J].信息技術(shù),2014,38(9):182-185.

[10] YANG Xinshe.Multiobjective firefly algorithm for continuous optimization[J].Engineering with Computers,2012,29(2):175-184.

[11] NASIRI B,MEYBODI M.Improved speciation-based firefly algorithm in dynamic and uncertain environments[J].Journal of Information Science and Engineering,2016, 32(3):661-676.

[12] XIAO Liye,SHAO Wei,LIANG Tulu,et al.A combined model based on multiple seasonal patterns and modified firefly algorithm for electrical load forecasting[J]. Applied Energy,2013,167:135-153.

[13] 吳虎勝,張風(fēng)鳴,李浩,等.求解TSP問題的離散狼群算法[J].控制與決策,2015,30(10):1861-1867.

A discrete firefly algorithm for solving the shortest escape path problem in underground coal mine

ZHANG Xueying, LI Zhiyong, LI Fenglian, CHEN Guijun

(College of Information Engineering, Taiyuan University of Technology, Jinzhong 030600, China)

A new discrete firefly algorithm was proposed to solve the shortest escape path problem in underground coal mine. Firstly, the firefly individual was initialized using transfer probability method. And then, a new efficient encoding and decoding method was proposed to redefine space distance, the maximum fluorescence intensity and fluorescence relative brightness of the firefly. So the firefly individual state can be expressed as an effective path from the starting point to the target point. In order to increase the diversity of solutions and to prevent the solutions falling into the local optimum, disturbed operation was carried out to the represented path of the firefly by a certain probability. After several iterations, the shortest path of the solution can be obtained. The experimental results show that the proposed algorithm can converge to the optimal solution with the smaller population size and less iterations than the other algorithms, and has strong convergence and flexibility, which can be used to solve any problem of the shortest path.

avoid disaster in underground coal mine; the shortest path; discrete firefly algorithm; coding; decoding; disturbance

2016-06-30；

2016-09-01；責(zé)任編輯：張強(qiáng)。

山西省科技重大專項(xiàng)項(xiàng)目(20121101004)；山西省國際科技合作項(xiàng)目(2015081007)；山西省科技攻關(guān)資助項(xiàng)目(20130321004-01)。

張雪英(1964-)，女，河北行唐人，教授，博士，主要從事煤礦安全、嵌入式系統(tǒng)及應(yīng)用、煤礦物聯(lián)網(wǎng)方面的研究工作，E-mail:tyzhangxy@163.com。

1671-251X(2016)12-0030-06

10.13272/j.issn.1671-251x.2016.12.007

TD773

A

時(shí)間：2016-12-01 10:26

http://www.cnki.net/kcms/detail/32.1627.TP.20161201.1026.007.html

張雪英，李智勇，李鳳蓮，等.用于求解井下最短逃生路徑問題的離散螢火蟲算法[J].工礦自動(dòng)化，2016,42(12)：30-35.