一种改进鱼群聚类算法在结构面分组中的应用

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-03-23

王述红¹, 任艺鹏¹, 陈俊智², 张紫杉¹
1. 东北大学资源与土木工程学院, 辽宁沈阳 110819;
2. 昆明理工大学国土资源学院, 云南昆明 650093
收稿日期：2017-11-01
基金项目：国家自然科学基金资助项目(51474050)；国家自然科学基金云南联合重点资助项目(U1602232)；辽宁省高等学校优秀人才支持计划项目(LN2014006)。
作者简介：王述红(1969-), 男, 江苏泰州人, 东北大学教授，博士生导师。

摘要：针对结构面产状常规分类方法存在的不足, 提出一种新型的结构面分类算法.基于K-Means算法的结构面分类, 将人工鱼群算法(artificial fish swarm algorithm，AFSA)与K-Means算法相结合, 建立了AFSA-RSK结构面分类算法.利用鱼群算法强大的寻优能力, 代替K-Means算法对结构面产状聚心集进行搜寻, 并通过K-Means算法进行聚类.聚类完成后, 选择相应参数指标对聚类效果进行评价.针对存在的问题, 对鱼群算法的步长和视野进行修正, 提高寻找聚心集的精度, 动态地调整了聚类过程.将改进后的AFSA-RSK算法与其他算法进行比较, 结果表明在迭代速度、聚类精度以及内存占比上, 改进后的AFSA-RSK算法都要更优, 更适合在结构面分组方面的应用.
关键词：人工鱼群算法岩体结构面岩体聚类边坡
An Improved Fish Swarm Clustering Algorithm for Structural Grouping
WANG Shu-hong¹, REN Yi-peng¹, CHEN Jun-zhi², ZHANG Zi-shan¹
1. School of Resources & Civil Engineering, Northeastern University, Shenyang 110819, China;
2. Faculty of Land and Resources and Engineering, Kunming University of Science and Technology, Kunming 650093, China
Corresponding author: WANG Shu-hong, E-mail: wangshuhong@mail.neu.edu.cn
Abstract: Aiming at the shortcomings of the conventional classification method of structural plane production, a new structural plane classification algorithm was proposed. Based on the structural plane classification of K-Means algorithm, the AFSA-RSK structural surface classification algorithm is established by combining the artificial fish swarm algorithm(AFSA)with the K-Means algorithm. The powerful optimization ability of the fish swarm algorithm is used to replace the K-Means algorithm to search for the structural surface set, and clustering by K-Means algorithm. After the clustering is completed, the corresponding parameters are selected to evaluate the clustering effect. According to the existing problems, the step size and visual field of the fish swarm algorithm are modified, the accuracy of finding the cluster is improved, and the clustering process is dynamically adjusted. Comparing the improved AFSA-RSK algorithm with other algorithms, it can be obtained that the improved AFSA-RSK algorithm is better in iterative speed, clustering precision and memory ratio, and it is more suitable for application in structural plane grouping.
Key words: artificial fish swarm algorithm(AFSA)rock joint planerock massclusteringslope
岩体是包含结构面和岩石的组合, 结构面的稳定一定程度上决定了岩体的失稳与否.因此对结构面进行统计和分组, 得到其分布规律, 对于研究大型边坡、地下硐室、隧道的稳定具有很大的意义.
由于表征结构面参数具有较大的随机性和变异性, 因此, 大多采用概率统计生成和分组的方式.王述红等^[1]采用双正态分布、Fisher分布等分布方式, 研究了随机结构面对块体搜索结果的影响.宋腾蛟等^[2]考虑几何参数和力学参数, 利用人工蜂群算法的优势对结构面产状进行了分类.Shanley等^[3-4]运用聚类算法对结构面数据进行分析.Hammah等^[5]首次将模糊C均值聚类算法应用于结构面的分组.张奇等^[6]基于层次聚类分析理论, 提出凝聚层次聚类结构面分组方法.黄润秋等^[7]利用粒子群算法较强的寻优能力, 优化了K-Means方法, 并结合K-Means方法对结构面进行分组.
本文将人工鱼群算法(AFSA)与K-Means算法相结合, 通过修正鱼群算法的步长和视野, 建立了改进的AFSA-RSK结构面分类算法.将改进后的AFSA-RSK算法与其他算法进行比较, 可以得到, 在迭代速度、聚类精度以及内存占比上, 改进后的AFSA-RSK算法都要更优, 更适合在结构面分组方面的应用.
1 结构面鱼群分类算法(AFSA-RSK)1.1 算法简介鱼群算法是李晓磊博士提出的一种智能寻优算法^[8-9], 通过构建人工鱼群并模拟鱼群寻找食物的过程来进行聚类.人工鱼群主要有三个行为:追尾、聚群、觅食.三种行为的最终目的是寻找到最优的个体.整个算法运行全过程控制参数主要有结构面样本集n、人工鱼移动步长Step、视野范围V, 迭代次数t.
1.2 鱼群适应度函数本文采用结构面坐标到结构面聚心距离平方和的倒数作为适应度函数.适应度计算公式为

(1)

式中:k为聚心个数; n为结构面样本总数; ‖d(c_i-x_j)‖²为分组结构面中样本x离聚心c的距离.距离计算公式^[7]为

(2)

式中, n_c, n_j分别为聚心结构面的单位法向量和j结构面的单位法向量.
1.3 移动策略觅食行为在假定初始聚心的情况下, 人工鱼在结构面样本集视野内随机搜寻, 搜寻公式为

(3)

式中:Step为移动步长; Rand函数输出(0~1)中随机一个数.按照式(3)随机移动后, 到达新的位置X_j处, 可以得到X_j的坐标值, 按照1.2节式(1), 式(2)计算新位置适应度, 若X_j处适应度更大, 则向前一步, 得到前进公式为

(4)

式中, X_i^t+1为多次执行觅食行为后新聚心的位置.
聚群行为人工鱼X_i搜索视野内的伙伴数量, 搜索完毕后, 计算当前视野内鱼群数目的均值坐标, 即为中心坐标值.若中心位置适应度较大, 输出中心坐标值, 同时按式(5)进行移动, 得到新的聚心坐标, 并与中心坐标值进行比较, 较优的记录下来, 中心位置计算方法如式(6)所示:

(5)

(6)

式中:X_j为视野内某结构面的坐标; g为伙伴数目;X_cen为鱼群经过聚群得到的结构面新聚心.
追尾行为??人工鱼X_i搜索当前视野中适应度最大的伙伴X_max, 寻找到之后, 在视野范围V内, 人工鱼进行移动, 移动方式见式(7), 按照式(7)可以得到新的聚类中心X_next的坐标值, 将X_next和X_max中的较优者记录下来.

(7)

式中, X_max为视野中最大适应度的个体.
1.4 算法流程1) 初始化鱼群行为参数, 并随机假定k个聚心, 根据结构面样本集(倾向、倾角)的极大值与极小值范围, 由聚心集生成的初始鱼群按照式(3), 式(4), 式(6), 式(7)分别执行觅食、聚群、追尾三种行为.每执行完一种行为, 将该行为中最优结构面坐标进行记录, 三种行为执行完毕, 比较三种行为中较优的坐标, 选择最优的结构面聚心坐标.
2) 按照新得到的结构面聚心坐标执行K-Means算法.
3) 采用Xie-Beni指标S_XB、分类熵指标Hm两项指标检验聚类效果, 计算单一K-Means算法, 并将结果记录, 与使用AFSA-RSK迭代后的聚类结果进行对比, 若AFSA-RSK两项指标误差均小于K-Means方法, 将结果记录, 并继续迭代, 超过最大迭代次数输出聚类结果, 若不满足, 执行步骤4).
4) 对步长和视野进行修正, 步长修正公式、改进的觅食行为策略和视野修正公式如式(8)~式(10)所示.
步长修正公式:

(8)

Step_max选为0.16, 则相应的改进觅食行为策略为

(9)

迭代次数对步长的影响如图 1所示.
图 1(Fig. 1)

图 1 步长变化图Fig.1 Step change chart

视野修正公式为

(10)

式中:V_max选为1;T_max为最大迭代次数.
对鱼群视野进行修正, 将鱼群视野范围与迭代次数建立函数关系, 随着迭代次数的增加, 鱼群每次行为之前视野的选取都与前一次迭代的视野相关, 建立视野随迭代次数动态的变化过程的函数, 有利于寻优精度的提升和运算速度的加快.
隶属度计算公式如式(11)所示:

(11)

式中:m为权值分配系数, 一般取1到2, 本文取1.5;d(x_j, c_i)是第j个结构面样本到i个聚类中心的距离; c_i为聚心坐标.
5) 修正视野与步长后, 改进后的AFSA-RSK算法每执行一步与前步结果进行比较, 并将两者间误差较小的值记录下来, 达到最大迭代次数后, 输出记录的最优结果, 并与K-Means算法计算结果比较.若优于, 则输出结果；否则, 再次修改步长, 重新迭代, 超过最大迭代次数后输出结果.
作者根据前述原理以及设计流程, 基于Matlab开发平台编写了该分析程序.
1.5 聚类有效性评价本文采取Xie-Beni指标S_XB、分类熵指标H_m^[10]两项指标进行聚类效果评价, 计算式为

(12)

(13)

式中:k是聚心个数; n为样本总数; U_ik为计算所得隶属度; d²(X_j, c_i)为某结构面样本X_j到聚类中心c_i距离的平方; min_i≠kd²(c_i, c_k)为两个距离最近的聚类中心距离的平方.分类指标H_m和指标S_XB越小, 代表聚类效果越良好; 反之, 聚类效果越差.利用以上两组评价指标, 对聚类结果进行评价.
2 工程实例分析2.1 工程简介本文采用云南省新平县鲁奎山铁矿岩质高边坡作为算例.该矿山边坡主要有碎石土、砾岩、泥灰岩等构成.
2.2 结构面优势分组为验证改进AFSA-RSK算法在结构面聚类分组的有效性, 选取鲁奎山铁矿某断面127组结构面, 采用Matlab和DIPS软件经过赤平投影分析可以得到密度云图, 如图 2所示.
图 2(Fig. 2)

图 2 结构面密度云图Fig.2 Structural surface density cloud image

根据上文所述方法, 要对聚类中心数目k进行假定, 根据结构面产状玫瑰花图, 并结合密度等值线图观察可以得到，聚类中心数目k为2~4.例如, 当选取k=2时, 随机生成2条人工鱼对应随机的结构面聚心, 分别采用前述步骤, 执行相关行为, 每进行一步, 对适应度进行计算, 若超过最大迭代次数, 终止算法, 并输出结果.限于文章篇幅, 选取k=3时改进AFSA-RSK算法与K-Means两种算法的聚类结果, 如图 3所示.
图 3(Fig. 3)

图 3 AFSA-RSK和K-Means聚类结果(k=3)Fig.3 The clustering results of AFSA-RSK and K-Means(k=3) (a)—AFSA-RSK；(b)—K-Means.

利用S_XB, H_m两种指标对k=2, k=3, k=4时的聚类结果进行评判, 评价结果如表 1所示.
表 1(Table 1)

表 1 聚类有效性评价Table 1 Cluster validity evaluation

方法	聚类数	S_XB	H_m
K-Means	k=2	0.2453	0.3123
	k=3	0.1997	0.2390
	k=4	0.2774	0.2619
AFSA-RSK	k=2	0.2204	0.2985
	k=3	0.1732	0.2174
	k=4	0.2639	0.2438

表 1 聚类有效性评价 Table 1 Cluster validity evaluation

通过表 1可以看出, 经过修正后的AFSA-RSK算法的两项指标的评价值优于K-Means算法, 且当聚类中心为3时, 无论是改进AFSA-RSK还是K-Means算法, 两项指标均小于聚类数为2和聚类数为4时的情况.这也说明从聚类效果来看, 聚类效果3是较为合理的, 两项指标均更优.
通过上述分析可以得到, 基于改进鱼群算法优化过后的K-Means算法, 适用于对结构面产状的聚类分析, 改进AFSA-RSK算法动态的优化机制, 使得鱼群在搜索结构面聚心的过程中, 不断搜索到适应度高的个体, 即结构面样本离聚心距离更小的个体, 最终达到优化聚类过程的目的.
由前文可以得到, 当k=3时, AFSA-RSK聚类结果较优.选取k=3时, 将AFSA-RSK结果与文献[7]、文献[11]计算结果进行比较, 三种算法都是通过优化迭代对聚心进行求解, 聚类结果见图 4.采用参数S_XB对计算结果进行评价, 参数变化图见图 5.
图 4(Fig. 4)

图 4 聚类结果对比Fig.4 Clustering results comparison (a)—AFSA-RSK；(b)—PSO；(c)—Firefly Algorith.

图 5(Fig. 5)

图 5 误差变化Fig.5 Error change graph

由图 5可看出, 鱼群算法通过修改迭代步长和视野, 迭代精度有所提高, 且随着迭代次数的增加, 4种算法的搜索精度都在提高, 视野与步长经过改进后的AFSA-RSK算法, 算法误差更小.
3 结论1) 改进AFSA-RSK算法动态的优化机制, 使得鱼群在搜索结构面聚心的过程中, 可以不断搜索到适应度高的个体, 最终达到优化聚类过程的目的.
2) 将鱼群算法中步长和视野与迭代次数建立联系, 使得人工鱼在搜索过程中动态地调整步长和视野, 优化鱼群搜索聚心的过程, 完成聚类.
3) 与其他算法进行比较, 在迭代精度、迭代速度和内存占比上, 经改进后的AFSA-RSK算法都要优于其他算法, 证明了本文提出算法的高效性和合理性.
参考文献

[1]	Wang S H, Ni P P, Yang H, et al. Modeling on spatial block topological identification and the irprogressive failure analysis of slope and cavern rock mass[J].Procedia Engineering, 2011, 10(7): 1509–1514.
[2]	宋腾蛟, 陈剑平, 张文, 等. 基于人工蜂群算法的岩体结构面多参数优势分组研究[J].岩土力学, 2015, 36(3): 861–868. ( Song Teng-jiao, Chen Jian-ping, Zhang Wen, et al. A method for multivariate parameter dominant partitioning of discontinuities of rock mass based on artificial bee colony algorithm[J].Rock and Soil Mechanics, 2015, 36(3): 861–868.)
[3]	Shanley R J, Mahtab M A. Delineation and analysis of clusters in orientation data[J].Journal of the International Association for Mathematical Geology, 1976, 8(1): 9–23.DOI:10.1007/BF01039681
[4]	Mahtab M A, Yegulalp T M. A rejection criterion for definition of clusters in orientation data[C]// Proceedings of the 22nd Symposium on Rock Mechanics. New York: American Institute of Mining Metallurgy and Petroleum Engineers, 1982: 116-123.
[5]	Hammah R E, Curran J H. Fuzzy cluster algorithm for the automatic identification of joint sets[J].International Journal of Rock Mechanics and Mining Sciences, 1998, 35(7): 889–890.DOI:10.1016/S0148-9062(98)00011-4
[6]	张奇, 王清, 阙金声, 等. 基于凝聚层次聚类分析法的岩体随机结构面产状优势分组[J].岩土工程学报, 2014, 36(8): 1432–1437. ( Zhang Qi, Wang Qing, Que Jin-sheng, et al. Dominant partitioning of discontinuities of rock masses based on AGNES[J].Chinese Journal of Geotechnical Engineering, 2014, 36(8): 1432–1437.)
[7]	宋金龙, 黄润秋, 裴向军. 基于粒子群算法的岩体结构面产状模糊C均值聚类分析[J].工程地质学报, 2012, 20(4): 591–598. ( Song Jin-long, Huang Run-qiu, Pei Xiang-jun. Particle swarm optimization algorithm based fuzzy C-means cluster analysis for discontinuities occurrence in rock mass[J].Journal of Engineering Geology, 2012, 20(4): 591–598.DOI:10.3969/j.issn.1004-9665.2012.04.016)
[8]	李晓磊, 邵之江, 钱积新. 一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践, 2002, 22(11): 32–38. ( Li Xiao-lei, Shao Zhi-jiang, Qian Ji-xin. An optimizing method based on autonomous animats:fish-swarm algorithm[J].Systems Engineering—Theory & Practice, 2002, 22(11): 32–38.DOI:10.3321/j.issn:1000-6788.2002.11.007)
[9]	李晓磊.一种新型的智能优化算法——人工鱼群算法[D].杭州: 浙江大学, 2003. ( Li Xiao-lei.A new intelligent optimization method—artificial fish school algorithm [D].Hangzhou: Zhejiang University, 2003.http://cdmd.cnki.com.cn/Article/CDMD-10335-2003051212.htm)
[10]	Bezdek J C. Pattern recognition with fuzzy objective function algorithms[M]. New York: Plenum Press, 1981: 203-239.
[11]	宋腾蛟, 陈剑平, 张文, 等. 基于萤火虫算法的岩体结构面优势产状聚类分析[J].东北大学学报(自然科学版), 2015, 36(2): 284–287. ( Song Teng-jiao, Chen Jian-ping, Zhang Wen, et al. Clustering analysis of dominative attitudes of rock mass structural plane based on firefly algorithm[J].Journal of Northeastern University(Natural Science), 2015, 36(2): 284–287.DOI:10.3969/j.issn.1005-3026.2015.02.028)