多种群遗传算法及其在复杂网络社区划分中应用地研究

《多种群遗传算法及其在复杂网络社区划分中应用地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要复杂网络的社区划分问题是近年来研究的热点问题，如何对复杂网络的社区结构进行探测和划分对于了解整个网络的结构和性质具有非常重要的意义。到目前为止，已经提出了许多复杂网络的社区划分算法，但大部分算法还存在一定的缺陷，如有些算法需要事先知道社区内的节点数目以及社区个数等预知条件，部分算法还需要知道其它的一些门限值，而大部分算法则是由于时间复杂度过高，不适合用于对大型复杂网络的分析。基于此，本论文提出了一种基于多种群遗传算法的复杂网络社区划分的新方法，即IMPGA算法，并且通过实验验证了该算法的优越性。本论文的主要工作及创新点如下：(1)提出了一种改进的多种群遗传算法的结构

2、形式。传统的多种群遗传算法采用串行的思路求解复杂网络社区划分问题，IMPGA算法采用三个子种群并行进化的结构形式，其中一个为精英种群，而另外两个为普通种群，并使用多线程技术实现多种群的并行操作，使三个子种群并行进化，最终获得全局最优解。结构形式的改进使得算法在效率上得到了明显的提高。(2)提出了一种改进的自适应交叉概率与变异概率。传统的多种群遗传算法采用的是固定的交叉与变异概率，在IMPGA算法中，交叉概率根据个体的差异性进行判断，若差异性小则交叉概率大，反之则小，这样有利于个体性状的分离，增加种群的多样性；自适应的变异概率根据个体适应值进行判断，若适应值大则变异概率小

3、，反之则大，这样既保护了适应值大的优秀个体，使其优良基因不受破坏，又可以让适应值小的劣质个体得以变异，使其劣质基因得到改良。改进的自适应交叉变异概率降低了传统交叉与变异操作的破坏性，提高了算法对参数的配置能力，使得算法在寻优质量以及收敛效率上都得到了很大的提高。(3)提出了一种改进的迁移算子。在传统的多种群遗传算法中，一代进化结束后进行精英迁移，这样不但给算法带来效率上的负担，同时忽略了低劣个体的发展，不利于种群的进化。在IMPGA算法中，经过设定代数的进化，采用迁移算子进行迁移操作。两个普通种群分别产生最优个体，然后将其迁移到精英种群中，同时将两个普通种群中各自的最劣

4、个体和最优个体与对方的最劣个体和最优个体进行互换，这样既可以保留住低劣个体中的优良基因，甚至可以通过环境的改变使得低劣基因得到改良。改进的迁移算子促进了种群间个体的信息交互，增强了种群的多样性。(4)提出了一种基于多种群遗传算法的复杂网络社区划分的新方法，即IMPGA算法。算法克服了传统的复杂网络社区划分中出现的受先验信息限制、算法复杂度大以及局限于网络规模等问题，IMPGA算法只需要较少的先验信息，算法的效率较高，复杂度较低，因而适于大规模复杂网络的社区划分问题。关键词：复杂网络；社区划分；多种群遗传算法；迁移算子IAbstractTheproblemofthecom

5、munitydivisionincomplexnetworkisahotspotinrecentyears,Howtodetectanddividethecommunitystructureofcomplexnetworkisofgreatsignificancetounderstandthestructureandpropertiesoftheentirenetwork.Sofar,peoplehaveproposedmanycommunitypartitionalgorithms,althoughmostofthealgorithmsstillhavesomedef

6、ects,suchassomealgorithmsneedtoknowthenumberofnodesinthecommunityorthenumberofthecommunitiesinadvance,andpartofthealgorithmsstillneedtoknowotherthreshold,moreimportantly,mostofthealgorithmsarenotsuitablefortheanalysistolargecomplexnetworkduetothehightimecomplexity.Basedontheconclusionabo

7、ve,thispaperforwardanewmethodofcommunitydivisionincomplexnetwork,whichisbasedonmulti-populationgeneticalgorithm,namelyIMPGAalgorithm.TheexperimentsshowthesuperiorityoftheIMPGAalgorithm.Themajorworkandinnovationpointsinthispaperareasfollows:(1)Animprovedstructureformofthem