DNA遗传算法的研究及其在指派问题中的应用

论文摘要

DNA(Deoxyribonucleic acid)计算是一种模拟生物分子结构并借助于分子生物技术进行计算的新方法。目前DNA计算还处于起步阶段,本身还有很多理论和实际问题需要解决。遗传算法是一种模拟生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,在搜索最优解方面有独特的优势。DNA计算与遗传算法两者天生就具有某种必然的联系,可以互相借鉴。由于生物DNA计算的局限性,遗传算法可以作为DNA计算进行复杂优化问题求解的桥梁。从DNA计算角度看,在所有基于进化机理的方法中,遗传算法最适合采用DNA来实现。基于DNA计算的遗传算法,可以进一步模拟生物的遗传机理和基因调控机理,同时改进了DNA计算和遗传算法,具有更好的应用前景。本文将DNA计算思想和遗传算法相结合,围绕研究DNA计算的实现以及提高遗传算法的搜索效率、局部搜索能力及克服早熟收敛等核心问题,研究DNA遗传算法。并在此基础上提出了一种基于优秀基因片段思想的改进DNA遗传算法,将这段基因片段提取出来并将它遗传到后代中,可以加快收敛速度。给出了DNA遗传算法的结构,讨论了选择、交叉和变异算子的具体操作。最后本文将改进后的DNA遗传算法应用到指派问题最优解的求解中,提出了具体的编码和详细的算法步骤,并对一个具体实例进行了仿真实验,证明了改进后的DNA遗传算法具有收敛速度快和较好的全局搜索能力,初步验证了该算法的有效性和实用性。

论文目录

• 摘要
• ABSTRACT
• 1 前言
• 1.1 研究背景
• 1.2 研究意义
• 1.3 研究历史、现状及发展趋势
• 1.4 本文的主要工作
• 2 DNA计算
• 2.1 DNA计算的生物基础
• 2.1.1 DNA分子结构
• 2.1.2 DNA计算生物操作
• 2.1.3 DNA计算的实现
• 2.2 DNA计算的编码
• 2.2.1 影响DNA编码的因素
• 2.2.2 DNA编码方法
• 2.3 DNA计算的发展和研究现状
• 2.3.1 DNA计算发展
• 2.3.2 DNA计算研究现状
• 2.3.3 DNA计算存在的问题
• 3 遗传算法
• 3.1 基本遗传算法
• 3.1.1 基本思想
• 3.1.2 基本要素
• 3.1.3 基本流程
• 3.2 遗传算法的特点
• 3.3 遗传算法的研究进展
• 3.3.1 编码问题
• 3.3.2 种群问题
• 3.3.3 遗传操作
• 3.3.4 执行策略
• 4 改进的DNA遗传算法
• 4.1 基于DNA计算的遗传算法
• 4.1.1 DNA遗传算法的假设
• 4.1.2 DNA遗传算法的结构
• 4.2 DNA遗传算法与常规遗传算法的比较
• 4.3 一种改进的DNA遗传算法
• 4.3.1 改进思想
• 4.3.2 改进技术
• 4.3.3 算法编码及操作算子
• 4.3.4 算法实现步骤
• 5 改进的DNA遗传算法在指派问题中的应用
• 5.1 指派问题
• 5.2 算法编码
• 5.3 算法步骤
• 5.4 实验仿真
• 5.5 小结
• 6 结论
• 7 展望
• 8 参考文献
• 9 攻读硕士学位期间发表论文情况
• 10 致谢