基于0-1规划的DNA计算模型的设计与实现

论文摘要

由于生物技术的发展和Adleman实验的成功使人们认识到一种新兴的计算方法一DNA计算。该方法具有的巨大并行性、海量存储以及低能耗等特点,引起了众多学者的关注,成为研究的热点。本文结合生物学的研究方法,对DNA计算及其模拟生物进化过程中的编码问题做了初步地探讨,对0-1规划的DNA计算模型和求解方法进行了研究。在DNA计算中,信息是以DNA序列为载体并通过DNA分子间的特异性杂交来完成信息的处理的,因此,DNA计算首要的问题就是DNA编码问题,目前的编码方法还无法很好地满足特定DNA计算模型的实际要求。本文在对DNA计算编码问题进行了探讨和分析,基于DNA模拟原理和DNA设计的基本原则,针对复杂的0-1规划模型—生产计划模型,提出了DNA编码策略,并用DNA编码链的理论及实验结果验证了编码的可行性。DNA计算离不开生物反应,并且在很大程度上依赖于生物技术,本文在用DNA计算解决生产计划问题的研究中,针对溶液计算的高度并行和高存储性,表面计算的高自动化程度等特点,采用基于溶液与表面计算相结合的方法,来建立复杂的0-1规划问题的DNA计算模型,充分利用了两种计算方法的优点,提高了求解的效率。DNA计算,可以求解复杂的计算问题。论文所构建的解决复杂的0-1规划问题0—生产计划问题的DNA计算模型,尽管在运算规模上还无法达到大容积溶液计算的高并行性和高存储量,但已具备说明问题的特征。通过将生物技术应用到0-1规划问题求解,会给解决NP复杂问题提供一种新思路、新方法。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第1章 绪论
• 1.1 现代分子学的发展与建立
• 1.2 DNA计算研究的背景及意义
• 1.3 DNA计算的发展及现状
• 1.4 本文的主要研究内容
• 第2章 0-1规划问题
• 2.1 0-1规划问题
• 2.2 0-1规划问题求解方法
• 2.3 0-1规划在生产计划问题的应用
• 2.4 小结
• 第3章 DNA计算
• 3.1 DNA计算的生物学基础
• 3.1.1 DNA分子结构
• 3.1.2 DNA计算生物操作
• 3.2 DNA计算的数学原理
• 3.3 DNA计算的编码策略
• 3.4 DNA计算的优势
• 3.5 小结
• 第4章 基于0-1规划的DNA计算模型设计
• 4.1 DNA计算模型
• 4.1.1 基于溶液的DNA计算模型
• 4.1.2 基于表面的DNA计算模型
• 4.2 基于0-1规划的DNA计算模型设计
• 4.3 小结
• 第5章 基于生产计划的DNA计算模型算法及实现
• 5.1 动态环境下生产计划模型
• 5.2 模型分析
• 5.3 模型的实现
• 5.3.1 算法实现
• 5.3.2 实验模拟
• 5.4 模型实现的结果
• 5.5 小结
• 第6章 结论
• 参考文献
• 致谢