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

基于公共池自适应迁移策略的并行遗传算法 　　摘 要： 分析了传统粗粒度并行遗传算法的局限性，针对其迁移固定不变及无效迁移造成的通信开销大等缺点，将公共池与自适应迁移策略相结合，提出了一种适合在多核计算机上运行的基于公共池自适应迁移策略的并行遗传算法。该算法根据当前的进化状态自适应地进行迁移，并利用公共池淡化了子种群间交换个体时的拓扑结构。对复杂非线性函数求极值的仿真结果表明，该算法与传统并行遗传算法相比，收敛速度快，求解精度高，得到最优解的进化代数提前，并行效率明显提升。 　　关键词： 粗粒度； 并行遗传算法； 公共池； 自适应迁移策略； 函数优化 　　中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2016）10-43-04 　　Parallel genetic algorithm based on adaptive migration strategy of sharing pool 　　Jiang Ran 　　（Faculty of Information Engineering， Yangzhou Ploytechnic College， Yangzhou， Jiangsu 225000， China） 　　Abstract： The limitations of traditional coarse grained parallel genetic algorithm are analyzed. Aiming at the disadvantages of high communication overhead caused by fixed or invalid migration， a parallel genetic algorithm is proposed， which is suitable for running on multi-core computers and based on the adaptive migration strategy of sharing pool. According to the current state of evolution， the proposed algorithm can adapt to the migration， and the sharing pool is used to dilute the topological structure of the individual exchange between the sub populations. Simulation results for extreme value of complex nonlinear function show that， compared with the traditional parallel genetic algorithm， the algorithm is fast convergence， high precision， early to obtain the evolutionary generation of optimal solution， and significantly improves the parallel efficiency. 　　Key words： coarse grained； parallel genetic algorithm； sharing pool； adaptive migration strategy； function optimization 　　0 引言 　　并行遗传算法（Parallel Genetic Algorithms，PGA）是将并行计算机的高速并行性和遗传算法的天然并行性相结合的一种算法。目前并行遗传算法模型分为主从式模型、粗粒度模型、细粒度模型和混合模型[1]。其中粗粒度模型是应用最广且适应性最强的并行遗传算法模型。 　　1 研究现状 　　国内外学者对粗粒度模型的研究，主要集中在迁移拓扑、迁移规模和迁移策略等问题上[2]。近几年相关的研究包括：蔡明?E、胡振兴等人提到的通过对交叉算子的修正，以及多个小规模种群并行优化求解的方案[3-4]；刘晋胜等人提出的采用八个不同策略为并行遗传算法的分支遗传操作进行群体寻优等[5-6]。 　　根据这些研究分析可知，一方面，如果粗粒度模型中各子种群之间迁移间隔小，则有利于提高解的精度和收敛速度，但会明显地增大通信及同步开销，如果迁移间隔较大，虽然降低了通信及同步开销，但不利于提高解的精度和收敛速度。针对这个问题，本文提出一种自适应迁移策略，即各个子种群中执行个体迁移时，并不是固定不变地移迁，而是根据