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

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

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

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

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

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

井下避災； 最短路徑； 離散螢火蟲算法； 編碼； 解碼； 擾動

0 引言

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

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

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

1 螢火蟲算法

1.1 算法的具體原理

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

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

相對熒光亮度定義為

I=I0exp(-γrij)

(1)

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

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

吸引度定義為

β=β0exp(-γrij)

(2)

式中β0為最大吸引度，吸引度的大小決定了螢火蟲個體移動的距離。

假設螢火蟲j向螢火蟲i移動，則螢火蟲j移動位置計算公式為

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

(3)

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

2 離散螢火蟲算法

2.1 煤礦巷道網(wǎng)拓撲結構

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

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

2.2 相關概念

路徑的權重w(p)即構成該路徑p的所有邊的權重之和：

(4)

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

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

(5)

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

在j,j1,…,jl中，若2個點不為鄰近點，則轉移概率為0。

2.3 編碼和解碼

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

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

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

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

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

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

(6)

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

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

2.4 算法的具體原理及實施步驟

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

步驟1 構建鄰近點矩陣和概率轉移矩陣。

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

因為點的索引從1開始，所以在鄰近點矩陣中，索引0代表節(jié)點1，依此類推，索引N-1代表節(jié)點N。

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

步驟2 初始化每個螢火蟲個體，使得每個螢火蟲代表一條從起點到目標點的可行路徑。

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

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

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

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

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

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

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

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

步驟8 判斷終止條件。

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

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

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

圖2 離散螢火蟲算法流程

3 仿真實驗及結果分析

3.1 實驗1

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

3.1.1 參數(shù)的選擇

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

3.1.2 結果分析

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

圖3 圖1的實驗結果

3.2 實驗2

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

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

3.2.1 參數(shù)的選擇

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

3.2.2 結果分析

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

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

4 結語

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

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

[2] 李翠平,曹志國,李仲學,等.地下礦火災煙流蔓延的三維仿真構模技術[J].煤炭學報,2013,38(2):257-263.

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

[4] 趙建偉,王洪燕,唐兵,等.基于移動機器人的GPS軌跡生成及定位研究[J].工礦自動化,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] 郎茂祥.用單親遺傳算法求解配送車輛調度問題的研究[J].交通與計算機,2006,24(1):119-122.

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

[9] 孫茜茜,陸南.求解最短路徑問題的改進人工魚群算法研究[J].信息技術,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] 吳虎勝,張風鳴,李浩,等.求解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；責任編輯：張強。

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

張雪英(1964-)，女，河北行唐人，教授，博士，主要從事煤礦安全、嵌入式系統(tǒ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

時間：2016-12-01 10:26

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

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