求解最大团问题的混合修复遗传算法及其在社会网络中的应用

摘要：

社会网络分析是数据挖掘中与社会生活联系最紧密的热点之一,凝聚子群分析是一种典型的社会网络子结构分析方法,其中最大团结构是关系最紧密的凝聚子群,最大团问题的研究在社会网络分析中有重要意义.针对遗传算法在求解最大团问题中运行时间长、部分基准图例求解精度不高等问题,提出了一种基于混合修复策略的遗传算法MGA.MGA算法融合度修复和随机染色体修复方法并结合随机配对的精英选择、均匀块交叉和倒位变异算子,可以有效避免算法陷入局部最优,在加快收敛速度和丰富种群多样性方面有明显效果.算法在DIMACS基准图例和典型的社会网络实例上进行了测试,实验结果表明MGA算法具有较好的求解精度和较快的收敛速度.

关键词：社会网络分析、最大团、遗传算法、混合修复策略、精英选择、均匀块交叉、倒位变异

所属期刊栏目：38

分类号：TP391.4(计算技术、计算机技术)

资助基金：天津市自然科学基金15JCQNJC00600;天津商业大学青年科研培育基金150115

在线出版日期：2017-01-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2552-2559