Paralleling Genetic Annealing Algorithm With OpenMP

Predicting the structure of protein through its sequence of amino acids is a complex and challenging problem in computational biology . Genetic annealing algorithm (GAA) is a kind of hybrid algorithm that combines genetic algorithm and simulated annealing. The GAA had been successfully employed in the protein structure prediction (PSP) on AB off-lattice model, which required a large-scale computing and a long time in the calculation. So it is an urgent task to find some ways to reduce the time and scale of the computation about the PSP problems.The emergence of the multi-core processor, the maturing of the parallel language and the existing algorithm based on shared memory directly running on the dual-core processor PC, provide a favorable prerequisite for application of the computer with the shared memory programming. OpenMP is an industry standard of the shared memory system programming and has many advantages such as simplicity, much better portability and scalability. So most users prefers to use OpenMP to improve computation efficiency of algorithms.In this paper we proposed a parallel GAA algorithm and employed it in the PSP problems to enhance the speed of computation. The Parallel GAA was implemented using coarse-grained parallel model and several sub-populations replacing the original single population, where every sub-populations evolved itself independently and the current best individual was distributed into all of the sub-populations at each evolution to promote the sub-populations'evolution. The experimental results confirmed that the parallel GAA has significantly improved the computation efficiency of GAA.