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

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

A genetic algorithm based on mixed repair for solving the maximum clique problem and its application in social networks

Social network analysis is a hot spot in data mining and it also has a very close contact with us in social life. The structure of the maximum clique, a typical social network substructure analysis method, is the most compact cohesive subgroup, so research on the maximum clique problem (MCP) has great significance in social network analysis. Aiming at the defects of the genetic algorithm (GA) for the MCP, such as long running, poor generality and low precision in some benchmark graphs, we propose a new genetic algorithm based on mixed repair, called MGA. A new mixed method based on degree and random chromosome repair, combing with the elitist selection based on randomly paire, uniform block crossover and inversion mutation operator, is adopted in the MGA, which can accelerate search speed, increase population diversity, and effectively prevent the algorithm from trapping into local optimum. We test the proposed algorithm on DIMACS benchmark graphs and typical social network instances. Experimental results show that the MGA has better performance and high generality, can more effectively resolve the MCP in social network analysis.