图1 煤矿巷道无向图网络
张雪英， 李智勇， 李凤莲， 陈桂军
(太原理工大学 信息工程学院， 山西 晋中 030600)
摘要：针对煤矿井下避灾路线最短路径求解问题，提出了一种新的离散萤火虫算法。该算法通过采用转移概率方法初始化萤火虫个体，并提出一种新的有效编码和解码方式，重新定义萤火虫的空间距离、最大荧光亮度和相对荧光亮度等，使得萤火虫个体的状态可表示为一条从起点到目标点的有效路径。为增加解的多样性及防止计算结果陷入局部最优解，以一定概率对萤火虫代表的路径执行扰动操作，经过多次迭代计算后，可得到所要求解的最短路径。实验结果表明，该算法在种群规模较小、迭代次数较少的情况下可以收敛到最优解，具有较强的收敛性和灵活性，可用于求解任何实际的最短路径问题。
关键词：井下避灾； 最短路径； 离散萤火虫算法； 编码； 解码； 扰动
求解最短路径是煤矿井下避灾[1-2]和智能车辆导航系统[3-4]等领域一个亟需解决的问题。在求解最短路径的算法中，学界目前高度认可的算法有经典的Dijkstra算法[5-6]和Floyd算法，但这2种算法在搜索路径时具有盲目性，且时间复杂度是它们的瓶颈。随着群智能优化算法的深入研究，一些新的算法不断被提出，包括遗传算法[7]、蚁群算法[8]及人工鱼群算法[9]等。虽然遗传算法和蚁群算法都能够求解结构较为复杂且维数较高情况下的最短路径问题，但是它们也存在搜索效率低、计算结果都容易陷入局部最优等缺点；人工鱼群算法虽然可以在一定程度上避免陷入局部最优，但是该算法收敛速度较慢，且随着维数的增加，算法也容易陷入局部最优。
在自然界的昆虫类中，萤火虫是通过发出一种荧光来求偶或觅食的。萤火虫能够发出荧光的原理：萤火虫具有发光的细胞，细胞中含有化学物质荧光素，这种化学物质通过反应可以发出亮光。萤火虫发出的亮光越大，则它对别的个体的吸引力越大，别的地方的萤火虫开始向这个地方靠近，慢慢地，原先分离的大部分萤火虫个体都聚集到了一个(或多个)位置上。萤火虫算法(Firefly Algorithm，FA)正是根据这种群体行为的启发演变而来的[10]，通过模拟自然界中萤火虫发出荧光来吸引伴侣和觅食的行为，最终实现了目标函数解的寻优过程。
为了求解井下最短路径问题，笔者提出了一种新的离散萤火虫算法(Discrete Firefly Algorithm，DFA)。该算法采用转移概率初始化的方法初始化萤火虫个体，定义了萤火虫的最大荧光亮度和相对荧光亮度等，并给出了萤火虫个体间距离的计算公式。为加快算法的收敛速度和跳出局部最优，对萤火虫的扰动行为重新做出了定义。最后，通过VC平台实现该算法，并对实际煤矿井下拓扑图进行仿真实验，得出了准确的计算结果。仿真实验结果表明，该算法具有收敛速度快、能跳出局部最优的优点，可用于求解任何实际的最短路径问题。
1.1 算法的具体原理
萤火虫算法与其他群智能算法相似，采用种群多点并行全局随机搜索的策略[11-12]。萤火虫种群中每一个萤火虫个体本身都携带一定数量的荧光素，且荧光素是可以更新的。萤火虫的移动方向是朝着它感知决策半径范围内相对荧光亮度最大的萤火虫靠近；对萤火虫的位置进行更改后，重新计算它们的最大荧光亮度和相对荧光亮度，然后重复上述移动过程，最终实现所有萤火虫聚集到亮度最大的一个(或几个)萤火虫所处的位置上。通过亮度和吸引度等的不断更新，从而实现目标优化。
1.2 算法参数和公式
相对荧光亮度定义为
I=I0exp(-γrij)
(1)
式中：I0为萤火虫个体的最大萤光亮度；γ为光吸收系数，通常设为大于零的常数，该参数用来描述荧光受距离及周围环境的影响而发生动态变化；rij为萤火虫个体i与萤火虫个体j之间的距离。
相对荧光亮度大小体现了萤火虫个体所在位置(即它的状态)的优劣并决定其移动方向。
吸引度定义为
β=β0exp(-γrij)
(2)
式中β0为最大吸引度，吸引度的大小决定了萤火虫个体移动的距离。
假设萤火虫j向萤火虫i移动，则萤火虫j移动位置计算公式为
xj=xj+β(xi-xj)+α(rand-1/2)
(3)
式中：xj和xi分别为萤火虫j和萤火虫i所处的空间位置；α为步长因子，取值范围为0～1；rand为随机数。
2.1 煤矿巷道网拓扑结构
煤矿巷道网是一个复杂的网络系统。巷道网有巷道路线、巷道交叉口等物理属性，将其抽象为带权无向图，用节点来表示网中的交叉路口，连接两节点之间的边表示为路线，并将路线的长度、通行时间、路况等属性表示为该边的权值。图1是一个抽象的巷道无向图网络，其中圆圈表示巷道的节点，节点与节点直接相连表示此路径可行，且数值的大小可表示从一个节点到另一个节点所用的时间或者节点间路径的长度等。离散萤火虫算法的目的是求取从其中某个节点到另一个不直接相连的节点的最短路径(如从节点1到节点20)。
图1 煤矿巷道无向图网络
2.2 相关概念
在N×M的解空间中(N为离散点总个数，M为萤火虫数目)规定：萤火虫i编码前后的位置定义为Xi={xi1,xi2,…,xim}和
其中xil,xiq,l,q∈{1,2,…,N}。w(l,q)表示节点l与q之间路径的权值，且节点l与q必须为邻近点，否则w(l,q)=∞。
路径的权重w(p)即构成该路径p的所有边的权重之和：
(4)
直接相连的2个节点互为邻近点。如图1中节点2和节点6互为邻近点。
转移概率：若节点j邻近点有j1,j2,…,jl，则转移概率可表示为
(5)
式中u∈{1,2,…,l}。
在j,j1,…,jl中，若2个点不为邻近点，则转移概率为0。
2.3 编码和解码
本文采用一种新的整数编码方式。为了方便起见，规定节点0为虚拟节点，即不存在的节点。节点0具有如下特点：
(1) 节点0到所有节点的权值为0，包括到自身，即w(l,q)=0，l=0或者q=0。
(2) 节点0到其他所有节点的转移概率为0，理论上不存在从0节点转移到其他节点，同理，也不能有其他节点转移到节点0，Pi(0)=0或者P0(i)=0。
以图1为例，求取从节点1到节点20的最短路径，若有一个路径p为1→4→15→19→20，即编码前路径为X(p)={1,4,15,19,20}，则编码后的路径X′(p)={1,4,15,19,0,…,0,20}，起点和终点固定，路径的有效位数不足时，补0。由于X′(p)为N维，且起始位和结束位固定，所以，在计算中也可以等效为{4,15,19,0,…,0}，即N-2维。
解码为编码的逆过程，即从N-2维还原为N维。
萤火虫之间的距离：萤火虫i编码后的路径为
萤火虫j编码后的路径为
则萤火虫i和j之间的距离为
(6)
式中：i,j∈{1,2,…,M}；xik为萤火虫i编码后路径的第k个点；xjk为萤火虫j编码后路径的第k个点。
路径的有效点、有效路径和有效点个数：路径p中除了虚拟点0之外的点均为有效点。例如X′(p)={1,4,15,19,0,…,0,20}中，有效点为1,4,15,19,20，有效路径即为1→4→15→19→20。显然，有效点个数为除了虚拟节点0之外，其他点的个数总和，即有效点个数为5。
2条路径中的公共点：萤火虫i编码的路径为萤火虫j编码的路径为若xiu=xjq，则称xiu(或xjq)为路径中的公共点。
2.4 算法的具体原理及实施步骤
离散萤火虫算法的具体原理：为求解煤矿井下避灾路线最短路径，假设萤火虫数目为M，令每个萤火虫个体代表一条从起点到终点的有效路径。首先采用转移概率的初始化方法[13]初始化所有萤火虫，即可得到M条有效路径，从中选择出目标函数(路径权重)最优的路径，保存为全局最短路径，并把每个萤火虫的有效路径权重倒数作为它们各自的最大荧光亮度值。其次，通过计算两两萤火虫之间的相对亮度，确定每个萤火虫移动的具体方向，即萤火虫个体都是朝着相对亮度最大的那个萤火虫个体靠近。将移动后产生的新路径与此时的全局最短路径进行比较，如果新产生的路径中有比全局最短路径权重和更小的，则用该路径替换掉全局最短路径，否则不予替换。然后，为增加解的多样性并防止计算结果陷入局部最优，以一定的概率对每个萤火虫编码后的路径进行随机扰动。把扰动后产生的新路径与此时全局最短路径的权重和进行比较，若新产生的路径中存在比全局最短路径权重和更小的路径，则用它替换全局最短路径，否则不予替换。最后，重新计算每个萤火虫的最大荧光亮度，一定迭代次数计算后得到的最终结果，即为所要求解的避灾路线最短路径。
离散萤火虫算法实施步骤：
步骤1 构建邻近点矩阵和概率转移矩阵。
(1) 构建N×N维的邻近点矩阵A，该矩阵存放的值为1或0，1表示对应的点为邻近点，0表示对应的点不为邻近点。如A(0,1)=1，表示节点2是节点1的邻近点；A(1,8)=0，表示节点9不是节点2的邻近点。
因为点的索引从1开始，所以在邻近点矩阵中，索引0代表节点1，依此类推，索引N-1代表节点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}。这样可以避免一条路径中出现重复的点。终止的条件：在轮盘赌法计算次数小于N的情况下，若搜索到终点，则初始化萤火虫i完成，此时萤火虫i代表一条从起点到终点的有效路径。若不满足终止条件，则重新开始初始化该萤火虫。
采用上面的方法初始化所有萤火虫，即可得到M条有效路径(包含重复的)。
步骤3 计算各个萤火虫的目标值，并将目标值的倒数作为各自的最大荧光亮度I0。
对于求解最短路径的问题，目标值可定义为萤火虫所代表路径的权重，显然，目标值越小，代表的路径越短。由于萤火虫朝着亮度更大的萤火虫移动，所以，本算法将路径权重和的倒数作为萤火虫各自的最大荧光亮度，即萤火虫代表路径越短，则它的最大荧光亮度越大。
步骤4 对每个萤火虫的有效路径进行编码，再由式(1)和式(2)计算萤火虫两两之间的相对荧光亮度和吸引度。其中，rij可由式(6)计算得出。
步骤5 根据萤火虫之间的相对亮度确定每个萤火虫的移动方向，即萤火虫i朝着相对亮度最大的萤火虫j移动。萤火虫i向萤火虫j移动，即用萤火虫j编码后路径中的一段代替萤火虫i编码后路径相同长度的一段。具体地，萤火虫i的路径编码为萤火虫j所代表的路径编码为从这2条路径的公共点中随机选取一点xiu=xjq(终点除外)，用xjq之后χ长度的一段替换xiu之后的χ长度的一段。若替换后路径
不是一条有效路径，则从xi(u+x-1)点开始，采用轮盘赌法计算搜索下一个点，依此类推，直到找到一条有效路径。否则，重新执行移动操作。
步骤6 为了避免计算结果陷入局部最优，以一定的概率Pr对每个萤火虫进行扰动。
若萤火虫i被选中进行扰动，则计算路径中有效点(终点除外)的个数，并用G来表示。扰动就是将i代表的路径
进行r次如下操作：随机选取从0到G的值作为索引u，将xiu作为起始点，采用轮盘赌法计算下一个离散点，并用该点替换xi(u+1)。若此时为有效路径，则结束该次操作。否则，将xi(u+1)作为当前点，继续采用轮盘赌法计算下一个不重复的离散点，将计算得到的点替换为xi(u+2)。重新判断该路径是否有效，若有效，则结束该次操作，否则继续上述操作。结束条件为某次替换后路径有效，或者搜索到终点，且最后一次替换的点xik满足k≤N。
步骤7 更新萤火虫的状态。
对于萤火虫i，比较它在移动前后及扰动后产生的r条路径权重大小，将最优的路径作为该萤火虫的路径，并更新状态。比较更新后所有萤火虫的状态，将最优路径保存为当前全局最优。
步骤8 判断终止条件。
如果达到最大迭代次数，或者进行若干次迭代后，全局最优结果保持不变，则结束计算，否则，跳到步骤3。
步骤9 输出最优结果，即避灾路线的最短路径。
离散萤火虫算法流程如图2所示。
图2 离散萤火虫算法流程
3.1 实验1
以图1的无向图网络为例，通过实验1来验证离散萤火虫算法的有效性，并与Dijkstra算法进行对比。
3.1.1 参数的选择
根据图1及离散萤火虫算法的特点，参数设置如下：离散点个数N=20，萤火虫数目M=50，替换长度数χ=2，扰动概率Pr=0.4，迭代总次数T=50，光吸收系数γ=1.0。
3.1.2 结果分析
经过多次实验，算法能够用较少的迭代次数得到最优路径，实验结果如图3所示。从图3可以看出，从节点1到节点20的最短逃生路径为1→3→8→10→17→20，该最短路径的权重和为14。与Dijkstra算法相比，虽然2种算法都可以求出从节点1到节点20之间的最短路径，且所得到的最短路径相同。但是，使用Dijkstra算法搜索时具有盲目性，而且随着离散点数的增加，搜索效率会迅速下降。离散萤火虫算法作为一种智能优化算法，在搜索时采用概率搜索的策略，可以达到快速向最优路径靠近的效果。
图3 图1的实验结果
3.2 实验2
为了说明离散萤火虫算法具有快速收敛性，这里以参考文献[9]中的无向图(图4)为例，通过实验计算，并与基本人工鱼群算法(AFSA)及改进人工鱼群算法(Im-AFSA)进行对比，比较这3种算法的收敛速度。
图4 参考文献[9]中的无向图网络
3.2.1 参数的选择
基本人工鱼群算法和改进人工鱼群算法的参数设置如下[9]：人工鱼群个数M=20，感知距离V=0.618，试探次数tN=20，拥挤度因子deta=6，最大阈值M_N=10，最大迭代次数T=50。离散萤火虫算法的参数设置如下：萤火虫数目M=20，替换长度数χ=2，扰动概率Pr=0.4，光吸收系数γ=1.0，迭代总次数T=50。
3.2.2 结果分析
3种算法的收敛曲线对比如图5所示，从图5可以看出，离散萤火虫算法具有更快的收敛速度。与其他人工智能算法相比，运用本文提到的编码、解码及转移概率初始化的方法，可以排除无效路径并省去许多不必要的计算。另外，以一定的概率对萤火虫的状态进行扰动，不仅可以使计算的结果跳出局部最优，而且也解决了对所有萤火虫进行扰动带来的计算量大的问题。
图5 3种算法的收敛曲线对比
针对煤矿井下寻求最短逃生路径问题，提出了离散萤火虫算法。仿真结果表明，该算法能够通过较少的迭代次数得到最优的解，具有较强的收敛性。该算法也可以用在车辆导航系统中，具有较强的实用性。
参考文献：
[1] 赵作鹏,宋国娟,宗元元,等.基于D-K算法的煤矿水灾多最优路径研究[J].煤炭学报,2015,40(2):397-402.
[2] 李翠平,曹志国,李仲学,等.地下矿火灾烟流蔓延的三维仿真构模技术[J].煤炭学报,2013,38(2):257-263.
[3] 徐雪松,杨胜杰,陈荣元.复杂环境移动群机器人最优路径规划方法[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.
[6] SEDE
O -NODA A,RAITH A.A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem[J].Computers & Operations Research,2015,57:83-94.
[7] 郎茂祥.用单亲遗传算法求解配送车辆调度问题的研究[J].交通与计算机,2006,24(1):119-122.
[8] 贾新果.基于蚁群算法的开采沉陷计算参数反演[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)
Abstract：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.
Key words：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-)，女，河北行唐人，教授，博士，主要从事煤矿安全、嵌入式系统及应用、煤矿物联网方面的研究工作，E-mail:tyzhangxy@163.com。
文章编号：1671-251X(2016)12-0030-06
DOI：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.