基于公共池自适应迁移策略的并行遗传算法

《基于公共池自适应迁移策略的并行遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于公共池自适应迁移策略的并行遗传算法　　摘要：分析了传统粗粒度并行遗传算法的局限性，针对其迁移固定不变及无效迁移造成的通信开销大等缺点，将公共池与自适应迁移策略相结合，提出了一种适合在多核计算机上运行的基于公共池自适应迁移策略的并行遗传算法。该算法根据当前的进化状态自适应地进行迁移，并利用公共池淡化了子种群间交换个体时的拓扑结构。对复杂非线性函数求极值的仿真结果表明，该算法与传统并行遗传算法相比，收敛速度快，求解精度高，得到最优解的进化代数提前，并行效率明显提升。　　关键词：粗粒度；并行遗传算法；公共池；自适应迁移策略；函数优化　　

2、中图分类号：TP391文献标志码：A文章编号：1006-8228（2016）10-43-04　　Parallelgeneticalgorithmbasedonadaptivemigrationstrategyofsharingpool　　JiangRan　　（FacultyofInformationEngineering，YangzhouPloytechnicCollege，Yangzhou，Jiangsu225000，China）　　Abstract：Thelimitationsoftraditionalcoarsegrainedp

3、arallelgeneticalgorithmareanalyzed.Aimingatthedisadvantagesofhighcommunicationoverheadcausedbyfixedor9invalidmigration，aparallelgeneticalgorithmisproposed，whichissuitableforrunningonmulti-corecomputersandbasedontheadaptivemigrationstrategyofsharingpool.Accordingtothecur

4、rentstateofevolution，theproposedalgorithmcanadapttothemigration，andthesharingpoolisusedtodilutethetopologicalstructureoftheindividualexchangebetweenthesubpopulations.Simulationresultsforextremevalueofcomplexnonlinearfunctionshowthat，comparedwiththetraditionalparallelgen

5、eticalgorithm，thealgorithmisfastconvergence，highprecision，earlytoobtaintheevolutionarygenerationofoptimalsolution，andsignificantlyimprovestheparallelefficiency.　　Keywords：coarsegrained；parallelgeneticalgorithm；sharingpool；adaptivemigrationstrategy；functionoptimization　　

6、0引言　　并行遗传算法（ParallelGeneticAlgorithms，PGA）是将并行计算机的高速并行性和遗传算法的天然并行性相结合的一种算法。目前并行遗传算法模型分为主从式模型、粗粒度模型、细粒度模型和混合模型[1]。其中粗粒度模型是应用最广且适应性最强的并行遗传算法模型。　　1研究现状9　　国内外学者对粗粒度模型的研究，主要集中在迁移拓扑、迁移规模和迁移策略等问题上[2]。近几年相关的研究包括：蔡明?E、胡振兴等人提到的通过对交叉算子的修正，以及多个小规模种群并行优化求解的方案[3-4]；刘晋胜等人提出的采用八个不同策略为并

7、行遗传算法的分支遗传操作进行群体寻优等[5-6]。　　根据这些研究分析可知，一方面，如果粗粒度模型中各子种群之间迁移间隔小，则有利于提高解的精度和收敛速度，但会明显地增大通信及同步开销，如果迁移间隔较大，虽然降低了通信及同步开销，但不利于提高解的精度和收敛速度。针对这个问题，本文提出一种自适应迁移策略，即各个子种群中执行个体迁移时，并不是固定不变地移迁，而是根据当前的进化状态动态、有条件地迁移；此外，本文提出公共池的概念，应用公共池的方式来代替各子种群间个体迁移时的拓扑结构。因此，将本文算法称为基于公共池自适应迁移策略的并行遗传算法（

8、ParallelGeneticAlgorithmBasedonAdaptiveMigrationStrategyofSharingPool，简称AMSPPGA算法）。　　2AMSPPGA算法　　2.1AMSPPGA算法的