基于改进萤火虫算法的矿井水害避灾路径规划

2021-06-18朱希安王占刚刘德民

中国矿业 2021年6期

王鹏，朱希安，王占刚，刘德民

(1.北京信息科技大学信息与通信工程学院，北京 100101；2.华北科技学院安全工程学院，北京 101601)

在煤矿生产过程中，从业人员在巷道中随时面临着矿井突水等自然灾害的威胁。当突水灾害发生时，如何使受困人员尽快摆脱险境，是一个值得考虑的问题。地下井巷道交错复杂，从事故发生地到安全区域通常会有很多条路径，在诸多路径中选择一条最优路径符合从业人员的安全利益[1-2]。

有学者对矿井突水逃生路径规划问题进行了研究。苑亚南等[3]通过综合考虑突水点处流体力学特性、巷道基本信息，提出了基于改进的D-K路径搜索算法的多路径逃生模型；蔡明杰等[4]通过重新设计遗传算子，引入新的交叉、变异算子，较好地提高了遗传算法在规划路径时的收敛速度和可靠性；刘梦杰等[5]通过将传统A*算法单向搜索方式改为双向搜索并改进评估函数的定义，使得每一步搜索都根据评估函数朝着某个方向搜索。随着计算机运算能力的加强，蚁群算法等元启发式算法逐渐成为路径规划的主流算法。但是，上述算法都存在以下缺点中的一个或多个：易陷入局部最优、收敛效果不佳、无效计算过多等。鉴于上述背景，本文通过引入巷道当量长度以调整萤火虫的初始化方式，改变萤火虫的间距、最大亮度和相对亮度等要素的定义，结合王家岭矿实例实现对避灾路径的最优规划。

1 巷道当量长度

考虑到受困人员的身体状况以及每条巷道的客观干扰因素，诸如风速风向、巷道坡度、局部障碍物类型、有毒有害气体浓度等都会对逃生巷道的安全性产生影响，所以不能简单地求解线路的最短距离并以此充当最优路径。因此，本文将当量长度的概念引入避灾路径的规划中，通过综合评价巷道中对逃生安全有重要影响的因素，计算巷道的当量长度[6]，并将该值作为巷道网络结构的权重。

1.1 影响系数的定义

通过对巷道实际情况的研判，本文重点的干扰因素为风速(含风向)、巷道坡度、局部障碍物类型、巷道类型，对应的影响系数[7]分别为δ1、δ2、δ3、δ4，干扰因素的影响系数见表1。设不受某项因素影响时通过巷道Rij的速度为V0，受某项因素影响时通过巷道Rij的速度为V，则影响系数的表达式为式(1)。

表1 巷道干扰因素及影响系数Table 1 Disturbance factors and influence coefficients of roadway

(1)

1.2 巷道当量长度的求解

将各巷道影响系数加权到对应的巷道实际长度即可得巷道当量长度。设定节点i和节点j(i，j须为可直接相连的两点)之间的巷道实际长度为lij，δ1，δ2，δ3，…，δn为该巷道干扰因素的影响系数，巷道Rij的当量长度wij定义见式(2)。

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

(2)

若有一条从突水点至安全点的路径U，包含p段巷道，第q条巷道的当量长度用wq表示，则路径U的当量长度WU可表示为式(3)。

(3)

当量长度表示通过该逃生路径的难易程度，路径的当量长度值越大，代表该路径越难以通过；路径的当量长度值越小，代表该路径越容易通过。可将改进后的萤火虫算法中的目标函数用当量长度表示，巷道当量长度越小则目标函数越优，反之则越差。

2 标准萤火虫算法

2.1 标准萤火虫算法基本原理

萤火虫算法(firefly algorithm，FA)是一种基于萤火虫的发光模式和运动模式的元启发式算法。其原理是萤火虫随机地分布在特定的场域中，亮度较小的萤火虫会飞向亮度较大的萤火虫，随着移动的过程在亮度较大的萤火虫处聚集。萤火虫算法是通过其运动、更新位置的过程来探寻最优解的过程[8]。

萤火虫相对亮度的表达式见式(4)。

(4)

式中：I0为萤火虫距离为零时的亮度，即最大亮度；γ为光吸收系数；Rij为萤火虫i和j的间距。

萤火虫吸引度表达式见式(5)。

(5)

式中：β0为两只萤火虫距离为零时的吸引力大小，即最大吸引力；γ、Rij含义同式(4)。

任意两只萤火虫的间距通过笛卡尔距离定义，表达式见式(6)。

(6)

式中：xi、xj为萤火虫i、j在场域中的位置；d为解空间的总维度。

萤火虫移动后位置的表达式见式(7)。

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

(7)

式中：xi(t)、xj(t)为萤火虫i、j在第t次迭代所处位置；α为随机化参数，α∈[0,1]；εi为搜索精度，εi∈[-0.5,0.5]。

2.2 标准萤火虫算法描述

在寻优问题中，目标函数表示为萤火虫的亮度，亮度越大代表该萤火虫所处的空间解越好。萤火虫算法首先设定一些基本参数，通过循环迭代萤火虫的亮度并更新萤火虫的亮度和位置，直至满足终止条件[9]。标准萤火虫算法步骤如下所述。①设定基本参数：β0、γ、α、N(萤火虫数量)、T(最大迭代次数)；②随机初始化萤火虫位置，根据目标函数计算其亮度；③计算萤火虫的亮度和吸引度，确定萤火虫的移动方向；④确定萤火虫更新移动后的位置，对其亮度进行重新计算；⑤若达到最大迭代次数则结束算法，否则返回到第②步继续搜索；⑥输出结果，算法程序结束。标准萤火虫算法流程图如图1所示。

图1 标准萤火虫算法流程图Fig.1 Flow chart of standard firefly algorithm

标准萤火虫算法虽然具有参数少、操作性强等优点，但也具有易陷入局部最优的缺点。萤火虫都是飞向比自己亮度更大的萤火虫，但当萤火虫个体全都集中于场域中的某一个或某几个位置时，其搜索能力显著下降。本文通过改进萤火虫基本要素的定义及搜索策略，将萤火虫算法应用于矿井突水逃生路径规划的研究。

3 改进的萤火虫算法

3.1 改进的萤火虫算法描述

设定在某场域中有N只萤火虫，M个离散点(巷道节点)，针对矿井逃生路径，令每只萤火虫代表一条完整的从突水点至安全点的路径。首先，对萤火虫进行初始化可得N条逃生路径，计算每条路径的当量长度，保留当量长度最小的路径，定义其为全局最优路径。此处，将萤火虫最大亮度定义为该条路径当量长度的倒数。其次，比较萤火虫的最大亮度值和种群最大亮度平均值，舍弃最大亮度值低于种群平均亮度值的路径，保留大于等于种群平均亮度值的路径，对舍弃的路径重新初始化。最后，计算萤火虫之间的相对亮度，以确定萤火虫的移动方向并进行移动。将移动后的路径当量长度与当前全局最优路径对比，若移动后有路径的当量长度小于当前全局最优路径，则保留该路径的当量长度并将其记为全局最优路径；反之则不变。通过数次迭代即可得到全局最优路径，该路径可满足矿井水害避灾路径规划的需求。

3.2 改进的萤火虫算法具体步骤

1) 初始化萤火虫。如图2所示，设定节点a0有n个与之直接相连的节点序列a={a1，a2，a3，…，an}，本文通过轮盘赌结合路径权重的方法初始化萤火虫。若ap为节点序列a中的一点，则节点a0选择ap为下一节点的概率计算见式(8)。

图2 萤火虫初始化的选择概率Fig.2 Selection probability of firefly initialization

(8)

式中：k∈{1,2，…，n}；w0p为节点a0与ap相连路径的权重；w0k定义同理。若两节点不相连，则两节点互相选择的概率均为0。

为选择一条从突水点至安全点的有效路径，必须保证已选择的点不会再被选择，故建立相邻点矩阵和移动选择矩阵。相邻点矩阵通过设定任意两点的关系为1或0来判断是否直接相连，若节点a0和a1直接相连，则表示为Con(a0，a1)=1；若节点a0和b0不直接相连，则表示为Con(a0，b0)=0。移动选择矩阵中的值表示为任意一点选择另一直接相连点的概率，若节点a0选择到了a1为其下一节点，则Con(a0，a1)=1，并修改a1对a0的移动概率为P(a0，a1)=0，可保证节点a1不会再选择到节点a0。以突水点为起点进行初始化直至选择到安全点为止，即可得到一条完整路径。

2) 舍弃劣质萤火虫路径。通过求得初始化后萤火虫路径的最大亮度平均值，逐个将萤火虫的最大亮度值与最大亮度平均值进行比较，当某萤火虫亮度值大于或等于亮度平均值时，则保留该条路径；反之，则不予保留。并返回步骤1)重新初始化舍弃掉的萤火虫路径。

3) 最大亮度。由于萤火虫都是向比自己亮度大的萤火虫移动，所以将萤火虫的最大亮度定义为目标函数的倒数，即萤火虫将通过迭代移动至目标函数(当量长度值)比自己小的萤火虫个体。

4) 相对亮度和吸引度。由于萤火虫序列中节点数可能不一致，所以对萤火虫的节点序列进行补0操作。设某萤火虫i包含n个节点，记为Xi={xi1，xi2，…，xin}；某萤火虫j包含m个节点，记为Xj={xj1，xj2，…，xjm}，在萤火虫i序列的终点xin前补(M-n)个0，在萤火虫j序列的终点xjn前补(M-m)个0，使每个序列中节点个数均为节点总数。萤火虫i到萤火虫j的距离表示为式(9)。

(9)

式中，xik、xjk为萤火虫i、j的第k个节点。

5) 移动。从两条路径中选择任意一个公共点，将公共点后的一段路径进行替换以完成移动。如萤火虫i的路径序列为Xi={xi1，xi2，…，xiM}；某萤火虫j的路径序列为Xj={xj1，xj2，…，xjM}，选择一公共点(不考虑终点)xia=xjb，若萤火虫i移动至j，则将xjb后长度小于等于μ的一段路径取代xia后长度小于等于μ的一段路径，如果替换后萤火虫i仍为从起点到终点的完整路径，则结束移动；反之，则随机另找一公共点进行上述操作，直至找到一条可行路线。若没有找到可行路线，则重新移动。移动后对萤火虫的最大亮度、相对亮度、吸引度更新，若更新后的值小于全局最优解的值，则将全局最优解替换为更新后的值。

6) 终止迭代。若达到最大迭代次数，则终止循环，输出全局最优解。反之，则返回步骤2)继续循环。改进的萤火虫算法流程图如图3所示。

图3 改进的萤火虫算法流程图Fig.3 Flow chart of improved firefly algorithm

4 改进的萤火虫算法在王家岭矿的实现

本文选取王家岭部分巷道构建了如图4所示的无向网络结构图，图中的圆圈表示巷道节点，线段表示巷道，图中未等比例构建。统计的巷道干扰因素、影响系数及巷道当量长度见表2。通过使用改进的萤火虫算法和A*算法规划逃生路径，比较和分析两个算法规划的路径结果。

图4 巷道简化架构图Fig.4 Simplified architecture diagram of roadway

表2 王家岭局部巷道实际长度及干扰因素信息Table 2 Information on actual length and interference factors of local roadways in Wangjialing

为验证算法在路径规划中的可行性，本文基于MATLAB环境进行仿真。因算法采用轮盘赌的方式进行节点选择，路径规划结果会受到随机因素的影响，为了减小随机因素所带来的差异，本文设置多组突水点和安全点以提高实验的可靠性。改进的萤火虫算法参数取值为：巷道节点数M=16，萤火虫个数N=40，最大迭代次数T=40，光吸收系数γ=1.0，替换长度数μ=600。改进后的萤火虫算法和A*算法路径规划的测试结果见表3和表4。

通过分析表3和表4的实验结果可知，改进的萤火虫算法所规划路径的实际长度和当量长度比A*算法求得的长度都短，表明改进的萤火虫算法更易找到最优解。因为本文考虑了巷道中的干扰因素，故本算法规划的逃生路径能更好地满足受困人员的安全利益，在矿井事故应急救援应用中具有较大的价值。