并行遗传算法的新进展

并行遗传算法将并行计算机的高速并行性和遗传算法固有的并行性相结合 ,极大地提升了遗传算法的求解速度和质量 .在主从式、细粒度和粗粒度这三类遗传算法并行化模型中 ,粗粒度模型以其较小的通讯开销和对种群多样化 ,获得了最广泛的应用 .本文概括了基于模式定理和有限状态马尔可夫链的遗传算法理论 ,总结了前人在粗粒度模型下开展的理论分析和实践应用 ,并指出并行遗传算法的研究将向异步化 ,理论化和模型化的方向发展 ,而有限状态马尔可夫链是构建并行遗传算法可执行模型的有力工具.

The Parallel Drifts of Genetic Algorithms

The parallel GAs (PGAs) combine the high-speed parallel-ability of supercomputers with the inherent parallelity of GAs, and improve greatly the efficiency and accuracy of GAs. Among the master-slave, fine-grained and coarse grained parallel avenues, the coarse-grained model is most widely used for its little communication overhead and its diversifying of the population. In this paper, the schema theory and the model based on the limit Markov chain are generalized, the previous analysis and implementation on the coarse grained model are reviewed. It is shown that researches of PGAs will focus on asynchronization, theorization and modelization. Furthermore, the theory of limit Markov chain provides powerful tools to construct executable models of PGAs.