基于IC的DNA计算算法的仿真与实现

论文摘要

1994年，Adleman用操纵DNA分子的办法解决了一个经典的NP完全问题—哈密顿路径问题(一个包含7个顶点实例)。自此以后，生物计算作为生物与计算机科学的交叉学科迅速地发展起来。虽然DNA计算(分子计算)具有运算高度并行，DNA作为载体信息贮存量大，能量消耗低，DNA分子资源丰富等优点，但是从目前分子计算发展来看，分子计算实现主要是溶液方式和表面方式，这两种实现方式目前显示出很多缺点：计算错误率高，单步执行慢，编码复杂，很难实现自动化。为了克服上述缺点，我们设计一种利用现有的IC技术解决DNA计算的新的实现方式。本文主要研究内容如下：1．系统地对DNA计算方法、原理、主要实现方式和优缺点等方面进行了探讨和总结，学习了FPGA和单片机的原理和软硬件开发环境，提出了一种基于大规模集成电路设计的DNA计算实现方式。2．结合传统计算机和DNA计算的并行性，本文设计了一种基于DNA计算的计算机结构模型。传统的计算机在解决串行工作任务的时候，其能力是无懈可击的，DNA计算相对于传统的计算机也有自己独特的优势，它能够同时搜索获得所有的结论。3．根据分子计算原理设计了一种具有可扩展性的解决SAT问题的算法，并用4个变量和6个变量的问题对算法的正确性进行了验证。并使用单片机作为控制器，FPGA上设计实现电路解决了上述问题。受限于目前实验条件，虽然理论上可以解决任意多个变量的问题，但是目前仅能解决11个变量也就是2048个分子处理单元的问题。4．研究分析了0—1规划问题的模型，并根据该问题的原理，提出了一种基于DNA计算的算法，并在所设计的机器模型上对该算法的正确性进行了验证，结果表明算法是正确的。5．分析了均分问题的计算模型原理，在原有模型基础上对7个变量的均分问题进行了仿真，验证了算法的正确性。6．最大集团问题是图论中一个重要问题，本文尝试了一个五个变量的最大集团问题，算法实现上目前只适合变量个数较少的问题，实现起来步骤虽然有所减少但是实现复杂度仍旧较大，本问题旨在探求一种用IC电路实现的满足进化算法和分子计算问题的实现电路。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 DNA分子的结构
• 1.3 DNA计算的基本思想
• 1.4 DNA计算机国内外研究现状
• 1.5 DNA计算研究内容及前景
• 1.6 DNA计算机优点
• 1.7 DNA计算目前存在的问题
• 1.8 本文主要研究内容
• 1.9 本文结果和创新点
• 第二章 基于 FPGA的片上系统设计
• 2.1 FPGA/CPLD简介
• 2.1.1 PLD的发展
• 2.1.2 FPGA/ CPLD的原理与区别
• 2.1.3 FPGA设计流程
• 2.2 VHDL语言介绍
• 2.3 ISE 8.1i介绍
• 2.4 本章小节
• 第三章 基于 DNA计算的计算机结构模型
• 3.1 模型的体系结构
• 3.2 转换器的设计
• 3.3 分子处理单元的设计
• 3.4 协控制器的设计
• 3.5 结果分析单元的设计
• 3.6 本章小结
• 第四章 基于 DNA计算的 SAT问题研究
• 4.1 可满足性（SAT）问题概念
• 4.1.1 定义
• 4.1.2 布尔表达式
• 4.2 3-SAT问题
• 4.3 其它SAT问题
• 4.4 SAT问题的分子计算方法
• 4.5 SAT问题实例一
• 4.6 SAT问题实例二
• 4.7 可满足性问题实现的规模
• 4.8 本章小结
• 第五章 基于 DNA计算的规划问题的算法研究
• 5.1 0-1规划问题介绍
• 5.2 0-1规划问题研究现状
• 5.3 实现算法
• 5.4 实例分析
• 5.4.1 模型总体设计
• 5.4.2 分子运算单元设计
• 5.4.3 操作过程
• 5.4.4 仿真结果
• 5.5 本章小结
• 第六章 若干其它问题的DNA计算算法研究
• 6.1 均分问题介绍
• 6.2 均分问题实现算法
• 6.3 均分问题实例分析
• 6.3.1 模型总体设计
• 6.3.2 计算步骤
• 6.3.3 仿真结果
• 6.3.4 结果分析
• 6.4 最大集团问题介绍
• 6.5 最大集团问题算法
• 6.6 最大集团问题实例分析
• 6.6.1 计算步骤
• 6.6.2 仿真结果
• 6.7 本章小结
• 第七章 总结与展望
• 7.1 结论
• 7.2 进一步工作
• 参考文献
• 致谢