论文并行遗传算法收敛性分析及优化运算

《论文并行遗传算法收敛性分析及优化运算》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第286卷　第期计　算　机　工　程20026年月Vol.28№6ComputerEngineeringJune2002·软件技术与数据库·文章编号：1000—3428(2002)06009——204文献标识码：A中图分类号：TP273并行遗传算法收敛性分析及优化运算1122戴晓明，许超，龚向阳，邵惠鹤（1.上海交通大学自动化研究所，上海200030；2.上海交通大学电子工程系，上海）200030摘要：经典遗传算法（CanonicalGeneticAlgorithms）利用单一种群对种群个体进行交叉、变异和选择操作，在

2、进化过程中的超级个体易产生过早收敛现象，粗粒度并行遗传算法利用多个子种群进行进化计算，各子群体分别独立进行遗传操作，相互交换最优个体后继续进化。该文证明了该算法的搜索过程是一个有限时齐遍历马尔柯夫链，给出粗粒度并行遗传算法全局最优收敛性证明。对于旅行商问题TSP(TravelingSalesmanProblem)利用粗粒度并行遗传算法进行了求解，以解决经典遗传算法的收敛到局部最优值问题。仿真结果表明，算法的收敛性能优于经典遗传算法。关键词：粗粒度并行遗传算法；有限时齐遍历马尔柯夫链；收敛；TSPConvergence

3、AnalysisofParallelGeneticAlgorithmandItsApplicationtoOptimization1122DAIXiaoming，XUChao,GONGXiangyang,SHAOHuihe(1.DepartmentofAutomation,ShanghaiJiaotongUniversity,Shanghai200030；2.DepartmentofElectronics,ShanghaiJiaotongUniversity,Shanghai200030)【Abstract】Cano

4、nicalgeneticalgorithmappliesasinglepopulationtooptimizethefunctions.Thesuper-individualduringtheearlystageofevolvingprocesscancausepre-maturityphenomenon.Coarse-grainedGeneticAlgorithm(CGGA)appliesmulti-populationtooptimizetheobjectiveproblem.Differentpopulatio

5、nevolvesindependently.ThemigrationfactorisintroducedtotheCGGA.Theeliteindividualreplacestheneighboringpopulationsworstindividual.ThesearchprocessofCGGAisanergodichomogeneousMarkovchain.TheglobalconvergenceproofofCGGAispresentedinthispaper.TheNP-hardTravelingSal

6、esmanProblem(TSP)iscitedasthebenchmarkproblemtotesttheefficacyoftheCGGA.ThesimulationresultshowsthatCGGAholdsfasterconvergencespeedthantheCanonicalGeneticAlgorithm(CGA).Theinherentpre-matureproblemcanbegreatlyleviedbyCGGA.【Keywords】Coarse-grainedparallelgenetic

7、algorithms；ErgodichomogeneousMarkovChain；；GlobalconvergenceTSP遗传算法是由美国Michigan大学Holland教授于年1975经典遗传算法存在着局部搜索性能较差的缺陷，对于某[1]首次提出的。遗传算法对求解问题无可微性及其他要求，些分布变化缓慢的问题，常常需要进行大量的计算，并且由在搜索过程中，同时对搜索空间中的多个解进行评估，但是于进化初期的超常个体使得种群过早收敛到局部最小值，为在经典遗传算法搜索过程中，进化初期的超常个体可能限制了解决这一缺陷，在遗

8、传算法并行运算的基础上，通过多种了其它个体进化，从而造成未成熟收敛现象。本文应用粗粒群并行进化和引入迁移算子进行种群间信息交流的思想，将度并行遗传算法，给出了其全局最优收敛性证明，对于NP遗传算法分解为在多个子种群间并行进行，并通过子种群间难的TSP问题求解，仿真结果表明粗粒度并行遗传算法的效交叉来增加基因模式数，避免未成熟收敛。粗粒度并行遗传