Large Population Parallel Genetic Algorithm Based on OpenCL

doi:10.3969/j.issn.1006-2475.2016.03.007

Abstract

Abstract: In order to improve the accuracy rate of RNA secondary structure prediction and accelerate the genetic algorithm, this thesis proposed the implementation of a large population parallel genetic algorithm based on OpenCL. Through researching the potential parallelism of genetic algorithm, this thesis uses Acer TMP246M-MG-5086 as experimental platform, firstly realizes the genetic algorithm on CPU, then realizes the large population parallel genetic algorithm on GPU. Test results show that the accuracy rate of parallel genetic algorithm prediction has been increased about 49.88%, and the average speedup of using GPU is 9.76x.

Key words: large population, parallel genetic algorithm, RNA secondary structure prediction

CLC Number:

TP391

XU Pei-yan, SHI Hui-bin. Large Population Parallel Genetic Algorithm Based on OpenCL[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.03.007.

References

[1] Borkar P S, Mahajan A R. Different RNA secondary structure prediction methods[C]// Proceedings of the 2014 International Conference on Electronic Systems, Signal Processing and Computing Technologies (ICESC). 2014:228-230.

[2] 董浩. RNA二级结构预测方法研究[D]. 长春:吉林大学, 2011.

[3] Holland J. Adaptation in Natural and Artificial Systems[M]. Ann Arbor: University of Michigan Press, 1992.

[4] Van Batenburg F, Gultyaev A P, Pleij C W. An APL-programmed genetic algorithm for the prediction of RNA secondary structure[J]. Journal of Theoretical Biology, 1995,174(3):269-280.

[5] Shapiro B A, Navetta J. A massively parallel genetic algorithm for RNA secondary structure prediction[J]. The Journal of Supercomputing, 1994,8(3):195-207.

[6] Shapiro B A, Wu Jin Chu, Bengali D, et al. The massively parallel genetic algorithm for RNA folding: MIMD implementation and population variation[J]. Bioinformatics, 2001,17(2):137-148.

[7] Hendriks A, Wiese K C, Glen E, et al. A distributed genetic algorithm for RNA secondary structure prediction[C]// Proceedings of the 2003 Congress on Evolutionary Computation. 2003,1:343-350.

[8] Tong Kwok-Kit, Cheung Kwan-Yau, Lee Kin-Hong, et al. GAknot: RNA secondary structures prediction with pseudoknots using genetic algorithm[C]// Proceedings of the 2013 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB). 2013:136-142.

[9] Munshi A, Gaster B R, Mattson T G, et al. OpenCL编程指南[M]. 苏金国,李璜,杨健康,译. 北京:机械工业出版社华章公司, 2012:7-15.

[10] 詹云,赵新灿,谭同德. 基于OpenCL的异构系统并行编程[J]. 计算机工程与设计, 2012,33(11):4191-4195.

[11] Gaster B R, Lee H, Kaeli D R, et al. OpenCL异构计算[M]. 张云泉,张先轶,龙国平,等译. 北京:清华大学出版社, 2012.

[12] Scarpino M. OpenCL in Action[M]. Manning Publications, 2011.

[13] 刘海军. RNA二级结构预测的建模及其应用研究[D]. 上海:上海大学, 2005.

[14] 任清华,莫中息,陶玉敏. 预测RNA二级结构的一种遗传模拟退火算法[J]. 武汉大学学报(理学版), 2004,50(1):23-28.

[15] 胥杰. 基于混沌模拟退火的RNA二级结构预测的研究[D]. 成都:电子科技大学, 2010.

[16] Seo Jang-Ho, Im Chang-Hwan, Heo Chang-Geun, et al. Multimodal function optimization based on particle swarm optimization[J]. IEEE Transactions on Magnetics, 2006,42(4):1095-1098.

[17] Baldi P, Brunak S, Chauvin Y, et al. Assessing the accuracy of prediction algorithms for classification: An overview[J]. Bioinformatics, 2000,16(5):412-424.

[18] Hamada M, Kiryu H, Sato K, et al. Prediction of RNA secondary structure using generalized centroid estimators[J]. Bioinformatics, 2009,25(4):465-473.

[19] Brown J W. The ribonuclease P database[J]. Nucleic Acids Research, 1999,27(1):314.