生物地理学优化算法及其在生物序列模式发现中的应用

摘要

生物序列中的模式发现问题是当前生命科学领域中的热门研究问题之一,对理解基因的功能与调控作用有重大价值。基于字符串和基于概率的模式发现方法虽已取得很大成功,但也存在一些问题,如基于字符串的方法仅适合发现一些短的完全有约束的模式和对长序列模式的发现性能不高;基于概率的方法对初始数据较敏感且不能保证全局最优解。
　　随着智能计算技术的迅速发展,进化计算以较强的全局搜索能力、初始条件的低敏感性、领域知识的非依赖性等优点受到关注,生物地理学优化算法(Biogeography-Based Optimization, BBO)作为一种新型的模拟自然界生物物种迁徙过程的进化算法,在提出的短短几年时间内已在许多领域获得成功应用。本文针对生物序列模式发现问题,分析了目前序列模式发现方法存在的问题,设计了生物地理学优化算法的三种改进算法,并将之应用于序列模式发现问题,为序列模式的发现提供了新的有效解决方案。
　　首先,本文通过分析BBO算法的特征,将其纳入群体智能算法之中,并借鉴群体智能的统一模型设计了BBO算法的模式及BBO的群体智能框架模型。将BBO算法纳入群体智能框架体系对BBO算法的理论及应用研究都有重要指导意义,同时对智能算法规律的探究和设计新的进化算法提供一些有益启示。
　　其次,针对目前序列模式发现方法在发现模式的准确性及运行时间存在的不足,考虑到BBO算法较强的局部开发能力和全局探测能力,提出一种针对序列模式发现问题的改进的生物地理学优化算法。该算法改进了BBO算法的迁移算子和变异算子,同时使用集成化机制生成初始种群。提出的算法能以较快的收敛速度获得有意义的模式。在两个常用数据集上的实验结果表明改进后的BBO算法用于模式发现问题的正确性和有效性,为序列模式发现问题提供了一种新的解决方案。
　　再次,为了增强BBO算法的开发能力及探测能力,提出一种增强算子的混杂生物地理学优化算法(Biogeography-Based Optimization/Differential Evolution/Generation, BBO/DE/GEN),BBO/DE/GEN算法利用差分进化算法的全局探测能力并结合生物地理学优化算法的局部开发能力,即借鉴差分进化改进BBO算法的变异算子,基于迭代次数改进BBO算法的迁移算子,并将BBO/DE/GEN算法用于全局数值优化问题及序列模式发现问题。对于全局数值优化问题,使用基准函数进行测试,并与BBO算法及BBO/DE(Biogeography-Based Optimization/Differential Evolution)算法比较,在求得的最优值和平均值方面均优于其它两种算法。对于序列模式发现问题,在常用的三个实验数据集上的实验结果表明,对复杂的长序列数据,BBO/DE/GEN算法能预测到更多有意义的模式。进而说明BBO/DE/GEN算法具有良好的性能。
　　最后,针对BBO/DE/GEN算法对少数基准函数的测试结果不理想,同时为了进一步提高预测模式的精度,提出了一种自适应参数的混杂生物地理学优化算法/差分进化算法(Adaptive Biogeography-Based Optimization/Differential Evolution/Generation, ABBO/DE/GEN),并将该算法应用于数值优化问题及序列模式发现问题。算法利用差分进化机制改进BBO算法的变异算子,基于迭代次数改进BBO算法的迁移算子,同时基于每一代适应度函数值与平均值之间的关系自适应的改变BBO算法的迁移概率和变异概率。在所有的基准函数上与BBO/DE/GEN算法比较,根据获得的最小值和平均值表明ABBO/DE/GEN算法有更好的性能。在序列模式发现问题上的实验结果也显示ABBO/DE/GEN算法比BBO/DE/GEN算法对长序列数据能发现更多的有意义的模式。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究工作的背景与意义

1.2 序列模式发现问题的国内外研究历史与现状

1.3 本文的主要工作与创新

1.4 本论文的结构安排

第二章 进化算法

2.1 遗传算法

2.2 差分进化算法

2.3 蚁群算法

2.4 粒子群算法

2.5 细菌觅食算法

2.6 文化算法

2.7 本章小结

第三章 生物地理学优化算法

3.1生物地理学优化算法

3.2生物地理学优化算法研究进展

3.4 本章小结

第四章 生物地理学优化算法求解序列模式发现问题

4.1引言

4.2 BBO算法

4.3 BBO算法的模式与框架

4.4序列模式发现问题的BBO算法

4.5实验结果和讨论

4.6本章小结

第五章 一种增强算子的生物地理学优化算法

5.1 引言

5.2 准备知识

5.3 BBO/DE/GEN算法

5.4 序列模式发现问题实验结果与讨论

5.5 本章小结

第六章 一种自适应参数的生物地理学优化算法

6.1引言

6.2 ABBO/DE/GEN算法

6.3 序列模式发现问题实验结果与讨论

6.4本章小结

第七章 全文总结与展望

7.1 全文总结

7.2 后续工作展望

致谢

参考文献

攻读博士学位期间取得的成果