多核集群系统下的混合并行遗传算法研究  

Research of Hybrid Parallel Genetic Algorithm Based on Multi-core Cluster System

作　　者：王竹荣[1] 巨涛[1] 马凡[1] 

机构地区：[1]西安理工大学计算机科学与工程学院,西安710048

出　　处：《计算机科学》2011年第7期194-199,共6页Computer Science

基　　金：国家自然科学基金(60873035);陕西省教育厅自然科学专项研究基金(2010JK713)资助

摘　　要：为应对传统遗传算法在处理大规模组合优化问题面临的进化速度缓慢,难以达到实时要求的严峻挑战,提出了一种在多核PC集群系统上实现"粗粒度-主从式"混合并行遗传算法的模型:通过把"粗粒度-主从式"并行遗传算法映射到多核PC集群上,结合消息传递和共享存储两种并行编程模型,在节点间使用消息传递模型(MPI),对应的遗传算法为粗粒度并行遗传算法,在节点内使用共享存储模型(OpenMP),对应的遗传算法为主从式并行遗传算法,用MPI和OpenMP混合编程的方式以进程和线程两级并行在多核集群上实现具体的混合并行遗传算法。理论分析和实验结果表明,提出的实现模型有较好的性能,可大大改进传统遗传算法的缺陷。为利用并行遗传算法在普通多核PC集群上处理大规模组合优化问题提出了一种有效、可行的解决方案。In response to the challenge of the traditional genetic algorithms facing the slow pace of the evolution and difficulties of unable to meet real-time requirements in handing large-scale combinatorial optimization problems,this paper proposed the coarse-grained-master-slave hybrid parallel genetic algorithm（HPGA） model run on multi-core cluster system.Through integrating the features of the message-passing model and the shared-memory model,we used message-passing model—MPI among nodes to correspond coarse-grained PGA,used share-memory model—OpenMP within one node to correspond master-slave PGA and thus combined the higher parallel computing ability of multi-core cluster system with inherent parallelism of PGA.Realized the HPGA based on two-layer parallel both process and thread by using hybrid parallel programming models combing MPI and OpenMP on multi-core cluster system.Theoretical analysis and experimental results show that the HPGA model of this paper has high performance and overcomes traditional GA＇s defects.It put forward an effective and viable solution for using Parallel Genetic Algorithm based on simple multi-core PC cluster to deal with the large-scale combinatorial optimization problems.

关 键 词：混合并行遗传算法 多核集群系统 OPENMP MPI 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]