论文部分内容阅读
电子计算机技术在科学研究与工程实践中获得了巨大的成功,但芯片的承载能力与处理能力限制了电子计算机计算速度的长久增长。作为一种新的计算模式,DNA计算获得了广泛关注。DNA计算主要面临以下困难:编码的质量与数量之间难以协调,编码问题难以求解;实验中繁琐的操作及生化反应的不完全,会对DNA计算结果产生不良影响;另外,对NP-完全问题,计算所需DNA分子数量与问题规模呈指数关系,限制了DNA计算的求解问题规模。针对上述问题,本文尝试从以下几个方面对DNA计算进行一些研究与讨论。
针对DNA编码问题,给出一种基于小种群遗传算法的求解方法。介绍了DNA编码问题的定义、约束条件及相关参数的计算方法。通过将H-类约束映射到DNA码字个体上,并引入码字之间的共享函数,构造了DNA编码问题的多目标优化模型,使得应用小种群遗传算法求解DNA编码问题成为可能。在具体求解过程中,引入逆补密码子算子,分段交叉算子,频变算子与倒位算子,对DNA编码问题进行了求解。与已有的结果相比,小种群遗传算法可以避免码字质量分布不均匀的问题,且种群规模约为DNA码字数量的2倍,计算量较少。
为降低DNA编码难度,在DNA算术运算中引入剩余数制。基于Adleman-Lipton模型,给出了DNA剩余算术运算的编码方案,以及二进制算术运算的DNA算法,并分别基于4-模数集P=f2n+1+2n ? 1; 2n; 2n ? 1; 2n+2n?1? 1g与n?模数集P=f2mn?1; 2mn?2 ? 1; ¢¢¢ ; 2m0? 1g,给出了剩余算术运算的DNA算法。在n?模数集中,计算的并行度为n,计算对DNA码字的需要量约为相应二进制情况下的1n。由于剩余位之间无进位影响,可以发挥DNA计算的并行性,减少DNA分子操作步骤,有助于误差控制。
为避免DNA计算中生化反应不完全对计算结果的不良影响,这里用PCR作为主要的操作手段实现了DNA计算过程,构造了基于PCR操作的计算操作模型,且计算过程中不需要限制性酶。基于该模型,给出了逻辑与算术运算的DNA编码方案以及DNA算法,并针对一个典型的NP-完全问题-最小顶点覆盖问题,给出了求解的DNA编码方案与DNA算法。PCR的应用使得计算操作简单可靠,DNA分子的分离仅与其长度有关,分离操作更为精确。
对DNA计算中NP-完全问题求解的指数爆炸问题,给出遗传算法的PCR构造。利用PCR操作来构造基本遗传算法中的变异算子、交叉算子以及选择算子,将遗传算法中的适应度函数映射为DNA双链分子的长度,并将用PCR构造的遗传算法应用于最小顶点覆盖问题的求解,给出了二进制位串的DNA编码方案,及问题求解的DNA算法与结果比较。与其它操作手段相比,用PCR构造遗传算法更为可行,且计算不需要预先生成解空间,可以避免指数爆炸问题。