集装箱装载问题的一种DNA遗传算法

三维集装箱装载是一个复杂的组合优化问题,约束条件多,属于NP完全问题,求解难度大.在考虑方向性约束和稳定性约束的情况下,提出了一种DNA遗传算法（DNA-GA）,给出了有效的编码和解码方法。实例计算结果表明,利用DNA-GA解决装箱问题是行之有效的一种方法,对推广DNA计算在求解NP难解问题中的应用具有一定的意义。     

基于多级抽取的0-1整数规划问题的DNA算法

DNA计算是一种借助于分子生物技术进行计算的新方法,在解决一类困难问题特别是NP-完全问题上具有硅计算机无法比拟的优势,利用DNA计算求解0-1整数规划问题的研究具有重大的意义.基于多级分离模型解决0-1整数规划问题,且给出DNA算法.通过一个实例给出了操作的步骤.     

赋权图上优化问题的DNA计算方法研究(英文)

对赋权图上经典优化问题的DNA计算方法进行探讨,改进原有DNA计算模型中的权值编码方法,提出一些新的DNA编码方法及DNA算法．具体地说,通过设计赋权无向图的相对长度图给出了旅行商问题的一种相对长度DNA编码方法及DNA算法,通过设计赋权无向图的广义边图给出了中国邮递员问题的一种广义边图DNA编码方法及DNA算法,通过选取DNA序列的最佳逆补比对给出了最小生成树问题的一种基于逆补比对的DNA编码方法及DNA算法,通过设计从顶点覆盖问题到Hamilton回路问题的一种改进多项式变换给出了顶点覆盖问题的一种基于多项式变换的DNA编码方法及DNA算法．所设计的DNA计算方法提高了DNA计算中表示数值和处理数值的能力．     

最大匹配问题的粘贴DNA算法

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。     

基于聚类小生境遗传算法的DNA编码优化

DNA编码优化问题是DNA计算中的核心问题。分析DNA编码优化的约束条件,在单链DNA序列集合上引入h距离,将聚类小生境技术应用于小种群遗传算法的构造,对DNA编码优化问题进行求解。基于h距离定义DNA序列间的相似函数,将碱基字母编码为4进制整数、DNA编码序列作为个体编码为4进制整数向量、种群编码为4进制整数矩阵,基于模4算术运算,构造相应的遗传算子,并给出DNA编码序列的具体计算结果。实验结果表明,与现有DNA编码序列优化结果相比,该算法可得到更好的DNA编码序列且计算效率较高。     

DNA计算与DNA密码

DNA计算作为一种新型计算模式,目前在理论和实践方面取得了若干初步成就。得益于DNA计算,密码学新领域——DNA密码也得到一定发展。DNA密码的安全性可以不依赖于计算困难问题,并且能够充分利用DNA分子所具有的超高存储密度、超低的能量消耗以及超大规模并行计算潜力。本文介绍了DNA计算的基本原理,DNA密码的基本特征,给出DNA计算和DNA密码的实例,并简要分析目前存在的问题及未来的展望。     

基于纠错码编码理论的DNA编码研究*

作为一种新的计算模式,DNA计算有着强大的计算能力,编码问题在DNA计算中占据重要的位置,有效的编码设计能够提高DNA计算的可靠性。基于纠错码编码理论,提出了一种新的DNA编码方法,该方法可以找出具有一定长度且满足汉明距离约束的DNA编码序列。最后,给出了该算法的仿真,结果表明了该算法的有效性。     

一种基于编码等价变换和遗传算法的DNA序列优化设计

针对DNA计算中的DNA序列设计问题,基于6个DNA序列设计约束条件,将DNA序列设计问题转化为多目标优化问题,提出小生境遗传算法进行求解。算法利用DNA序列设计中的相似性约束与H-测度约束,在单链DNA序列集合上定义共享函数,利用两种类型的编码等价变换以及模4算术运算,构造了5个遗传算子,并给出具体的DNA序列设计结果。通过比较,算法可以得到质量更好的DNA序列,且在种群规模与进化代数方面具有更高的计算效率。     

DNA计算中编码序列的过滤函数研究

构造了用于DNA编码序列过滤的函数,并给出了DNA序列编码的算法,采用该文设计的过滤函数和算法所得到的DNA编码序列,能够满足一定的组合约束条件,并满足一定热力学条件,大大提高了DNA编码字的质量,有利于提高DNA计算的可靠性。     

一类特殊整数规划问题的DNA计算

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义．提出了约束方程组的“秩”以及约束方程的3种“约束补链”概念,并基于这些概念,利用在基于表面的DNA计算中采用荧光标记的策略,给出了一类特殊整数规划问题最优解的一种基于DNA计算的求解算法．新算法利用荧光猝灭技术来排除非解,从而得到满足约束条件的所有可行解,最后再通过比较所有可行解的目标函数值来求得问题的所有最优解．算法分析表明,新算法具有解读、编码简单和错误率低的特点。     

经典Ramsey数DNA计算模型(Ⅰ):位序列计算模型

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一．对于经典Ramsey数,至今只有9个Ramsey数得到解决．按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任．研究表明,DNA计算在求解困难的NP一完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解．全文共分两篇,该文属首篇,建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型,其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序．文中重点对该模型的机理与使用方法进行了分析研究．     

经典Ramsey数DNA计算模型(Ⅱ):基于位序列的DNA计算模型

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一．对于经典Ramsey数,至今只有9个Ramsey数得到解决．按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任．研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解．全文共分两篇,该文属第二篇,在首篇工作的基础上,建立了所谓的经典Ramsey数位序列DNA计算模型,文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论,并给出了使用该模型求解经典Ramsey数详细的方法与步骤．     

旅行商问题的闭环DNA算法

旅行商问题TSP是NP完全问题,在工程实践中有着广泛的应用,利用常规算法很难在多项式时间内解决。DNA计算是一种新兴的计算模式,与生俱来的强大并行计算能力使得它在解决众多NP问题上表现出了巨大的优势。尝试利用DNA计算中改进的闭环模型解决TSP问题。首先介绍了闭环DNA 计算模型及其改进;随后提出了一种基于改进的闭环模型求解TSP问题的算法,并对算法的实验过程进行了详细的描述;最后运用该算法解决了一个小规模的TSP问题算例,结果表明,该算法能在较低的时间复杂度内有效地解决TSP问题。     

构造对角Ramsey图的DNA算法设计*

Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题,使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸,穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法,该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。     

DNA编码问题及其复杂性研究*

高质量的DNA编码可以避免DNA分子间的非特异性杂交,提高DNA计算的有效性和可靠性。首先对DNA编码的约束条件进行归类,分析了各编码约束对编码质量的影响;然后研究了编码质量、编码数量、序列长度与DNA计算可靠性、有效性、可扩充性之间的关系;最后通过类比DNA编码问题和图的独立集问题,说明了求解最大DNA序列集合问题是NP完全的。     

基于联姻遗传算法的混合FloWshop提前/拖期调度问题

混合流水车间(Flowshop)提前／拖期调度问题的目标是4~_r-件的提前／拖期惩罚成本最小，这是一个NP完全问题，很难用一般的方法解决。文中首先给出了问题的数学模型，然后采用联姻遗传算法求解该问题。仿真结果表明此算法能有效地解决该类复杂调度问题。     

DNA自组装的可满足性问题模型

DNA自组装技术在DNA计算和纳米技术领域都发挥着极其重要的作用,许多小规模NP完全问题都可以通过自组装模型得以解决.文中以可满足问题为模型,通过构造范式中变量的特殊补链,使其与初始数据库中初始DNA链发生杂交反应,形成发夹结构,利用形成发夹结构的DNA链与没形成发夹结构的DNA链长度不同的特点,通过凝胶电泳将这些带发夹的DNA链提取出来;然后加入与这些特殊补链完全互补的DNA链,在一定温度下,通过碱基互补配对原则,发夹结构又将被重新打开.该模型充分利用了DNA分子间的自组装能力,在计算过程中只需要用到凝胶电泳操作,在一定程度上大大减少了因生物操作过多而引起的各种实验误差.     

智能仿生算法及其网络优化中的应用研究进展

网络优化问题是一类特殊的组合优化问题,很多问题找不到求最优解的多项式时间算法,属于NP困难问题;智能仿生类算法主要是模拟生物进化和生物群体的智能化方法,如人工神经网络、遗传算法、DNA分子算法、蚂蚁算法等,它们在解决NP问题上表现出得天独厚的优势,取得了诸多丰硕的成果。因此,该文系统地综述了近年来智能仿生算法及其网络优化中的应用研究进展和未来发展方向。     

基于免疫遗传算法的装箱问题求解

装箱是一类典型的ＮＰ完全问题．本文用一种免疫遗传算法来研究装箱问题的求解．免疫遗传算法在传统遗传算法的全局随机搜索基础上,借鉴生物免疫机制中抗体的多样性保持策略,大大提高了算法的群体多样性,实验表明,免疫遗传算法具有很好的全局收敛性,能有效解决装箱问题．     

Application of a novel IWO to the design of encoding sequences for DNA computing

Encoding and processing information in DNA-, RNA- and other biomolecule-based devices is an important requirement for DNA based computing with potentially important applications. To make DNA computing more reliable, much work has focused on designing the good DNA sequences. However, this is a bothersome task as encoding problem is an NP problem. In this paper, a new methodology based on the IWO algorithm is developed to optimize encoding sequences. Firstly, the mathematics models of constrained objective optimization design for encoding problems based on the thermodynamic criteria are set up. Then, a modified IWO method is developed by defining the colonizing behavior of weeds to overcome the obstacles of the original IWO algorithm, which cannot be applied to discrete problems directly. The experimental results show that the proposed method is effective and convenient for the user to design and select effective DNA sequences in silicon for controllable DNA computing.