遗传模拟退火算法在系统发育树构建中的应用研究

摘要

系统发生是指生物形成或进化的历史。系统发生学研究物种之间的进化关系，其结果往往是以系统发生树表示。系统发生树是描述物种进化顺序和进化关系的一种拓扑结构。一个可靠的系统发生的推断，将揭示出有关生物进化过程的顺序，有助于我们了解生物进化的历史和进化机制。 发生树的构建问题是一个NP完全问题，因此，研究构造发生树的近似最优算法有着重要意义。目前常用的构建发生树的方法有三种，即距离法、最大简约法和最大似然法。 本文针对最大简约法，提出了一种新的搜索方法即遗传算法与模拟退火算法棚结合的启发示搜索。随机产生初始群体，然后通过遗传退火算子对初始群体进行优化，从中寻找更优树，不断地更新当前最优树，直到无法找到更优树或者达到了搜索次数的上限，算法停止。 对改进算法采用了评价建树算法中最常用的计算机模拟法来测试其性能，从实验结果来看，改进算法的准确性都有较大提高。

目录

文摘

英文文摘

声明

引 言

第1章绪 论

1.1生物信学

1.2课题背景

1.3国内外研究现状

1.4降低算法复杂性的方法

1.5确定树根

1.6本文的主要研究工作

1.7本章小结

第2章系统发育推断

2.1引言

2.2基本概念

2.3距离法

2.3.1非加权组平均法(UPGMA)

2.3.2Fitch-Margoliash方法

2.3.3邻接法

2.4最大简约法

2.4.1算法思想

2.4.2简约法搜索策略

2.5最大似然法

2.5.1算法思想

2.5.2似然法搜索策略

2.6发生树的检验标准

2.7本章小结

第3章构建发生树算法的研究

3.1引言

3.2遗传算法简介

3.2.1遗传算法中的基本概念

3.2.2基本遗传算法的构成要素

3.2.3基本遗传算法的运算过程

3.3模拟退火算法基本理论

3.3.1模拟退火算法的特点

3.3.2物理退火过程

3.3.3 Metropolis准则

3.3.4冷却进度表

3.3.5模拟退火算法的数学模型

3.3.6模拟退火算法基本步骤

3.4基于遗传算法和模拟退火算法的最大简约法

3.4.1遗传算法的“早熟”现象分析

3.4.2“早熟”现象的改进策略

3.4.3遗传退火算法设计简单描述

3.4.4基于遗传退火算法简约法建树的实现

3.5本章小结

第4章实验分析与系统设计

4.1引言

4.2数据实验与结果分析

4.2.1数据来源

4.2.2实验环境

4.2.3实现算法的参数

4.2.4实验结果与分析

4.3模拟实验与结果分析

4.3.1操作流程

4.3.2实验结果与分析

4.4本章小结

结 论

致 谢

参考文献

发表论文和参与科研情况