论文部分内容阅读
最大团问题(Maximum Clique Problem,MCP)是图论中的经典组合优化问题,也是一类NP完全问题。被广泛的应用于许多领域,如人工智能、聚类分析、信号传输、子图同构问题、顶点覆盖问题等,所以对最大团问题的研究在理论上和实际生活中均有重要的意义。但是随着问题规模的增大,求解时间及复杂性呈指数增加,以往的确定性求法变得不再适用,人们开始将目光转移到采用启发式算法求解最大团问题,并取得了一定的研究成果。遗传算法作为一种常用的解决组合优化问题的启发式算法,在求解最大团问题上也已经取得一定成果,但仍存在通用性差、耗时长的问题,文中针对解决这一问题,提出了改进的遗传算法,并将对改进后的算法应用于社会网络中。文中首先简单的介绍了最大团问题、遗传算法以及社会网络的研究意义,然后详细的描述了最大团问题、遗传算法的研究现状,指出目前遗传算法解决最大团问题存在的不足,在此基础上提出了三种求解最大团问题的遗传算法,为了提高遗传算法求解最大团问题的时间效率,文中提出了一种基于度的染色体修复方法,给出了一种快速的求解最大团问题的遗传算法(FGA);之后为了在提高算法求解效率的同时进一步提高算法的通用性,文中引入了分阶段混合染色体修复方法,并且通过大量的实验确定了合理的遗传算子配置及参数配置,提出了基于分阶段混合修复的遗传算法求解最大团问题(MGA);最后为了进一步的提高算法的求解精度,通过分析国际通用基准图库DIMACS中不同类型图例的特点,提出了一种概率混合修复方法和多样化方法来增加遗传过程中种群的多样性,给出了一种基于概率混合修复求解最大团问题的多样化遗传算法(MDGA)。随着网络和信息技术的飞速发展,挖掘社会网络的行为特性和组织结构有着越来越重要的研究意义,寻找网络中的最大团是分析发现社团结构的有效途径之一,因此对最大团问题的研究具有实用价值和广阔的应用前景。文中提出的改进的遗传算法在国际通用基准图库DIMACS的基准图例上进行了测试,实验表明改进的遗传算法在时间效率和求解结果中均优于已有的求解最大团的遗传算法,同时文中提出的算法应用到了典型的社会网络实例上并与已有的求解社会网络较好的算法进行了比较,实验说明了算法求解精度得到了提高。