基于并行免疫遗传算法的无向排列的反转排序方法研究

论文摘要

生物的遗传物质随着进化而改变,相对于单个基因或少数几个基因组成的基因块的点变化,越来越多的研究更加关注基因组水平的较大变化。基因组重排是生物分子进化的一种重要模式,是计算分子生物学研究的一个重要问题,特别是基于反转的基因组重排的数学特征及算法的研究,一直受到广泛关注。由此产生了借助于反转来排序无向排列的问题,即给定可以代表基因组的两个排列,找到由一个排列转化到另一个排列的最优方案。遗传算法是一种基于自然选择和基因遗传学原理的全局性概率搜索算法,它已经过了三十多年的研究与实践。免疫学已成为一门学科,引起了国内外学者的注意。对于并行计算,这是一个充满活力的领域,它经过几十年的发展,这一领域的研究成果已在科学与技术的众多领域中随处可见。本文提出的是一种基于并行免疫遗传算法的无向排列的反转排序的方法,将一种免疫算子加入到遗传算法的框架中,通过对个体接种疫苗来进一步提升个体的存活能力,免疫遗传算法作为集免疫机制和进化机制于一体的全新演化算法应用到反转基因组重排的问题上是一种新的尝试,可以避免遗传算法存在的早熟缺点,同时使免疫遗传算法并行化可以提高收敛速度,由于无向排列的基因组反转排序问题是NP难题,现有的算法都是近似算法,因此将提高近似解的精确度。

论文目录

• 摘要
• ABSTRACT
• 引言
• （1） 研究背景
• （2） 国内外研究现状
• 第一章 基因组重排基础
• 1.1 基因组重排及其生物学背景
• 1.1.1 生物学背景
• 1.1.2 基因组重排
• 1.2 反转排序的基础知识
• 1.2.1 反转排序的相关概念
• 1.2.2 反转排序的相关定理
• 第二章 免疫遗传算法基础
• 2.1 遗传算法的基本原理
• 2.1.1 遗传算法的发展
• 2.1.2 遗传算法的基本概念及思想
• 2.1.3 基本遗传算法的描述及算法实现
• 2.1.4 基本遗传算法的特点与不足
• 2.2 免疫遗传算法的原理
• 2.2.1 免疫算法的原理及优势
• 2.2.2 本文采用的免疫遗传算法
• 2.3 遗传算法的并行性
• 2.3.1 遗传算法固有的并行性
• 2.3.2 引入并行遗传算法的理由
• 2.3.3 并行遗传算法的分类
• 第三章 并行计算基础
• 3.1 并行计算
• 3.1.1 并行计算的特点
• 3.1.2 并行计算的原理
• 3.1.3 并行系统的性能度量及开销
• 3.2 .NET 远程处理技术
• 3.2.1 远程处理框架
• 3.2.2 简化的远程处理结构
• 3.2.3 生成基本的.NET 远程处理运用程序
• 3.2.4 .NET 远程处理其它相关知识
• 3.3 .NET 线程处理部分
• 3.3.1 多线程的优缺点
• 3.3.2 使用线程和线程处理
• 第四章 并行免疫遗传算法无向反转排序的设计
• 4.1 适应度函数的设计思想
• 4.2 免疫遗传算法的设计思想
• 4.3 免疫遗传算法并行化的设计思想
• 第五章 并行免疫遗传算法系统的实现
• 5.1 基于RPC 的并行通信机制的实现
• 5.2 PIGA 并行系统的实现
• 5.2.1 Server 类
• 5.2.2 Client 类
• 5.2.3 Service 类
• 5.2.4 MainRun 类
• 第六章 实验结果与分析
• 6.1 实验平台
• 6.2 实验方案及结果
• 6.2.1 实验方案一及结果
• 6.2.2 实验方案二及结果
• 6.3 实验结果分析
• 结束语
• 参考文献
• 致谢
• 在读期间科研成果简介