Paralleling Genetic Annealing Algorithm on Grid

Protein structure prediction (PSP) aims to search min energy for protein, which is a problem of non-deterministic polynomial (NP). A lot of algorithms have been proposed to solve this problem, and the time cost of the algorithms are significantly expensive due to complex computation. Genetic annealing algorithm (GAA) combining with simulated annealing algorithm and genetic algorithm, which is one of the most representative algorithms to be applied into the PSP, also requires large computing power for the complexity of the algorithm itself. To improve the efficiency of the algorithm, we established a grid system, implemented one parallel GAA algorithm in this system, and made some improvements to this algorithm. The results of the experiments shown that the parallel GAA´s maximum speed-up rate is 3.81 times the serial algorithm.