基于OpenCL大规模种群并行遗传算法

doi:10.3969/j.issn.1006-2475.2016.03.007

计算机与现代化

基于OpenCL大规模种群并行遗传算法

(南京航空航天大学计算机科学与技术学院，江苏南京 210016)

收稿日期:2015-10-16 出版日期:2016-03-17 发布日期:2016-03-17
作者简介:徐沛彦(1991-)，女，安徽宣城人，南京航空航天大学计算机科学与技术学院硕士研究生，研究方向：计算机系统结构; 施慧彬(1966-)，男，副教授，研究方向：计算机系统结构，可重构计算，编译优化技术。

Large Population Parallel Genetic Algorithm Based on OpenCL

(College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Received:2015-10-16 Online:2016-03-17 Published:2016-03-17

摘要/Abstract

摘要： 为了提高RNA二级结构预测的准确率和加速遗传算法，提出基于OpenCL大规模种群并行遗传算法。通过研究遗传算法中潜在的并行性，以Acer TMP246M-MG-5086为实验平台，先在CPU中实现遗传算法，再使用OpenCL技术在GPU中实现大规模种群并行遗传算法。测试结果表明，并行遗传算法对于RNA二级结构预测的准确率平均提高了约49.88%，使用GPU平均加速比为9.76x。

关键词: 大规模种群, 并行遗传算法, RNA二级结构预测

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

中图分类号:

TP391

徐沛彦，施慧彬. 基于OpenCL大规模种群并行遗传算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.03.007.

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.

参考文献

[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.

基于OpenCL大规模种群并行遗传算法

Large Population Parallel Genetic Algorithm Based on OpenCL

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价