基于OpenMP的遗传退火算法的并行化

论文摘要

在生物学领域根据氨基酸序列预测蛋白质结构是一个复杂而具有挑战性的问题。遗传退火算法是结合遗传算法和退火算法的优点而形成的一种新算法。它克服了遗传算法早熟早收敛、局部寻优能力差的缺点,同时也提高了模拟退火算法效率不高的问题。遗传退火算法(GAA)是被应用在AB非格点模型上的蛋白质结构预测(PSP)的最具代表性的算法之一,但是遗传退火算法需要大规模和很长时间的计算。因此,寻找一些方法减少有关蛋白质结构预测问题的计算时间和计算规模成了一项急迫的任务。多核处理器的出现,逐渐成熟的并行语言和可以直接运行在双核处理器电脑上的现存算法,这些为基于共享内存的编程提供了一个良好的先决条件。OpenMP是基于共享内存编程的工业标准,它具有许多优点,如简单性,可移植性和较好的可扩展性。因此,大多数用户喜欢使用OpenMP来提高算法的计算效率。本文提出了一种并行的模拟退火算法(GAA),此算法的目的是为提高蛋白质结构预测问题的计算速度。并行遗传退火算法使用了粗粒度并行模型,若干子种群代替了原来单一的种群,每个子种群独立的进化,每次进化完成之后本子种群中最好的个体依次取代其他子种群中最坏的个体以促进整个种群的进化。实验结果证明,此并行算法大大提高了遗传退火算法的计算效率。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究的背景及意义
• 1.2 国内外研究现状
• 1.3 研究的主要内容
• 1.4 本文的结构安排
• 第二章 OpenMP 介绍
• 2.1 OpenMP 编程简介
• 2.1.1 OpenMP 多线程发展状况
• 2.1.2 OpenMP 多线程编程基础
• 2.1.3 编译指导语句
• 2.1.4 运行时库函数
• 2.2 OpenMP 多线程应用程序编程技术
• 2.2.1 循环并行化
• 2.2.2 并行区域编程
• 2.3 线程同步
• 2.3.1 互斥锁机制
• 2.4 OpenMP 多线程应用程序性能分析
• 2.5 本章小结
• 第三章 遗传算法及退火算法
• 3.1 蛋白质的结构模型
• 3.2 遗传算法（GA）
• 3.2.1 遗传算法的基本原理
• 3.3 模拟退火算法（SA）
• 3.3.1 Metropolis 准则
• 3.3.2 算法的描述
• 3.4 本章小结
• 第四章 基于OpenMP 的遗传退火算法的并行化
• 4.1 遗传退火算法
• 4.2 遗传退火算法并行模型
• 4.2.1 直接并行模型
• 4.2.2 分布式并行模型
• 4.2.3 交叉并行模型
• 4.3 并行算法
• 4.4 本章小结
• 第五章 实验结果
• 5.1 实验环境
• 5.2 Fibonacci 蛋白质序列
• 5.3 实验结果对比
• 5.4 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 工作展望
• 参考文献
• 致谢
• 附录Ⅰ 攻读硕士学位期间成果
• 大摘要