《DNA进化算法及其改进研究》由会员分享，可在线阅读，更多相关《DNA进化算法及其改进研究（31页珍藏版）》请在金锄头文库上搜索。
1、word分类号：UDC：D10621-408-(2012)2757-0密 级：公 开编 号：2008073138DNA进化算法与其应用研究论文 申请学位专业：自动化申请学位类别：工学学士指导教师(职称)：论文提交日期：2012年06月06日DNA进化算法与其应用研究摘要DNA计算是一个崭新的研究领域，DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，对解决复杂的组合优化问题非常有效，本研究在借鉴遗传算法的根底上，模拟DNA编码的方式，改变传统遗传算法的0、1编码方式，实现了根本DNA进化算法，针对根本型DNA进化算法可能出现的“早熟问题(过早的收敛于某一局部最优值)，本设计提出对
2、遗传操作概率自适应操作的方法，同时改变遗传进化操作的步骤，以期加快收敛速度。最后，针对根本型DNA进化算法寻优效果不理想的情况，利用模拟退火算法有着良好的局部寻优性能以与根本型DNA算法全局寻优性能较好的特点，提出一种与模拟退火算法结合的混合算法，即首先使用根本型DNA进化算法运算寻优，假设其运算结果参数在全局比拟接近理论值，然后用此求出的参数作为模拟退火步骤的初始搜索值，而最终结果在以上参数的附近经模拟退火操作随机寻找，并最终找到理论最优值，经大量的仿真试验明确，根本型算法大致能够达到设计要求，改良后的算法具有理想的寻优性能。关键词：DNA计算；自适应算法；模拟退火算法 / Research
3、 on the DNA Algorithm and Its ApplicationsAbstractThe puting based on DNA is a new field of research,DNA evolutionary algorithm is a class of bionic optimization algorithm which based on biological DNA encoding and evolutionary mechanisms ,it is very effective to solve the plex bination optimization
4、 problem ,In this research, based on genetic algorithm for reference,we use the way of simulation of DNA-encoded to change the traditional genetic algorithm 0、1 encoding and achieved the basic DNA evolutionary algorithm, for the problem of Premature that the basic algorithm may arise,use the adaptiv
5、e probability instead of the fixed probability to achieve the purpose of high speed.At last ,Basic algorithm optimization result is not an ideal situation, the use of simulated annealing algorithm has a good local search performance characteristics, so this paper propose a hybrid algorithm that bine
6、d with the simulated annealing algorithm, experiments show that the algorithm has good optimization performance.Key Words: DNA puting; Adaptive algorithm; The simulated annealing algorithm目录论文总页数：27页1 引言11.1 课题背景11.2 国外研究现状221.3.1 DNA生物计算机31.3.2 DNA计算与软计算的集成31.4 本课题研究方法42 研究容42.1 遗传算法简介42.1.1 遗传算法的生
7、物学根底42.1.2 根本遗传算法62.2 基于DNA计算的进化算法72.2.1 DNA计算中的根本术语72.2.2 有关对DNA进化算法的假设82.2.3 DNA进化算法的结构82.2.4 DNA进化算法与常规遗传算法的比拟132.2.5 根本DNA算法的实现143改良方法研究143.1 自适应DNA进化算法153.2 与模拟退火算法结合的DNA算法164 研究结果184.1 根本算法的实验结果204.2 采取自适应方法改良的DNA进化算法实验结果204.3 采用与模拟退火算法结合的混合算法实验结果214.4 典型测试函数运行效果图214.5 几种方法的比拟23结 论24参考文献25致 26
8、声 明271 引言1994年，美国南加州大学的Aldeman教授在Science上发表了一篇关于DNA计算的开创性文章，其容是运用生化实验的方法，解决了一个7节点的Hamilton路径(HP)问题。HP问题已被证明是难于计算的NP完备问题，但是Aldeman教授在实验室里运用生物工具成功地实现了该问题的求解，从而开创了DNA计算的新纪元，从此DNA计算也理所当然的迅速成为活跃的研究领域。他的根本过程是以DNA序列作为信息编码的载体，利用分子生物学技术，以试管控制酶作用下的DNA序列反响作为实现运算的过程，以反响后的DNA序列作为运算结果。在此之后，美国普林斯顿大学Lipton教授在1995年把
9、DNA计算推广至求解另一类NP完备问题满意(satisfaction)问题(即SAT问题)。SAT问题是基于DNA生物实验方法的一种能解决NP完备问题的更一般方法的特殊情形(SAT是一个著名的NP问题的算法，需要指数时间)。在这个方法中，首先使用DNA链来表示所求问题所有可能的解，然后删除那些无效的解。通过对数目巨大的可能解空间的彻底搜索，在DNA计算的高效搜索机制的特点下，可快速得到所有的正确解1。所以我们可以知道DNA计算其实就是一种模仿分子生物DNA的双螺旋结构和碱基互补配对原如此的一门仿生科学，以该原如此对信息进展编码，因为DNA计算无论在理论层次或是技术方面均是一门崭新的技术，因此D
10、NA计算对传统计算方式都是一种挑战。近年来，随着国际顶级杂志诸如Science和Nature等对DNA计算的相继报道和有关DNA计算的国际专题研讨会议的召开，DNA很快而且已经成为一个极具开发价值的生物科学研究的前沿领域。虽然DNA计算从诞生到现在已经有十余年的时间了，而且DNA计算的研究也已经取得了初步的令人高兴的进展和成果，但是，随着人们不断的更深入的研究，DNA的计算并不像起初研究者们认为的那样乐观，针对DNA计算的研究已经出现了一些问题或障碍，其中最大的莫过于如何克制DNA计算过程中所产生的“指数爆炸问题；此外，DNA计算的理论本身仍然不是很成熟，只能解决一些简单的优化问题；最后，其运
11、用的生物技术目前还没有达到足够尖端和准确的水平，因此难以应付实际工程领域中可能出现的各种复杂优化问题2。1.1 课题背景DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，能有效的解决复杂的组合优化问题，近年来受到了研究学者越来越多的关注。该算法通过模拟DNA的编码方式取代传统进化算法的0、1编码，具有种群多样性丰富、收敛速度快等特点。遗传算法如此是一种在分子水平上模拟生物进化过程来用求解复杂问题的有效算法，DNA计算是利用生物分子的各种生化反响来完成计算过程，两种很自然的具有某种特殊的关系，应该可以互相参考，用DNA编码表示系统携带的信息，模拟DNA分子的各种操作以发现和处理信息
12、，在进化过程中不断获取和更新信息，既可以充分发挥开创性DNA计算的思想，又可以解决诸如自动控制、模式识别、决策问题、机器学习等工程领域中广泛存在的各种复杂优化问题。理论上DNA计算的实验应当在DNA计算机上进展，但是DNA计算机的制造与DNA计算一样还处于起始阶段，因而借助于遗传算法来研究DNA进化算法是可行的方法。1.2 国外研究现状第一届有关DNA计算的国际研讨会议于1995年，在美国的普林斯顿大学举行，自此之后，每年召开一次这样的国际研讨会。这些会议为DNA计算的研究提供了一个良好的交流平台。1998年，Paun等发表关于DNA计算学术专着的第一本书DNA计算新的计算模式，其归纳了之前大
13、家研究的几个主要的DNA计算模型以与在数学理论的根底上的经验。率领的以色列科学家团队在自然杂志上发表了他们的研究结果，即利用DNA分子和DNA限制性切酶达到了简化图灵机功能的，具有可编程的自动DNA 分子计算机模型。这显示了在生物计算机的研究上，取得了比拟大的突破。2005年，Martynamos发表一篇题为理论与实验的计算的专著，系统地介绍了计算的历史和开展，并详细论述了迄今为止的所有现有的理论模型和实验结果，为DNA计算提供了一份权威的参考资料，在中国，有关对DNA计算的研究已经逐渐蔓延开来。2000年，世界上第二个bio-x生命科学研究中心在交大成立，交大利用多学科交叉的优势，完成了国产
14、第一个原型的“DNA计算机的研究。华中科技大学分子生物学计算机研究所，成立于2001年，系中国最早从事分子生物学计算研究团队。大学的理论生物学中心正式成立于2001年9月，系由政道先生倡议下成立，并已经开始进展对生物分子进化、DNA计算的探索研究。许进等人在2004年翻译并发表了一部Paun等关于DNA计算专著。2006年，首届生物计算理论与应用国际会议在召开。目前，关于DNA计算与DNA计算机的研究开展速度非常惊人，无论是理论研究上，还是实验研究都取得了很大的进展。同时，也有学者开始将DNA计算和遗传算法、神经网络、混沌系统等智能计算方法相结合。本文研究的就是将DNA计算融合于遗传算法中成为
15、DNA进化算法。有关DNA计算的相关应用，主要有以下几个方面：1.3.1 DNA生物计算机任何材质的计算机，无论是以碳为根底或是以硅为根底的，都必须具备一种普通的数学计算能力，其中最为根底的问题莫过于进展四如此运算了。和电子计算机相比拟，现在研究的DNA分子计算机还处于起始萌芽阶段，开展快速的执行分子计算的根本操作，如加减乘除操作等等，对研制生物计算机，有着重要的意义。Guamieri等首次应用DNA重组技术提出了分子计算的一位加法运算。随后，他们又利用连续引物扩增反响进展二进制加法的布尔逻辑操作。事实上，虽然他们已经通过一个简单示例说明了上述DNA分子运算的可行性，但是DNA生物分子运算仍然主要受限于以下两点:(l)只能达到两个数字相加的效果，而不能表现DNA分子计算应该具有的海量并行处理能力 ;(2)DNA分子的运算操作，不允许重复，操作的结果根据输入时的编码。另外，研究人员提出了各种各样的DNA分子计算方法可以用并行方式执行,并允许系列操作。2001年，以shapiro为首的研究团队发表了一篇相关的研究论文，足以令所有关心生物计算机研究的人都为之高兴，该团队用携带遗传信息的双链DNA分子作为数据存储的载体，数据处理器如此是用DNA分子的限制
