Abstract: 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 coarscgrained-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 r工caster-slave PGA and thus cor工ibined the higher parallel cor工iputing ability of rnuhi core cluster system with inherent parallelism of PGA. Realized the HPGA based on two-laycr 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.

Key words: Hybrid PGA, Multi-core cluster system, OpenMP, MPI