基于SAGA-FCM的煤与瓦斯突出预测方法_李心杰.pdf

第 44 卷 第 2 期煤田地质与勘探Vol. 44 No.2 2016 年 4 月COALGEOLOGYEXPLORATIONApr. 2016 收稿日期 2015-03-28 基金项目 国家自然科学基金项目（51374121）；辽宁省高等学校杰出青年学者成长计划基金项目（LJQ2011028） Foundation item National Natural Science Foundation of China（51374121） ； University Excellent Younth Scholars Growth Plan Project of Liaoning Province（LJQ2011028） 作者简介 李心杰（1988），男，山东滕州人，硕士研究生，从事矿井通风及瓦斯防治工作 E-maillixinjie2013 . 通讯作者 贾进章（1974），男，河北石家庄人，教授，博士生导师，从事矿井通风与防灭火工作. E-mailjiajinzhang 引用格式 李心杰， 贾进章，李兵. 基于 SAGA-FCM 的煤与瓦斯突出预测方法［J］. 煤田地质与勘探，2016，44（2）00-00. LI Xinjie， JIA Jinzhang， Li Bing. Prediction of coal and gas outburst based on SAGA-FCM［J］. Coal Geology Exploration， 2016， 44（2） 00-00. 文章编号 1001-1986（2016）02--06 基于 SAGA-FCM 的煤与瓦斯突出预测方法 李心杰 1，2，贾进章1，李 兵 1 （1. 辽宁工程技术大学安全科学与工程学院，矿山热动力灾害与防治教育部重点实验室，辽宁 阜新 123000；2. 贵州省六盘水市钟山区安全生产监督管理局，贵州 六盘水 553000） 摘要 为提高模糊 C-均值聚类（Fuzzy C-Means Clustering Algorithm，FCM）算法在煤与瓦斯突出预 测中的准确度，提出一种将模拟退火算法（Simulated Annealing Algorithm，SA）与遗传算法（Genetic Algorithm，GA）相结合用于模糊 C-均值聚类分析的煤与瓦斯突出预测方法。该方法综合了模拟退 火算法全局搜索、高精度的优点和遗传算法强大的空间搜索能力，将经遗传模拟退火算法优化后 的初始值赋给 FCM，避免了由于聚类中心初始值选择不当造成 FCM 算法收敛到局部极小点上。 结合典型突出矿井数据进行分析，结果表明遗传模拟退火算法优化后的 FCM 算法较单一，预测 准确度高。 关键词模糊 C-均值聚类算法；遗传算法；模拟退火算法；煤与瓦斯突出 中图分类号P54；X936文献标识码ADOI 10.3969/j.issn.1001-1986.2016.02.000 Prediction of coal and gas outburst based on SAGA-FCM LI Xinjie1，2，JIAJinzhang1，Li Bing1 （1. College of Safety Science and Engineering， Liaoning Technical University， Fuxin 123000， China； 2. Administration of Work Safety of Zhongshan District of Liupanshui City of Guizhou Province， Liupanshui 553000， China） Abstract In order to improve the accuracy of Fuzzy C-Means Clustering Algorithm （FCM） in prediction of coal and gas outburst， a was putted forward. The uses fuzzy C-means clustering that combines simulated annealing algorithm （SA） and genetic algorithm （GA） to predict coal and gas outburst. The combines global search， high-precision advantages of simulated annealing algorithm and powerful search ability of space of genetic algorithm. Initial value optimized by the genetic simulated annealing algorithm is assigned to FCM. It avoids FCM algorithm convergence to local minima when the initial cluster center value is not properly selected. In combination with the analysis of typical outburst mine data， the results indicate that FCM optimized by the genetic simulated annealing algorithm is more accurate than the single FCM algorithm in prediction of coal and gas outburst. Key words fuzzy C- means clustering algorithm； genetic algorithm； simulated annealing algorithm； coal and gas outburst 近年来随着开采深度的增加，煤与瓦斯突出的 几率和强度逐渐增加，煤与瓦斯突出治理难度亦随 之加大。煤与瓦斯突出预测在煤矿突出治理中起着 非常重要的基础作用，相关学者在这方面已有较多 研究，如郭德勇等［1］的灰色理论预测方法，朱玉等［2］ 的免疫遗传算法，梁冰等［3］的灰靶决策方法，师旭 超等［4］的支持向量机预测方法等。上述预测方法在 煤与瓦斯突出预测方面取得了一定的成绩，但仍需 进一步改进和完善，比如存在推理技术的单调、学 习能力弱、 对待模糊边界点时处理准确率低等缺点。 模糊聚类分析能够集成上述缺点得出一个比较好的 预测结果［5］。模糊 C－均值聚类（Fuzzy C-Means Clustering Algorithm，FCM）是应用最广泛的模糊聚 类算法，该算法使用了在欧几里得空间确定数据点 的几何贴近度的概念，它将这些数据分配到不同的 聚类，然后确定这些聚类之间的距离［5］。但是，从 本质上 FCM 算法是一种局部搜索优化算法，如果 初始值选择不当，它就会收敛到局部极小点上［6］。 0014 ChaoXing 煤田地质与勘探第 44 卷 笔者将模拟退火算法和遗传算法相结合（SAGA）用 于聚类分析，在遗传操作进行到一定代数时， 对群 体中的最优个体进行退火操作和“撒种”操作， 使算 法跳出局部最优并且加快速度向全局最优解靠近， 有效克服了传统遗传算法的早熟现象，使该算法更 有效、更快速地收敛到全局最优解，因而能够提高 对煤与瓦斯突出预测的准确度。 1算法理论及其实现 1.1模糊 C- -均值聚类算法（FCM） 设｛｝ 12 ，，， n Xx xx为 n 个 数 据 样 本 ， （）2ccn≤ ≤是要将数据样本分成的类型的数目， ｛｝ 12 ，，， c A AA表示相应的c个类别，U 是其相似分 类矩阵，各类别的聚类中心为｛｝ 12 ，，， c v vv，（） ki xμ 是样本 i x 对于类 k A 的隶属度（简写为 ik μ）［7］。 则目标 函数 b J 表达式为 （）（） （） 2 11 ， nc b bikik ik JU vdμ ΣΣ（1） 式中（） （） 2 1 m ikikijkj j dd xvxv -- Σ ， ik d是欧几里 得距离， 用来度量第i个样本 i x与第k类中心点之间 的距离；m是样本的特征数。b是加权参数，取值 范围1b∞≤ ≤。模糊C-均值聚类方法就是寻找一 种最佳分类，使该分类能产生最小的函数值 b J。它 要求一个样本对于各个聚类的隶属度值和为1［7］， 即 满足 （） 1 1 c ji j xμ Σ ，1，2，，in（2） 式（3）和式（4）分别用于计算 i x对于类 k A的隶属 度 ik μ和c个聚类中心｛ ｝ i v 2 1 1 1 ik c b ik lkj d d μ - ■■ ■■ ■■ Σ （3） 设｛｝2；0 kik Iicn d＜≤，对所有的i类， k iI∈，0 ik μ。 （） （） 1 1 n b ikkj k ij n b ik k x v μ μ Σ Σ （4） 用式（3）式（4）反复修改聚类中心和数据隶属 度，并进行分类。当算法收敛时，就得到了各类聚 类中心及各样本对于各模式类的隶属度理论值，完 成模糊聚类的划分。FCM虽有很高的搜索速度，但 仅限于局部搜索算法，且对聚类中心的初值十分敏 感，若初值选择不当，则会收敛到局部极小点［8］。 1.2模拟退火算法实现 模拟退火算法于1983年成功地应用在组合优 化的问题上，其思想是通过模拟高温物体退火过程 找到优化问题的全局最优或近似全局最优解［9］。模 拟退火算法描述如下 a. 选 0 S作为初始状态，令（ ） 0 0SS，同时设 初始温度为T，令0i。 b. 令 i TT，以T和 i S调用Metropolis抽样算 法，返回状态S作为本算法的当前解， i SS。 c. 按 照 一 定 方 式 降 温 ， 即 1i TT， 其 中 1i TT＜，1ii 。 d. 检查终止条件，如果满足则转至步骤（5），否 则转回步骤（2）。 e. 当前解 i S为最优解，输出结果，停止［10］。 1.3遗传算法实现 a. 编码方式遗传聚类算法中，待优化的参 数是c个初始聚类中心，这里使用二进制编码，每 条染色体由c个聚类中心组成，对于m维的样本向 量，待优化的变量数为cm。假定每个变量使用k 位二进制编码，则染色体为长度是cmk的二进 制码串。 b. 适应度函数衡量个体优劣的尺度是适应 度函数，其作用类似于自然界中生物适应环境能力 的度量。 每个个体以式（1）得出的 b J为目标函数， b J 越小，个体适应度值就越高。因此，适应度函数采 用排序的适应度分配函数［11］（）intranking b FVJ。 c. 选择算子采用随机遍历抽样（sus）。 d. 交叉算子采用最简单的单点交叉算子。 e. 变异算子以一定概率产生变异基因数，用 随机方法选出发生变异的基因。如果所选的基因编 码为1，则变为0；反之则变为1［12］。 1.4算法流程 基于模拟退火遗传算法的模糊C-均值聚类，其 过程如图1所示。 2基于遗传模拟退火算法和模糊 C- -均值聚类的 煤与瓦斯突出预测方法 2.1煤与瓦斯突出预测指标的选取 煤与瓦斯突出是一种受多种因素控制的复杂矿 井动力现象，根据相关研究，选取瓦斯压力、瓦斯 放散初速度、煤体破坏类型、坚固性系数4个指标 为样本元素［13］。 15 ChaoXing 第2期李心杰等基于SAGA-FCM的煤与瓦斯突出预测方法 图 1算法流程图 Fig. 1Flowchart of the algorithm 2.2预测方法步骤 基于遗传模拟退火算法和模糊C-均值聚类的 煤与瓦斯突出预测方法步骤（图1）如下 a. 初始化各类控制参数，包括模糊C-均值聚 类算法中加权指数b，最大迭代次数N，目标函数 的终止容限D，种群个体大小sizepop，最大进化次 数MAXGEN，交叉概率 c P，变异概率 m P，退火初 始温度 0 T，温度冷却系数k，终止温度 end T。 b. 随机初始化c个聚类中心，并生成初始种群 Chrom， 对每个聚类中心用式（3）计算各样本隶属度， 及每个个体的适应度值 i f， 其中1，2，，isizepop。 c. 设循环计数变量gen0。 d. 对群体Chrom实施选择、 交叉和变异等异常 操作，对新产生的个体用式（3）、式（4）计算c个聚类 中心、各样本的隶属度，以及每一个体的适应度值 i f。若 ii ff ′＞ ，则以新个体替代旧个体；否则以概 率 （）（） exp ii PffT ′ -接受新个体，舍弃旧个体。 e. 若gen＜MAXGEN， 则gengen1， 转至步骤 d；否则，转至步骤 f。 f. 若 endi TT＜，则算法成功结束， 返回全局最优 解；否则，执行降温操作 1ii TkT ，转至步骤 c。 3实例分析 3.1基于 SAGA-FCM 的煤与瓦斯突出预测 将选取的18组典型突出矿井数据作为预测样 本，建立样本矩阵（表1）。其中， P为瓦斯压力；PΔ 为瓦斯放散初速度；f为坚固性系数。 由表1可知， 将煤与瓦斯突出的等级分为四类， 即I级突出程度为强，II级突出程度为中，III级突 出程度为弱，IV级突出程度为无。由于原始数据量 纲、数量级的不同，数值过大或过小都会对分类结 果造成较大的偏差［14］，利用式（5）对数据进行归一化 处理。 min maxmin n ll n l ll xx x xx - ′ - （5） 式中 n l x ′为归一化后的指标值； n l x 为第n个样本 的第l个指标； maxl x为第l个指标的样本最大值； minl x为第l个指标的样本最小值。 对归一化后得到的数据作为预测样本，利用 Matlab软件编码实现基于遗传模拟退火和模糊C- 均值聚类算法的煤与瓦斯突出预测，初始化控制参 数中加权指数b是模糊C-均值（FCM）聚类算法中的 一个重要参数，控制着隶属度的分配和聚类的模糊 程度，要使用FCM算法分析数据就必须选取合适 的b值，由文献［15］可知，在实际应用中b的最佳 取值范围是［1.5，2.5］，因此，设定b2，其余参数设 置最大迭代次数N10，目标函数的终止容限D1 10-6，种群个体大小sizepop100，最大进化次数 MAXGEN100， 交 叉 概 率 c P 0.7， 变 异 概 率 m P 0.01，退火初始温度 0 T 100，温度冷却系数 k 0.8，终止温度 end T1。 计算待测样本对于4个等级的隶属度，将各个 等级的隶属度进行比较，隶属度最大的等级即为待 测地点的煤与瓦斯突出预测等级。例如样本1的各 等级隶属度大小为I＞III＞II＞IV，因此样本1的预测 等级为I级，即突出程度为强。以此类推，得出其 它样本点的突出预测结果（表2）。 由表1与表2对比可知，在是否突出的预测中 所有样本预测结果与实际结果完全一致，在具体突 出程度的预测中稍有偏差，如样本2和样本16；其 他样本的预测突出程度与实际突出程度完全一致， 可见该方法预测准确度较高。 16 ChaoXing 煤田地质与勘探第44卷 表 1预测样本指标具体数据 Table 1Specific inds of prediction samples 序号P/MPaΔP构造类型f突出强度序号P/MPaΔP构造类型f突出强度 12.7519.030.31强101.054.820.60无 20.956.050.24弱112.3911.030.28弱 31.175.010.61无123.8613.050.32强 41.258.030.36中131.403.030.51无 52.007.010.48无142.1614.040.58弱 63.9514.030.22强150.9510.020.57无 71.404.030.58无162.007.050.48中 82.1614.040.34弱172.7519.050.31强 90.956.030.24中181.404.020.58无 表 2各样本点的隶属度及预测结果 Table 2Membership and prediction results of different sampling points 序号 隶属度 预测 结果 序号 隶属度 预测 结果 IIIIIIIVIIIIIIIV 10.420 20.101 80.416 90.061 1强100.009 30.031 80.016 60.942 3无 20.115 10.552 60.213 60.118 6中110.218 80.230 00.477 10.074 1弱 30.039 90.104 90.063 70.791 4无120.722 70.060 80.178 80.037 6强 40.017 70.883 80.048 30.050 2中130.038 20.200 70.072 30.688 8无 50.090 70.204 60.141 10.563 5无140.184 70.175 60.455 70.184 0弱 60.687 20.079 20.183 70.050 0强150.053 10.168 70.108 50.669 8无 70.028 00.104 10.052 80.815 0无160.162 00.308 50.345 50.184 0弱 80.025 00.016 50.952 50.005 9弱170.466 00.090 50.394 70.048 8强 90.043 00.793 40.084 10.079 4中180.004 80.015 60.008 20.971 4无 3.2SAGA- -FCM算法与FCM算法的收敛性比较 将SAGA-FCM算法和FCM算法的相应参数 设置完全一致，然后分别独立地运行10次，比较 两者的目标函数的收敛值。 由表3可知，SAGA-FCM算法运行10次的目 标函数收敛值均为12.192 3，说明每次都能得到最 优目标函数值，FCM算法运行10次的目标函数收 表 310 次预测结果目标函数收敛值 Table 3Convergence of objective function values in 10 prediction results 试验次数 目标函数收敛值 SAGA-FCM 算法 FCM 算法 112.192 312.251 1 212.192 312.301 4 312.192 312.244 3 412.192 312.253 8 512.192 312.589 7 612.192 312.269 3 712.192 312.227 2 812.192 312.252 5 912.192 312.923 4 1012.192 312.677 2 平均值12.192 312.399 0 敛值均不一样且都大于SAGA-FCM算法，说明 FCM算法容易收敛到局部最优解。 3.3准确度比较 SAGA-FCM算法与FCM算法分别用于煤与瓦 斯突出预测， 预测结果见表4。 对比表4与表1，FCM 算法能够准确预测是否突出，但是在突出程度的预 测中FCM算法预测偏差较大， 其中样本2、 样本8、 样本11、样本16的预测结果与实际偏差较大。可 见，SAGA-FCM算法较FCM算法预测偏差相对较 小，预测准确度有了较大提高。 表 4SAGA-FCM 算法与 FCM 算法对煤与瓦斯突出预 测结果的比较 Table 4Prediction results of SAGA-FCM algorithm and FCM algorithm for coal and gas outburst 突出程度 等级 预测结果 SAGA-FCM 算法 FCM 算法（Jb12.593 0） I1，6，12，181，6，8，12，18 II2，4，92，4，9，11 III8，11，14，1614，16 IV3，5，7，10，13，15，173，5，7，10，13，15，17 17 ChaoXing 第2期李心杰等基于SAGA-FCM的煤与瓦斯突出预测方法 4结 论 a. 将模拟退火算法与遗传算法相结合，然后用 于模糊C-均值聚类的煤与瓦斯突出预测， 通过在典 型突出矿井数据的试验，结果表明该方法预测准确 度较高。 b. 通过煤与瓦斯突出预测中SAGA-FCM算法 与FCM算法在相同的迭代次数下目标函数收敛值 大小的比较， 表明SAGA-FCM算法在收敛性上优于 FCM算法。 c. 基于SAGA-FCM算法的煤与瓦斯突出预测 方法通过模拟退火算法较强的局部搜索能力和遗传 算法较强的全局搜索能力，可以有效、快速的解决 FCM算法由于初始值选择不当，造成的收敛到局 部极小点上的问题， 提高了煤与瓦斯突出预测的准 确度。 参考文献 ［1］ 郭德勇，郑茂杰，郭超，等. 煤与瓦斯突出预测可拓聚类方法 及应用［J］. 煤炭学报，2009，34（6）783-787. GUO Deyong，ZHENG Maojie，GUO Chao，et al. Extension clustering for coal and gas outburst prediction and its application［J］. Journal of China Coal Society，2009，34（6） 783-787. ［2］ 朱玉， 张虹， 苏成. 基于免疫遗传算法的煤与瓦斯突出预测研 究［J］. 中国矿业大学学报，2009，38（1）125-130. ZHU Yu，ZHANG Hong，SU Cheng. The prediction of coal and gas outburst based on immune genetic algorithm［J］. Journal of China University of Mining and Technology，2009，38（1） 125-130. ［3］ 梁冰， 秦冰， 孙维吉. 基于灰靶决策方法的煤与瓦斯突出可能 性评价［J］. 煤炭学报，2011，36（12）1974-1978. LIANG Bing，QIN Bing，SUN Weiji. Possibility assessment of coal-gas outburst based on grey target model［J］. Journal of China Coal Society，2011，36（12）1974-1978. ［4］ 师旭超， 韩阳. 煤与瓦斯突出预测的支持向量机（SVM）模型［J］. 中国安全科学学报，2009，19（7）26-30． SHI Xuchao，HAN Yang. Prediction model for outburst of coal and gas based on SVM［J］. China Safety Science Journal，2009， 19（7）26-30． ［5］ 姚茂宣，任丽娜. 基于自适应权重模糊 C-均值聚类的瓦斯突 出预测［J］. 矿业工程，2012（10）96-99. YAO Maoxuan，REN Lina. Prediction on gas outburst of fuzzy C-mean value cluster base on self adaptive weighting［J］. Mining Engineering，2012（10）96-99. ［6］ 刘素华. 一种基于 Tabu 搜索的模糊聚类方法［J］. 计算机应 用，2005，25 （1）43-48. LIU Suhua. Fuzzy clustering based on Tabu search［J］. Computer Application，2005，25 （1）43-48. ［7］ 洪沛霖， 张佑生， 邢燕. 基于改进模拟退火算法的手写体数字 识别［J］. 计算机技术及发展，2007，17（9）15-17. HONG Peilin， ZHANG Yousheng， XING Yan. Hand written digit recognition based on improved simulated annealing algorithm［J］. Computer Technology and Development，2007，17（9）15-17. ［8］ 刘素华，侯惠芳. 一种基于模拟退火算法的模糊模式识别及其 应用［J］. 计算机仿真，2004，21（12）182-184. LIU Suhua，HOU Huifang. Fuzzy pattern recognition of grain insects based on simulated annealing algorithm［J］. Computer Simulation ，2004，21（12）182-184. ［9］ 李丽丽， 刘希玉， 庄波. 基于模拟退火粒子群算法的 FCM 聚 类方法［J］. 计算机工程与应用，2008，44（30）170-172. LI Lili，LIU Xiyu，ZHUANG Bo. Fuzzy C-means algorithm based on simulated annealing particle swarm optimization［J］. Computer Engineering andApplications， 2008， 44（30） 170-172. ［10］ 武兆慧，张桂娟，刘希玉．基于模拟退火遗传算法的聚类分 析［J］. 计算机应用研究，2005，22（12）24-26. WU Zhaohui，ZHANG Guijuan，LIU Xiyu. Clustering based on simulated annealing genetic algorithm［J］. Application Research of Computers，2005，22（12）24-26. ［11］ 杨珺，张闯，黄旭，等. 基于模拟退火遗传算法的分散式风电 选址定容［J］. 东北电力技术，2014（2）6-11. YANG Jun，ZHANG Chuang，HUANG Xu，et al. Sitting and sizing of distributed wind generation based on simulated annealinggeneticalgorithm［J］.NortheastElectricPower Technology，2014（2）6-11. ［12］ 马昌喜. 危险品道路运输网络优化设计研究［D］. 兰州兰州 交通大学，2013. ［13］ 梁冰，秦冰，孙维吉，等. 智能加权灰靶决策模型在煤与瓦 斯突出危险评价中的应用［J］. 煤炭学报，2013，38（9） 1611-1615. LIANG Bing，QIN Bing，SUN Weiji，et al. The application of intelligentweightinggreytargetdecisionmodelinthe assessment of coal-gas outburst［J］. Journal of China Coal Society，2013，38（9）1611-1615. ［14］ 杨志磊，王向前，王开元. 基于模糊 K-均值聚类法的煤与瓦 斯突出危险性评价［J］. 矿业工程研究，2012，27（3）44-46. YANG Zhilei， WANG Xiangqian， WANG Kaiyuan. Coal and gas outburst risk assessment based on fuzzy K-means clustering ［J］. Mineral Engineering Research，2012，27（3）44-46. ［15］ 高新波， 李洁，谢维信. 模糊 C-均值聚类算法中参数 m 的优 选［J］. 模式识别与人工智能，2000，13（1）7-11. GAO Xinbo，LI Jie，XIE Weixin. Optimal choice of weighting exponent in a fuzzy C-means clustering algorithm［J］. Pattern Recognition andArtificial Intelligence，2000，13（1）7-11. （责任编辑 晋香兰） 18 ChaoXing