旅行商问题的闭环DNA算法

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

基于环形DNA分子的一种求解最大集团的计算模型

文中提出了一种基于环形DNA分子的新型计算模型.该模型的核心构成包括环形DNA分子,链霉亲和素包被的磁珠及环化酶.通过应用该模型解决了一个5个顶点的最大团问题,证明了该模型的可行性.在整个计算过程中,真解的搜索是借助于磁珠和环化酶,DNA分子结构在线性和环形之间相互转化.环形DNA分子的应用极大地减少了计算所需的时间和空间,算法的时间和空间复杂度均为O(n+m).对于解决一个n个节点的最大团问题,这种算法和枚举型算法相比,在搜索过程中所需试管数较少,只需n+1个试管,而利用枚举型算法则需要2n个试管.另外,文中构建的非枚举型初始解空间大大提高了DNA计算机的存储和计算能力.在将来,这种新型的DNA计算模型或许会成为一种解决某些NP完全问题的有效工具.     

旅行商问题的DNA算法

旅行商问题是求仅一次遍访指定城市并返回出发城市的最短旅行路线的问题,它是图论中一个经典的NP完全问题,用电子计算机需要指数级的时间才能得到解决,该文基于分子生物技术并利用Adleman-Lipton模型给出旅行商问题的DNA算法,这个DNA算法理论上能在多项式的时间内解决这个NP完全问题。具体地对n个城市的旅行商问题,首先将它视为一个具有顶点和边的图,并将顶点、边分别用DNA链编码表示,边的方向通过顶点的编码获得;再将这些DNA链投放在试管中进行生物化学反应,利用DNA计算的高效并行性,通过基本的生物实验操作最后得到旅行商问题的解,其过程的复杂度为O(n)。该算法的创新之处在于表示城市和路径的DNA链长度的设计,能使我们在合理小的范围内寻找旅行商问题的解,较大地简化了问题的复杂度。     

一种最大匹配问题DNA计算算法

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.     

DNA计算与背包问题

该文通过对背包问题这一典型的NP完全问题的DNA计算研究,针对属于组合优化一类的ZKP问题给出了一种DNA计算方法,该算法解决了组合优化一类DNA计算的加权赋值问题,并根据DNA计算的特点给出了一般加权赋值型组合优化问题的DNA计算模式。     

求解TSP问题的一种改进蚁群算法

TSP问题是典型的NP—hard组合优化问题,用蚁群算法求解此问题存在搜索时间长,容易陷入局部最优解的不足。本文提出了一种改进的蚁群算法。该算法在蚁群算法中植入遗传算法,利用遗传算法生成信息素的分布,克服了蚁群算法中搜索时间长的缺陷。此外,在蚁群算法寻优中,采用交叉和变异的策略,改善了TSP解的质量。仿真结果显示,改进的蚁群算法是有效的。     

基于文化遗传算法的DNA编码序列设计

DNA编码问题是DNA计算的关键,然而,它已被证明为NP困难问题,通常采用优化算法求解。针对传统遗传算法缺乏有效指导,容易陷入局部极值的缺点,结合文化算法采用种群空间和信念空间的双层进化结构进行寻优,提出了一种基于遗传算法和文化算法的混合优化算法用于解决DNA编码问题。仿真结果表明该混合算法能有效地用于DNA编码序列设计。     

有向哈密尔顿路问题的研究

DNA计算是在分子水平上进行的计算,与传统的基于电子计算机的线性计算系统相比较,具有如可并发计算、耗能量小等无法比拟的特点。目前的研究主要集中在一些特定问题上,如NP完全问题,而这些问题在电子计算机上需要指数时间。本文利用已有的Adleman实验[1]解决有向图哈密尔顿路问题,给出了剪贴计算模型的形式化模型,并从算法复杂性角度分析其复杂性。     

一种新的动态TSP模型及其求解方法

TSP问题是经典的NP难问题,学者们已经提出很多有效的方法,但大多都是基于静态情形的,然而现实中的TSP问题基本为动态的,动态TSP将是一个更符合实际TSP问题的研究领域。提出了一种基于高斯扰动的动态TSP模型,设计了扰动响应算法,并对反序交叉算子做了改进。实验证明该算法的有效性和新模型的现实意义。     

基于闭环DNA的指派问题算法

给出了闭环DNA计算模型及其生化实验。用闭环DNA计算模型设计出了指派问题的DNA算法。首先对决策变量进行二维DNA编码来存放决策变量和效益值，然后通过有目的的终止技术和删除实验得到指派问题的全部可行解，最后通过电泳实验和检测实验获得最优指派问题的最优解。举例说明了算法的可行性。最后，为减少DNA编码数量和缩短DNA编码的码长，讨论了算法的两种改进方法。     

基于闭环DNA模型的八皇后问题算法

给出了闭环DNA计算模型及其基本生化实验,提出了基于闭环DNA的求解八皇后问题全部可行解的DNA算法,分析了算法的实现步骤及其实现方式并得到了全部的可行解。最后讨论了算法的复杂性。     

基于闭环DNA计算的最大独立集问题的算法

提出闭环DNA计算模型及其基本生化实验,给出解决最大独立集问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造所有最大独立集的构想,即通过多次删除实验使顶点集合逐步满足独立集的要求,最后达到最大独立集。该方法使得算法的设计简单明了。算法仅用到基本的删除实验,实现简捷、可靠。     

最小顶点覆盖问题的闭环DNA算法

提出了闭环DNA计算模型的基本概念及其基本生化实验,并给出了解决最小顶点覆盖问题的闭环DNA算法。在闭环DNA算法中,提出并实现了用删除实验直接构造顶点覆盖补集的构想;再通过电泳实验得到最小顶点覆盖的补集,由补集得到最小顶点覆盖。这使得算法的设计独特而新颖;由于算法仅用到基本的生化实验,这使得算法的实现简捷、可靠。     

基于猴群算法求解旅行商问题

鉴于旅行商问题是一个NP难问题,而猴群算法是一种新的群体智能优化算法,因此,利用猴群算法给出旅行商问题的求解。在分析了旅行商问题的特点后,采用整数编码的方式来表示猴群的位置,这样就解决了猴群算法在求解含有离散变量的组合优化问题时,算法中的爬过程失效的问题,有效地利用猴群算法求解旅行商问题。为了提高猴群算法的性能,在猴群算法的爬过程中,引入好动策略,给出改进算法,并将其应用到求解旅行商问题。在仿真实验中,与其他算法进行比较,结果表明利用改进猴群算法能够有效地求解旅行商问题。     

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

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

基于自适应蚁群算法的车辆路径问题研究

车辆路径问题(VRP)是物流研究领域中一个具有重要理论和现实意义的问题．蚁群算法是一种新型的模拟进化算法,可以很好地解决旅行商问题(TSP)．在分析VRP与TSP区别的基础上,构造了求解VRP的自适应蚁群算法．指出可行解问题是蚁群算法的关键问题,并重点对该问题进行了研究,提出了近似解可行化等解决策略．实验结果表明,自适应蚁群算法性能优良,能够有效地求解VRP问题．     

求解TSP算法

首先提出旅行商问题（TSP）,并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。     

DNA分子计算模型

The field of practical DNA computing opened in 1994 with Adleman's paper,in which a laboratory experi-ment involving DNA molecules was used to solve a small instance of the Hamiltonian Path problem. The characteris-tic of this computation is its powerful ability in parallelism,its huge storage and high energy efficiency. This paper mainly introduces the principles of DNA computing and the sticker computing model.     

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

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