基于蚁群算法的井下救援路径优化方法

龚星宇1, 常心坦2, 贾澎涛1, 罗碧波3

(1.西安科技大学 计算机科学与技术学院, 陕西 西安 710054; 2.西安科技大学 能源学院,陕西 西安 710054; 3.陕西省科技资源统筹中心, 陕西 西安 710077)

摘要:针对火灾背景下煤矿应急救援路径的优化问题,提出了一种基于蚁群算法的井下救援路径优化方法;建立了井下救援路径选择影响因素的层次结构模型,各影响因素按重要程度由高到低排列为CO浓度、瓦斯浓度、风量风速、巷道行走难度和人员综合素质;利用各影响因素的量化值更新蚁群算法信息素,寻找并保存最优路径。仿真结果表明,采用基于蚁群算法的井下救援路径优化方法能够选出最优路径,同时最优解具有较好的收敛性。

关键词:井下应急救援; 路径优化; 蚁群算法; 层次结构模型; 层次分析法

0 引言

智能仿生优化算法具有运筹学理论方法无法比拟的优越性,将其用于解决路径优化问题是一个研究热点[1-3]。蚁群算法在智能仿生优化算法推动下得到了很大发展,这也是本文以蚁群算法作为基础的重要理论背景。将蚁群算法应用于解决煤矿井下应急救援路径优化的研究尚不多见[4]。文献[5-6]将蚁群算法与井下巷道当量长度相结合,搜索应急救援最短路径。本文在此基础上,考虑应急救援中的环境因素作用,提出了基于蚁群算法的井下救援路径优化方法,利用AHP(Analytic Hierarchy Process,层次分析法)对影响路径选择的因素进行量化分析,并将其用于更新蚁群算法中的信息素,以获得最优救援路径。

1 蚁群算法研究现状

蚁群算法包含系统的研究原理和数学模型[7-8],将蚁群算法应用于解决实际问题具有较大的研究空间。

(1) 理论研究方面。文献[9]针对基本蚁群算法存在的缺陷,引入动态调整因子,并结合Max-Min Ant System,将各条路径的信息素浓度限制在最大值与最小值之间,避免信息素无限累加和信息素为零的现象,加速收敛同时避免早熟、停滞现象。文献[10]将蚁群算法和灰色理论相结合用于城市道路寻优中,充分发挥蚁群算法全局搜索的优势,在交通数据量大、交通情况复杂的背景下,提高了路径选择的效率,实现了城市道路动态最优选择的目标。文献[11]针对基本蚁群算法的不足,对其数学模型及参数组合选择方法进行了改进研究,将改进后的蚁群算法应用于事故受灾点救灾物资的配送中,取得了较好的效果。

(2) 应用研究方面。文献[12]针对公路煤运路径选择,从选择策略和信息素挥发速度两方面改进了基本蚁群算法,较好地克服了其最优解不稳定和易陷入局部最优解的缺点,在提高收敛速度、优化配送路径方面取得了良好的效果。文献[13]基于复杂系统脆性理论和蚁群算法,对综合交通枢纽应急疏散路径选择问题进行了探讨。文献[14]针对交通网络中多属性条件下路径选择问题,将蚁群分为若干个子蚁群搜索最优解,各个子蚁群之间互相影响,综合搜索效果较好。文献[15]针对物流配送中车辆路径优化问题,提出在状态转移规则中引入时间窗跨度和服务等待时间因素,在算法的不同阶段采用不同的信息素蒸发策略来防止算法陷入局部最优,使得车辆等待时间较少而配送效率较高。文献[16]针对云数据库分布性及动态性带来的路由预测计算效率问题,提出基于自适应多态蚁群算法的动态路径优化方法,能够有效提高收敛速度,实现搜索结果全局最优。

2 救援路径选择影响因素层次结构模型

利用AHP方法[17],结合影响煤矿火灾救援的主要因子,建立救援路径选择影响因素层次结构模型,如图1所示。

图1 救援路径选择影响因素层次结构模型
Fig.1 Hierarchical structure model of influencing factors of rescue path selection

该模型中影响救援路径选择的因素包括巷道行走难度(巷道行走难度是换算当量长度中的一项系数)、瓦斯浓度、CO浓度、风量风速和人员综合素质。其中巷道行走难度可由巷道的长度、坡度、安全性和底鼓等因素综合得到;瓦斯浓度是选择救援路径时非常重要的指标;CO属于有毒气体,其浓度直接关系到救援人员的安全,是最为重要的指标;考虑到一些巷道有最低风速的要求,因此,风量风速是比较重要的指标;人员综合素质是综合性的指标,包括救援人员的经验、体能、负重、文化程度、专业技能等。救援队在防毒面罩和氧气罐的保护下,允许在CO浓度、瓦斯浓度低的路径上通过。

综合考虑,各影响因素的重要程度由高到低排列为CO浓度、瓦斯浓度、风量风速、巷道行走难度和人员综合素质。

3 基于蚁群算法的井下救援路径优化方法

蚁群算法搜索过程如下:初始时刻,m只蚂蚁随机放置于井下节点中,各节点间的信息素初始值τ0相等,τ0=m/LmLm为采用相邻相通启发式方法构造的路径长度。经过时间t,所有蚂蚁完成一次周游,更新各节点间的信息素,更新公式为

(1)

式中:τij为边(i,j)上的信息素;ρ为信息素挥发系数,0<ρ≤1;为第k只蚂蚁在其经过的边上释放的信息素。

信息素的变化由图1所示的各主要影响因素决定,计算公式为

(2)

式中:dijhijcijaijrij分别为边(i,j)上巷道当量长度值、瓦斯浓度值、CO浓度值、风量值、人员综合素质值;T为巷道边的集合。

选择路径的原则:信息素越大,被选择的概率越高。因此,求取最优路径问题可转换为求取τij最大值问题,τij值越大,蚂蚁选择的概率越高。蚁群算法流程如图2所示。

图2 蚁群算法流程
Fig.2 Flow of ant colony algorithm

4 仿真分析

4.1 AHP准则层权值计算

收集5位煤矿相关专家经验构造判断矩阵,包括准则层对目标层的判断矩阵,取平均后得到最终的判断矩阵,见表1。

表1 准则层S对目标层T的判断矩阵Table 1 Judgment matrix of guidelines layer S to target layer T

TS1S2S3S4S5S111/51/71/32S2511/236S372157S431/31/514S51/21/61/71/41

用层次分析法计算得到准则层权重,巷道当量长度、瓦斯浓度、CO浓度、风量风速和人员综合素质的准则层权值分别为0.061 6,0.288 8,0.474 3,0.132 0,0.043 2。

4.2 仿真数据

选取西北某矿业公司1号井307工作面巷道数据进行仿真模拟。为了方便描述和简化巷道模型,选取其中8个关键节点之间的巷道进行仿真计算,这8个节点的属性数据见表2。

利用Matlab软件求得8个关键节点之间的距离,构建距离矩阵。如果节点之间不直接连接,则将其距离设置为无穷大,用INF表示。编程计算得到距离矩阵,见表3。

表2 巷道节点属性数据
Table 2 Attribute data of roadway nodes

节点经距(X)纬距(Y)标高(Z)131523141653229882841587329732594575429433124641523272429623630042574589729232857622828802207625

表3 相邻节点间的距离矩阵
Table 3 Distance matrix between adjacent nodes m

节点1234567810348580INFINFINFINFINF23480247291INFINFINF64435802470534INFINF271INF4INF2915340928INFINFINF5INFINFINF9280INFINF5956INFINFINFINFINF02963897INFINF271INFINF29606518INF644INFINF5953896510

通过现场模拟与测量,得到巷道的影响因素系数和巷道当量长度,见表4。巷道影响因素系数包括巷道有效宽度、巷道有效高度、巷道坡度、路面湿度和有无障碍物,分别用β1β5表示。

表4 巷道影响因素系数及当量长度
Table 4 Influence factor coefficient and equivalent length of roadway

巷道实际长度/mβ1β2β3β4β5当量长度/mE123480.40.30.30.10.1765E135800.30.10.30.20.41334E232470.20.30.20.20.2518E242910.20.40.30.20.3698E286440.30.10.30.20.41481E345340.30.20.40.10.31228E372710.30.30.20.40.4704E459280.20.40.40.40.32505E585950.20.30.50.20.21428E672960.30.40.50.40.5917E683890.40.30.50.10.31011E786510.20.50.40.10.31627

根据表4,得到以当量长度为权重的邻接矩阵,见表5。

表5 当量长度邻接矩阵
Table 5 Equivalent length adjacency matrix m

节点12345678107651334INFINFINFINFINF27650518698INFINFINF14813133451801228INFINF704INF4INF698122802505INFINFINF5INFINFINF25050INFINF14286INFINFINFINFINF091710117INFINF704INFINF917016278INF1481INFINF1428101116270

4.3 仿真结果

为了分析蚁群算法参数对路径优化效果的影响,按照表6进行参数设置,寻找最适合井下节点环境因素特征的参数组合,结果见表7。

表6 蚁群算法参数设置
Table 6 Parameter settings of ant colony algorithm

组别NC_maxAlphaBetaRho1501.42.20.152500.83.00.073501.03.00.074501.02.80.075501.03.00.056501.23.00.077501.03.20.078501.03.00.099501.03.00.12

表7 参数优化适应度比较
Table 7 Comparison of fitness of parameter optimization

组别适应度值比较结果排序1110.9672113.4823113.501(最佳适应度)4111.304509(陷入局部最优)6111.2567110.9588113.4739111.325(陷入全局最优)

表6中,NC_max代表最大迭代次数;Alpha表示信息素相对重要性;Beta表示行走难易度相对重要性;Rho表示信息素挥发系数。

参数设置中,强调行走难易度相对重要性,故Beta取值大于Alpha。信息素挥发系数的值越小,其发现最优解的能力越强,但是其值较小时容易陷入局部最优,较大时容易陷入全局最优。由表7可知,第3组参数得到的适应度值最大。

利用本文提出的方法进行蚁群路径优化,获得最优救援路径,结果如图3所示。基于巷道当量长度法得到的最优路径与解的收敛性如图4所示。

(a) 最优路径

(b) 最优解适应度

图3 用本文方法得到的最优路径与解的收敛性
Fig.3 The optimal path and solution convergence obtained by the proposed method

(a) 最优路径

(b) 最优解适应度

图4 用巷道当量长度法得到的最优路径与解的收敛性
Fig.4 The optimal path and solution convergence obtained by roadway equivalent length method

4.4 结果分析

计算个体适应度函数是为了计算个体的适配值,适应度值是非负值,而且适应度值越大则该个体越优,即结果越好。从图3、图4可知,本文方法与巷道当量长度法均能产生最优解,且用本文方法得到的最优解的收敛性优于巷道当量长度法。

5 结论

(1) 将蚁群算法引入井下应急救援问题中,用于搜索最优救援路径,算法收敛性较好。

(2) 建立了救援路径选择影响因素层次结构模型,各影响因素按重要程度由高到低排列为CO浓度、瓦斯浓度、风量风速、巷道行走难度和人员综合素质。根据各因素与井下救援的关系,建立信息素更新公式,通过蚁群算法选择最优路径。

(3) 采用西北某矿业公司1号井307工作面巷道的数据进行仿真分析。仿真结果表明,采用基于蚁群算法的井下救援路径优化方法能够选出最优路径,同时最优解具有较好的收敛性。

参考文献(References):

[1] 李晓静,余东满.煤炭勘探及救援机器人最优路径规划研究[J].工矿自动化,2017,43(3):24-29.

LI Xiaojing,YU Dongman.Research on the optimal path planning of coal exploration and rescue robot[J].Industry and Mine Automation,2017,43(3):24-29.

[2] 冯鹏程,高社生,王东.基于区域分层的车辆队列行驶路径优化算法[J].武汉理工大学学报(交通科学与工程版),2015,39(3):484-487.

FENG Pengcheng,GAO Shesheng,WANG Dong.Paths optimizing algorithms for platoon vehicle based on area-layered[J].Journal of Wuhan University of Technology (Transportation Science & Engineering),2015,39(3):484-487.

[3] 胡丽丽,王战备,赵峰.考虑驾驶员满意度的高斯和声搜索物流配送路径优化算法[J].计算机应用研究,2015,32(12):3622-3625.

HU Lili,WANG Zhanbei,ZHAO Feng.Gaussian harmony search algorithm for driver satisfaction based logistics distribution path optimization[J].Application Research of Computers,2015,32(12):3622-3625.

[4] 刘勇.基于蚁群算法的应急救援最优路径研究[D].武汉:中国地质大学(武汉),2010.

[5] 王伟杰.基于蚁群算法的矿井火灾救灾最短路径研究[J].煤炭技术,2012,31(9):40-41.

WANG Weijie.Research on shortest path of mine fire disaster relief based on ant colony algorithm[J].Coal Technology,2012,31(9):40-41.

[6] 李兴宇.基于蚁群算法的矿井应急救援最短路径研究[J].煤炭技术,2013,32(1):102-103.

LI Xingyu.Research on shortest path of mine emergency rescue based on ant colony algorithm[J].Coal Technology,2013,32(1):102-103.

[7] DENG X,ZHANG L,LUO L.An improved ant colony optimization applied in robot path planning problem[J].Journal of Computers,2013,8(3):585-593.

[8] CHIVILIKHIN D S,ULYANTSEV V I,SHALYTO A A.Modified ant colony algorithm for constructing finite state machines from execution scenarios and temporal formulas[J].Automation and Remote Control,2016,77(3):473-484.

[9] 周科平,翟建波.改进蚁群算法在地下矿山运输路径优化的应用[J].中南大学学报(自然科学版),2014,45(1):256-261.

ZHOU Keping,ZHAI Jianbo.Application of improved ant colony algorithm in route optimization of underground mine's transportation[J].Journal of Central South University(Science and Technology),2014,45(1):256-261.

[10] 屈文斌.城市道路动态路径选择方法研究[D].西安:长安大学,2007.

[11] 杜业凡.城市道路交通网络最优路径选择研究[D].西安:西安建筑科技大学,2010.

[12] 荣海涛,宁宣熙.改进蚁群算法在公路煤运路径选择中的应用[J].计算机工程与应用,2009,45(12):239-241.

RONG Haitao,NING Xuanxi.Improved ant colony algorithm and its application in routing selection of coal transportation[J].Computer Engineering and Applications,2009,45(12):239-241.

[13] 周继彪,陈红,闫彬,等.综合交通枢纽安全应急疏散路径选择研究[J].中国安全科学学报,2014,24(2):164-170.

ZHOU Jibiao,CHEN Hong,YAN Bin,et al.Research on emergency evacuation route choice in integrated transport hub[J].China Safety Science Journal,2014,24(2):164-170.

[14] 陈京荣,俞建宁,李引珍.基于蚁群算法的多属性路径选择模型[J].系统工程,2009,27(5):30-34.

CHEN Jingrong,YU Jianning,LI Yinzhen.Model of choosing routes with multi-attributes based on ant colony algorithm[J].Systems Engineering,2009,27(5):30-34.

[15] 李琳.电子商务环境下物流配送中若干优化问题的研究[D].沈阳:东北大学,2010.

基金项目:国家自然科学基金资助项目(71271194);河南省基础与前沿技术研究项目(162300410073)。

作者简介:孙明波(1970-),女,河南郑州人,教授,博士,主要从事质量工程与故障诊断方面的研究工作,E-mail:1074278011@qq.com。

引用格式:孙明波,马秋丽,张炎亮,等.基于HGWO-MSVM的采煤机滚动轴承故障诊断方法[J].工矿自动化,2018,44(3):81-86. SUN Mingbo, MA Qiuli, ZHANG Yanliang, et al. Fault diagnosis method for rolling bearing of shearer based on HGWO-MSVM[J].Industry and Mine Automation,2018,44(3):81-86.

[16] 高长元,张云晖,张树臣,等.基于自适应免疫多态蚁群算法的云数据库动态路径优化研究[J].计算机应用研究,2015,32(10):2955-2959.

GAO Changyuan,ZHANG Yunhui,ZHANG Shuchen,et al.Cloud database dynamic path optimization based on immune polymorphic ant colony algorithm[J].Application Research of Computers,2015,32(10):2955-2959.

[17] 马春艳,龚瑛.煤矿谐振接地故障模糊综合选线方法[J].工矿自动化,2015,41(11):81-84.

MA Chunyan,GONG Ying.Fuzzy comprehensive line selection method of resonance grounding fault in coal mine[J].Industry and Mine Automation,2015,41(11):81-84.

Optimization method for mine rescue path based on ant colony algorithm

GONG Xingyu1, CHANG Xintan2, JIA Pengtao1, LUO Bibo3

(1.School of Computer Science and Technology, Xi'an University of Science and Technology, Xi'an 710054, China; 2.School of Energy and Resource, Xi'an University of Science and Technology, Xi'an 710054, China; 3.Shaanxi Science and Technology Resource Center, Xi'an 710077, China)

Abstract:In view of optimization problem of emergency rescue path in underground fire condition, an optimization method for mine rescue path based on ant colony algorithm was proposed. Hierarchical structure model of influencing factors on mine rescue path selection was established, and according to degree of importance, the influencing factors were listed as follows: CO concentration, gas concentration, wind speed, roadway difficulty and personnel quality. The quantification of each factor is used to update pheromone of the ant colony algorithm to find and save the optimal path. The simulation results show that the optimal path can be selected by using the rescue path optimization method based on the ant colony algorithm, and the optimal solution has good convergence.

Key words:underground emergency rescue; path optimization; ant colony algorithm; hierarchical structure model; AHP

文章编号:1671-251X(2018)03-0076-06

DOI:10.13272/j.issn.1671-251x.2017030023

中图分类号:TD77

文献标志码:A 网络出版时间:2018-02-05 17:18

网络出版地址:http://kns.cnki.net/kcms/detail/32.1627.TP.20180205.1023.001.html

收稿日期:2017-03-05;

修回日期:2018-01-10;责任编辑:胡娴。

基金项目:西安市科技计划项目(2017079CG/RC042(XAKD001));西安科技大学培育基金项目(201746)。

作者简介:龚星宇(1982-),男,宁夏平罗人,讲师,博士研究生,主要从事煤矿通风安全模拟研究工作,E-mail:108615030@qq.com。

引用格式:龚星宇,常心坦,贾澎涛,等.基于蚁群算法的井下救援路径优化方法[J].工矿自动化,2018,44(3):76-81. GONG Xingyu, CHANG Xintan, JIA Pengtao, et al. Optimization method for mine rescue path based on ant colony algorithm[J].Industry and Mine Automation,2018,44(3):76-81.

收稿日期:2017-11-06;

修回日期:2018-01-15;责任编辑:胡娴。