DNA进化算法及其改进探讨

分类号：TP301.6 U D C：D10621-408-(2012) 2757-0密 级：公 开 编 号：2008073138DNA 进化算法及其应用研究论文作者姓名：申请学位专业： 自动化申请学位类别： 工学学士指 导 教 师 姓 名 (职 称 )：论文提交日期： 2012 年 06 月 06 日DNA 进化算法及其应用研究摘要DNA 计算是一个崭新的研究领域，DNA 进化算法是基于生物 DNA 编码和进化机制的一类仿生优化算法，对解决复杂的组合优化问题非常有效，本研究在借鉴遗传算法的基础上，模拟 DNA 编码的方式，改变传统遗传算法的 0、1编码方式，实现了基本 DNA 进化算法，针对基本型 DNA 进化算法可能出现的“早熟”问题(过早的收敛于某一局部最优值)，本设计提出对遗传操作概率自适应操作的方法，同时改变遗传进化操作的步骤，以期加快收敛速度。最后，针对基本型 DNA 进化算法寻优效果不理想的情况，利用模拟退火算法有着良好的局部寻优性能以及基本型 DNA 算法全局寻优性能较好的特点，提出一种与模拟退火算法结合的混合算法，即首先使用基本型 DNA 进化算法运算寻优，假设其运算结果参数在全局内比较接近理论值，然后用此求出的参数作为模拟退火步骤的初始搜索值，而最终结果在以上参数的附近经模拟退火操作随机寻找，并最终找到理论最优值，经大量的仿真试验表明，基本型算法大致能够达到设计要求，改进后的算法具有理想的寻优性能。关键词：DNA 计算； 自适应算法； 模拟退火算法Research on the DNA Algorithm and Its ApplicationsAbstractThe 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 “Premature“ 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: DNA computing; Adaptive algorithm; The simulated annealing algorithm目录论文总页数：27 页1 引言 .11.1 课题背景 .11.2 国内外研究现状 .21.3 本课题研究的意义 .21.3.1 DNA 生物计算机 .31.3.2 DNA 计算与软计算的集成 .31.4 本课题研究方法 .42 研究内容 .42.1 遗传算法简介 .42.1.1 遗传算法的生物学基础 .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声 明 .271 引言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 编码，具有种群多样性丰富、收敛速度快等特点。遗传算法则是一种在分子水平上模拟生物进化过程来用求解复杂问题的有效算法，DNA 计算是利用生物分子的各种生化反应来完成计算过程，两种很自然的具有某种特殊的关系，应该可以互相参考，用 DNA 编码表示系统携带的信息，模拟 DNA 分子的各种操作以发现和处理信息，在进化过程中不断获取和更新信息，既可以充分发挥开创性 DNA 计算的思想，又可以解决诸如自动控制、模式识别、决策问题、机器学习等工程领域中广泛存在的各种复杂优化问题。理论上 DNA 计算的实验应当在 DNA 计算机上进行，但是 DNA 计算机的制造与 DNA 计算一样还处于起始阶段，因而借助于遗传算法来研究 DNA 进化算法是可行的方法。1.2 国内外研究现状第一届有关 DNA 计算的国际研讨会议于 1995 年，在美国的普林斯顿大学举行，自此之后，每年召开一次这样的国际研讨会。这些会议为 DNA 计算的研究提供了一个良好的交流平台。1998 年，Paun 等发表关于 DNA 计算学术专着的第一本书DNA 计算新的计算模式 ，其归纳了之前大家研究的几个主要的 DNA 计算模型以及在数学理论的基础上的经验。2001 年，E.shapiro 率领的以色列科学家团队在自然杂志上发表了他们的研究结果，即利用 DNA分子和 DNA 限制性内切酶达到了简化图灵机功能的，具有可编程的自动 DNA 分子计算机模型。这显示了在生物计算机的研究上，取得了比较大的突破。2005 年，Martynamos 发表一篇题为理论与实验的计算的专著，系统地介绍了计算的历史和发展，并详细论述了迄今为止的所有现有的理论模型和实验结果，为 DNA 计算提供了一份权威的参考资料，在中国，有关对 DNA 计算的研究已经逐渐蔓延开来。2000 年，世界上第二个 bio-x 生命科学研究中心在上海交大成立，交大利用多学科交叉的优势，完成了国产第一个原型的“DNA 计算机”的研究。华中科技大学分子生物学计算机研究所，成立于 2001 年，系中国最早从事分子生物学计算研究团队。北京大学的理论生物学中心正式成立于2001 年 9 月，系由李政道先生倡议下成立，并已经开始进行对生物分子进化、DNA 计算的探索研究。许进等人在 2004 年翻译并发表了一部 Paun 等关于DNA 计算专著。2006 年，首届生物计算理论及应用国际会议在武汉召开。目前，关于 DNA 计算与 DNA 计算机的研究发展速度非常惊人，无论是理论研究上，还是实验研究都取得了很大的进展。同时，也有学者开始将 DNA 计算和遗传算法、神经网络、混沌系统等智能计算方法相结合。本文研究的就是将DNA 计算融合于遗传算法中成为 DNA 进化算法。1.3 本课题研究的意义有关 DNA 计算的相关应用，主要有以下几个方面：1.3.1 DNA 生物计算机任何材质的计算机，无论是以碳为基础或是以硅为基础的，都必须具备一种普通的数学计算能力，其中最为基础的问题莫过于进行四则运算了。和电子计算机相比较，现在研究的 DNA 分子计算机还处于起始萌芽阶段，发展快速的执行分子计算的基本操作，如加减乘除操作等等，对研制生物计算机，有着重要的意义。Guamieri 等首次应用 DNA 重组技术提出了分子计算的一位加法运算。随后，他们又利用连续引物扩增反应进行二进制加法的布尔逻辑操作。事实上，虽然他们已经通过一个简单示例说明了上述 DNA 分子运算的可行性，但是 DNA 生物分子运算仍然主要受限于以下两点 :(l)只能达到两个数字相加的效果，而不能体现 DNA 分子计算应该具有的海量并行处理能力 ;(2)DNA 分子的运算操作，不允许重复，操作的结果根据输入时的编码。另外，研究人员提出了各种各样的 DNA 分子计算方法可以用并行方式执行,并允许系列操作。2001 年，以 shapiro 为首的研究团队发表了一篇相关的研究论文，足以令所有关心生物计算机研究的人都为之高兴，该团队用携带遗传信息的双链 DNA 分子作为数据存储的载体，数据处理器则是用 DNA 分子的限制性内切酶，并在试管实验中使用分子生物学反应实现了一个简化的图灵机。不夸张的说，这是一个与 Adleman 在 1994 年实现的的研究成果可以相提并论的重大成就。紧接着在接下来两年内，同样是这一批科学家分别在 PNAs 和 Nature 上发表了两篇研究论文，改进优化了他们之前获得的 DNA 分子图灵机模型并成功的应用于智能化药物的研究方面。但是，要在实际应用中使用生物计算机或者说要取代目前电子计算机在实际应用中的位置，仍然有很多理论和技术方面的问题需要一个个逐步解决。如对 DNA 分子的存取速度、生物计算反应中的单分子操作技术、生物计算反应是否可靠、如何实现通用的可编程生物计算方法以及生物计算机的人机交互界面等问题，都是很关键的需尽快解决的问题。1.3.2 DNA 计算与软计算的集成生物信息系统向生物智能的方向发展可导向“计算智能” ，这些计算智能技术用于计算领域可看成“软计算” 。现有的计算智能主要包括神经网络、进化计算、免疫计算及模拟人类大脑思维方式的模糊系统等，一直是智能科学领域的研究热点，且已经被广泛应用于各个领域。但到目前为止，计算智能的理论研究只是停留在对生物系统的简单模拟，对生物系统的研究结果也仅局限于理解生物过程、仿真生命、计算模型、分布计算及智能机器人等方面。如遗传算法，虽然在不可微函数、复杂及非线性系统寻优等问题上显示出突出的作用，但其实质是对生物进化的一种简单抽象，即基于“0” 和 “1”编码的信息模型，不能表达丰富的遗传信息，且遗传信息对生物体的生长、发育的调控作用也没有在传统遗传算法的计算模型中反映出来，尤其是起关键作用的 DNA 编码机理和调控作用在现有的计算智能中没有体现出来。DNA 的生物背景使我们能够进一步的分析和模仿遗传信息调控系统的自生成、自组织功能，引入基因工程机理改造系统结构而和参数，实现基于遗传机理的在线优化，从而建立分子水平的基因 DNA 控制机理的遗传信息模型。1.4 本课题研究方法本设计首先对基本 DNA 进化算法进行理论分析，在实现基本算法的基础上，发现算法存在的不足，针对算法中各种操作的概率值选择，改变常用的赋以恒定大小的方法，采用自适应的方法，同时，针对传统遗传算法和 DNA 进化算法全局内寻优效果不佳的特点，提出了 DNA 进化算法和模拟退火算法结合的构想，针对典型的复杂测试函数，通过多次仿真实验比较原算法和改进算法的结果，证实算法的有效性和可行性。2 研究内容2.1 遗传算法简介遗传算法(Genetic AlgorithmsGA)是一类建立在自然选择和群体遗传机理基础上的通用问题求解算法，其研究的历史可以追溯于上世纪的 1962 年，由美国的密执安大学著名学者 J.H.Holland 教授提出来的。他从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。在此之后经过不到 30 年的发展，遗传算法已经取得了较为丰硕的应用成果，尤其是最近十年来在全球范围内形成的研究进化计算的热潮，人们逐渐意识到传统人工智能方法的局限性，以及后来的人工生命研究兴起，使得遗传算法受到广泛的关注。从 1985 年在美国卡耐基梅隆大学召开的第一届遗传算法会议(International Conference on Genetic Algorithms:ICCGA85),到 1997 年 5 月 IEEE的 Transaction on Evolutionary Computation 创刊，遗传算法也由早期的主要研究组合优化问题以及复杂函数优化问题求解扩展到遍及科学、工程、商业等领域，有着良好的应用前景 3。2.1.1 遗传算法的生物学基础首先，为了更好的理解遗传算法，我们在这里先了解一下有关生物进化和遗传学方面的有关基本知识。众所周知，生物进化的基本步骤包括生长，繁殖，新陈代谢和遗传变异。所谓“生命”正是个体不断进化的累积，现代的生物是在长期复杂进化过程中最终得以发展起来的。达尔文(1858)年用自然选择(natural selection)来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：(1)遗传(heredity) 这是生物的普遍特征，亲代把生物信息交给子代，子代按照所得信息而发育，分化，因而子代总是和亲代具有相同和相似的性状。生物有这个特征，物种才能稳定存在。(2)变异(variation) 亲代和子代之间以及子代与不同个体之间总是有些差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多 样性的根源。(3)生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断的进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变异被定向着一个方向积累，所有物种的个体性状逐渐偏离原来的的祖先，从而最终进化为新物种。这种逐渐积累变异方向的自然选择是一个长期的缓慢的过程，是不间断的 4。1866 年奥地利科学家孟德尔发表了有着遗传学上开篇巨著的植物杂交实验的论文，两个遗传学上的基本规律被他首次提出来分离率和自由组合率，这使得遗传学从此步入科学性。20 世纪 20 年代以后，随着遗传学的发展，一些科学家用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论，形成了现代综合进化论。达尔文进化论和孟德尔的遗传学说正是遗传算法基本思想的借鉴和来源。作为达尔文进化论最重要的适者生存原理认为：首先，所有的物种是一个动态的过程并不断适应环境的。物种的后代又不断的继承其基本的特征和优点，但继承的同时后代由于变异等原因又会出现不同于父代的性状出现。基因遗传原理是孟德尔的遗传学说的核心，他认为遗传广泛存在于细胞中是以密码的方式，以基因的方式包含与物种的染色体之内。不同的基因在其不同的位置上存在一种决定生物性状的物质。所以，每个基因产生的个体对环境具有某种适应性，基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。假设一长度为 M 的 n 个二进制编码串 bi(i=1,2,3，n )组成