分类号：TP301.6 U D C：D10621-408-(2012) 2757-0 密 级：公 开 编 号：2008073138
DNA进化算法及其应用研究
论文作者姓名： 申请学位专业： 申请学位类别： 指导教师姓名(职称)： 论文提交日期：
自动化 工学学士
2012年06月06日
DNA进化算法及其应用研究
摘要
DNA计算是一个崭新的研究领域，DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，对解决复杂的组合优化问题非常有效，本研究在借鉴遗传算法的基础上，模拟DNA编码的方式，改变传统遗传算法的0、1编码方式，实现了基本DNA进化算法，针对基本型DNA进化算法可能出现的“早熟”问题(过早的收敛于某一局部最优值)，本设计提出对遗传操作概率自适应操作的方法，同时改变遗传进化操作的步骤，以期加快收敛速度。最后，针对基本型DNA进化算法寻优效果不理想的情况，利用模拟退火算法有着良好的局部寻优性能以及基本型DNA算法全局寻优性能较好的特点，提出一种与模拟退火算法结合的混合算法，即首先使用基本型DNA进化算法运算寻优，假设其运算结果参数在全局内比较接近理论值，然后用此求出的参数作为模拟退火步骤的初始搜索值，而最终结果在以上参数的附近经模拟退火操作随机寻找，并最终找到理论最优值，经大量的仿真试验表明，基本型算法大致能够达到设计要求，改进后的算法具有理想的寻优性能。
关键词：DNA计算； 自适应算法； 模拟退火算法
Research on the DNA Algorithm and Its Applications
Abstract
The computing 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 complex combination optimization 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 \ that the basic algorithm may arise, use the adaptive 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 combined with the simulated annealing algorithm, experiments show that the algorithm has good optimization performance.
Key Words:
annealing algorithm
DNA computing; Adaptive algorithm; The simulated
目录
论文总页数：27页
1 引言............................................................................................................................................... 1
1.1 课题背景 ........................................................................................................................... 1 1.2 国内外研究现状 ............................................................................................................. 2 1.3本课题研究的意义 ............................................................................................................ 2
1.3.1 DNA生物计算机 ................................................................................................. 3 1.3.2 DNA计算与软计算的集成 ............................................................................... 3 1.4 本课题研究方法 ............................................................................................................... 4 2 研究内容 ....................................................................................................................................... 4
2.1 遗传算法简介 ................................................................................................................... 4
2.1.1 遗传算法的生物学基础 ....................................................................................... 4 2.1.2 基本遗传算法 ....................................................................................................... 6 2.2 基于DNA计算的进化算法 ............................................................................................ 7
2.2.1 DNA计算中的基本术语 ........................................................................................ 7 2.2.2 有关对DNA进化算法的假设 .............................................................................. 8 2.2.3 DNA进化算法的结构 ............................................................................................ 8 2.2.4 DNA进化算法与常规遗传算法的比较 ........................................................... 13 2.2.5 基本DNA算法的实现 ...................................................................................... 14
3 改进方法研究 ........................................................................................................................... 14
3.1 自适应DNA进化算法 ................................................................................................. 15 3.2 与模拟退火算法结合的DNA算法 ............................................................................. 16 4 研究结果 ..................................................................................................................................... 18
4.1 基本算法的实验结果 ...................................................................................................... 20 4.2 采取自适应方法改进的DNA进化算法实验结果 ....................................................... 20 4.3 采用与模拟退火算法结合的混合算法实验结果 .......................................................... 21 4.4 典型测试函数运行效果图 ............................................................................................ 21 4.5 几种方法的比较 ............................................................................................................ 23 结 论 ......................................................................................................................................... 24 参考文献 ......................................................................................................................................... 25 致 谢 ......................................................................................................................................... 26 声 明 ......................................................................................................................................... 27
1 引言
1994年，美国南加州大学的Aldeman教授在《Science》上发表了一篇关于DNA计算的开创性文章，其内容是运用生化实验的方法，解决了一个7节点的Hamilton路径(HP)问题。HP问题已被证明是难于计算的NP完备问题，但是Aldeman教授在实验室里运用生物工具成功地实现了该问题的求解，从而开创了DNA计算的新纪元，从此DNA计算也理所当然的迅速成为活跃的研究领域。他的基本过程是以DNA序列作为信息编码的载体，利用分子生物学技术，以试管内控制酶作用下的DNA序列反应作为实现运算的过程，以反应后的DNA序列作为运算结果。在此之后，美国普林斯顿大学Lipton教授在1995年把DNA计算推广至求解另一类NP完备问题—满意(satisfaction)问题(即SAT问题)。SAT问题是基于DNA生物实验方法的一种能解决NP完备问题的更一般方法的特殊情形(SAT是一个著名的NP问题的算法，需要指数时间)。在这个方法中，首先使用DNA链来表示所求问题所有可能的解，然后删除那些无效的解。通过对数目巨大的可能解空间的彻底搜索，在DNA计算的高效搜索机制的特点下，可快速得到所有的正确解[1]。
所以我们可以知道DNA计算其实就是一种模仿分子生物DNA的双螺旋结构和碱基互补配对原则的一门仿生科学，以该原则对信息进行编码，因为DNA计算无论在理论层次或是技术方面均是一门崭新的技术，因此DNA计算对传统计算方式都是一种挑战。近年来，随着国际顶级杂志诸如Science和Nature等对DNA计算的相继报道和有关DNA计算的国际专题研讨会议的召开，DNA很快而且已经成为一个极具开发价值的生物科学研究的前沿领域。
虽然DNA计算从诞生到现在已经有十余年的时间了，而且DNA计算的研究也已经取得了初步的令人高兴的进展和成果，但是，随着人们不断的更深入的研究，DNA的计算并不像起初研究者们认为的那样乐观，针对DNA计算的研究已经出现了一些问题或障碍，其中最大的莫过于如何克服DNA计算过程中所产生的“指数爆炸”问题；此外，DNA计算的理论本身仍然不是很成熟，只能解决一些简单的优化问题；最后，其运用的生物技术目前还没有达到足够尖端和精确的水平，因此难以应付实际工程领域中可能出现的各种复杂优化问题[2]。
1.1 课题背景
DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，能有效的解决复杂的组合优化问题，近年来受到了研究学者越来越多的关注。该算法通过模拟DNA的编码方式取代传统进化算法的0、1编码，具有种群多样性丰富、收敛速度快等特点。
第1页 共27页