1、DNA进化算法及其改进研究分类号：TP301.6 U D C：D10621-408-(2012) 2757-0密 级：公 开 编 号：2008073138DNA进化算法及其应用研究论文作者姓名：申请学位专业：自动化申请学位类别：工学学士指导教师姓名(职称)：论文提交日期：2012年06月06日DNA进化算法及其应用研究摘要DNA计算是一个崭新的研究领域，DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，对解决复杂的组合优化问题非常有效，本研究在借鉴遗传算法的基础上，模拟DNA编码的方式，改变传统遗传算法的0、1编码方式，实现了基本DNA进化算法，针对基本型DNA进化算法可能出现的
2、“早熟”问题(过早的收敛于某一局部最优值)，本设计提出对遗传操作概率自适应操作的方法，同时改变遗传进化操作的步骤，以期加快收敛速度。最后，针对基本型DNA进化算法寻优效果不理想的情况，利用模拟退火算法有着良好的局部寻优性能以及基本型DNA算法全局寻优性能较好的特点，提出一种与模拟退火算法结合的混合算法，即首先使用基本型DNA进化算法运算寻优，假设其运算结果参数在全局内比较接近理论值，然后用此求出的参数作为模拟退火步骤的初始搜索值，而最终结果在以上参数的附近经模拟退火操作随机寻找，并最终找到理论最优值，经大量的仿真试验表明，基本型算法大致能够达到设计要求，改进后的算法具有理想的寻优性能。关键词：
3、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
4、 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 basi
5、c 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 pap
6、er 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生物计算
7、机 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 采取自适应方法改进的DN
8、A进化算法实验结果 204.3 采用与模拟退火算法结合的混合算法实验结果 214.4 典型测试函数运行效果图 214.5 几种方法的比较 23结 论 24参考文献 25致 谢 26声 明 271 引言1994年，美国南加州大学的Aldeman教授在Science上发表了一篇关于DNA计算的开创性文章，其内容是运用生化实验的方法，解决了一个7节点的Hamilton路径(HP)问题。HP问题已被证明是难于计算的NP完备问题，但是Aldeman教授在实验室里运用生物工具成功地实现了该问题的求解，从而开创了DNA计算的新纪元，从此DNA计算也理所当然的迅速成为活跃的研究领域。他的基本过程是以DNA序列
9、作为信息编码的载体，利用分子生物学技术，以试管内控制酶作用下的DNA序列反应作为实现运算的过程，以反应后的DNA序列作为运算结果。在此之后，美国普林斯顿大学Lipton教授在1995年把DNA计算推广至求解另一类NP完备问题满意(satisfaction)问题(即SAT问题)。SAT问题是基于DNA生物实验方法的一种能解决NP完备问题的更一般方法的特殊情形(SAT是一个著名的NP问题的算法，需要指数时间)。在这个方法中，首先使用DNA链来表示所求问题所有可能的解，然后删除那些无效的解。通过对数目巨大的可能解空间的彻底搜索，在DNA计算的高效搜索机制的特点下，可快速得到所有的正确解1。所以我们可
10、以知道DNA计算其实就是一种模仿分子生物DNA的双螺旋结构和碱基互补配对原则的一门仿生科学，以该原则对信息进行编码，因为DNA计算无论在理论层次或是技术方面均是一门崭新的技术，因此DNA计算对传统计算方式都是一种挑战。近年来，随着国际顶级杂志诸如Science和Nature等对DNA计算的相继报道和有关DNA计算的国际专题研讨会议的召开，DNA很快而且已经成为一个极具开发价值的生物科学研究的前沿领域。虽然DNA计算从诞生到现在已经有十余年的时间了，而且DNA计算的研究也已经取得了初步的令人高兴的进展和成果，但是，随着人们不断的更深入的研究，DNA的计算并不像起初研究者们认为的那样乐观，针对DN
11、A计算的研究已经出现了一些问题或障碍，其中最大的莫过于如何克服DNA计算过程中所产生的“指数爆炸”问题；此外，DNA计算的理论本身仍然不是很成熟，只能解决一些简单的优化问题；最后，其运用的生物技术目前还没有达到足够尖端和精确的水平，因此难以应付实际工程领域中可能出现的各种复杂优化问题2。1.1 课题背景DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，能有效的解决复杂的组合优化问题，近年来受到了研究学者越来越多的关注。该算法通过模拟DNA的编码方式取代传统进化算法的0、1编码，具有种群多样性丰富、收敛速度快等特点。遗传算法则是一种在分子水平上模拟生物进化过程来用求解复杂问题的有效
12、算法，DNA计算是利用生物分子的各种生化反应来完成计算过程，两种很自然的具有某种特殊的关系，应该可以互相参考，用DNA编码表示系统携带的信息，模拟DNA分子的各种操作以发现和处理信息，在进化过程中不断获取和更新信息，既可以充分发挥开创性DNA计算的思想，又可以解决诸如自动控制、模式识别、决策问题、机器学习等工程领域中广泛存在的各种复杂优化问题。理论上DNA计算的实验应当在DNA计算机上进行，但是DNA计算机的制造与DNA计算一样还处于起始阶段，因而借助于遗传算法来研究DNA进化算法是可行的方法。1.2 国内外研究现状第一届有关DNA计算的国际研讨会议于1995年，在美国的普林斯顿大学举行，自此
13、之后，每年召开一次这样的国际研讨会。这些会议为DNA计算的研究提供了一个良好的交流平台。1998年，Paun等发表关于DNA计算学术专着的第一本书DNA计算新的计算模式，其归纳了之前大家研究的几个主要的DNA计算模型以及在数学理论的基础上的经验。2001年，E.shapiro率领的以色列科学家团队在自然杂志上发表了他们的研究结果，即利用DNA分子和DNA限制性内切酶达到了简化图灵机功能的，具有可编程的自动DNA 分子计算机模型。这显示了在生物计算机的研究上，取得了比较大的突破。2005年，Martynamos发表一篇题为理论与实验的计算的专著，系统地介绍了计算的历史和发展，并详细论述了迄今为止
14、的所有现有的理论模型和实验结果，为DNA计算提供了一份权威的参考资料，在中国，有关对DNA计算的研究已经逐渐蔓延开来。2000年，世界上第二个bio-x生命科学研究中心在上海交大成立，交大利用多学科交叉的优势，完成了国产第一个原型的“DNA计算机”的研究。华中科技大学分子生物学计算机研究所，成立于2001年，系中国最早从事分子生物学计算研究团队。北京大学的理论生物学中心正式成立于2001年9月，系由李政道先生倡议下成立，并已经开始进行对生物分子进化、DNA计算的探索研究。许进等人在2004年翻译并发表了一部Paun等关于DNA计算专著。2006年，首届生物计算理论及应用国际会议在武汉召开。目前
15、，关于DNA计算与DNA计算机的研究发展速度非常惊人，无论是理论研究上，还是实验研究都取得了很大的进展。同时，也有学者开始将DNA计算和遗传算法、神经网络、混沌系统等智能计算方法相结合。本文研究的就是将DNA计算融合于遗传算法中成为DNA进化算法。1.3本课题研究的意义有关DNA计算的相关应用，主要有以下几个方面：1.3.1 DNA生物计算机任何材质的计算机，无论是以碳为基础或是以硅为基础的，都必须具备一种普通的数学计算能力，其中最为基础的问题莫过于进行四则运算了。和电子计算机相比较，现在研究的DNA分子计算机还处于起始萌芽阶段，发展快速的执行分子计算的基本操作，如加减乘除操作等等，对研制生物
16、计算机，有着重要的意义。Guamieri等首次应用DNA重组技术提出了分子计算的一位加法运算。随后，他们又利用连续引物扩增反应进行二进制加法的布尔逻辑操作。事实上，虽然他们已经通过一个简单示例说明了上述DNA分子运算的可行性，但是DNA生物分子运算仍然主要受限于以下两点:(l)只能达到两个数字相加的效果，而不能体现DNA分子计算应该具有的海量并行处理能力 ;(2)DNA分子的运算操作，不允许重复，操作的结果根据输入时的编码。另外，研究人员提出了各种各样的DNA分子计算方法可以用并行方式执行,并允许系列操作。2001年，以shapiro为首的研究团队发表了一篇相关的研究论文，足以令所有关心生物计
17、算机研究的人都为之高兴，该团队用携带遗传信息的双链DNA分子作为数据存储的载体，数据处理器则是用DNA分子的限制性内切酶，并在试管实验中使用分子生物学反应实现了一个简化的图灵机。不夸张的说，这是一个与Adleman在 1994年实现的的研究成果可以相提并论的重大成就。紧接着在接下来两年内，同样是这一批科学家分别在PNAs和Nature上发表了两篇研究论文，改进优化了他们之前获得的DNA分子图灵机模型并成功的应用于智能化药物的研究方面。但是，要在实际应用中使用生物计算机或者说要取代目前电子计算机在实际应用中的位置，仍然有很多理论和技术方面的问题需要一个个逐步解决。如对DNA分子的存取速度、生物计
18、算反应中的单分子操作技术、生物计算反应是否可靠、如何实现通用的可编程生物计算方法以及生物计算机的人机交互界面等问题，都是很关键的需尽快解决的问题。1.3.2 DNA计算与软计算的集成生物信息系统向生物智能的方向发展可导向“计算智能”，这些计算智能技术用于计算领域可看成“软计算”。现有的计算智能主要包括神经网络、进化计算、免疫计算及模拟人类大脑思维方式的模糊系统等，一直是智能科学领域的研究热点，且已经被广泛应用于各个领域。但到目前为止，计算智能的理论研究只是停留在对生物系统的简单模拟，对生物系统的研究结果也仅局限于理解生物过程、仿真生命、计算模型、分布计算及智能机器人等方面。如遗传算法，虽然在不
19、可微函数、复杂及非线性系统寻优等问题上显示出突出的作用，但其实质是对生物进化的一种简单抽象，即基于“0”和“1”编码的信息模型，不能表达丰富的遗传信息，且遗传信息对生物体的生长、发育的调控作用也没有在传统遗传算法的计算模型中反映出来，尤其是起关键作用的DNA编码机理和调控作用在现有的计算智能中没有体现出来。DNA的生物背景使我们能够进一步的分析和模仿遗传信息调控系统的自生成、自组织功能，引入基因工程机理改造系统结构而和参数，实现基于遗传机理的在线优化，从而建立分子水平的基因DNA控制机理的遗传信息模型。1.4 本课题研究方法本设计首先对基本DNA进化算法进行理论分析，在实现基本算法的基础上，发
20、现算法存在的不足，针对算法中各种操作的概率值选择，改变常用的赋以恒定大小的方法，采用自适应的方法，同时，针对传统遗传算法和DNA进化算法全局内寻优效果不佳的特点，提出了DNA进化算法和模拟退火算法结合的构想，针对典型的复杂测试函数，通过多次仿真实验比较原算法和改进算法的结果，证实算法的有效性和可行性。2 研究内容2.1 遗传算法简介遗传算法(Genetic AlgorithmsGA)是一类建立在自然选择和群体遗传机理基础上的通用问题求解算法，其研究的历史可以追溯于上世纪的1962年，由美国的密执安大学著名学者J.H.Holland教授提出来的。他从试图解释自然系统中生物的复杂适应过程入手，模拟
21、生物进化的机制来构造人工系统的模型。在此之后经过不到30年的发展，遗传算法已经取得了较为丰硕的应用成果，尤其是最近十年来在全球范围内形成的研究进化计算的热潮，人们逐渐意识到传统人工智能方法的局限性，以及后来的人工生命研究兴起，使得遗传算法受到广泛的关注。从1985年在美国卡耐基梅隆大学召开的第一届遗传算法会议(International Conference on Genetic Algorithms:ICCGA85),到1997年5月IEEE的Transaction on Evolutionary Computation创刊，遗传算法也由早期的主要研究组合优化问题以及复杂函数优化问题求解扩展
22、到遍及科学、工程、商业等领域，有着良好的应用前景3。2.1.1 遗传算法的生物学基础首先，为了更好的理解遗传算法，我们在这里先了解一下有关生物进化和遗传学方面的有关基本知识。众所周知，生物进化的基本步骤包括生长，繁殖，新陈代谢和遗传变异。所谓“生命”正是个体不断进化的累积，现代的生物是在长期复杂进化过程中最终得以发展起来的。达尔文(1858)年用自然选择(natural selection)来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：(1)遗传(heredity) 这是生物的普遍特征，亲代把生物信息交给子代，子代按照所得信息而发育，分化，因而子代总是和亲代具有相同和相似的性状
23、。生物有这个特征，物种才能稳定存在。(2)变异(variation) 亲代和子代之间以及子代与不同个体之间总是有些差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多 样性的根源。(3)生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断的进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变异被定向着一个方向积累，所有物种的个体性状逐渐偏离原来的的祖先，从而最终进化为新物种。这种逐渐积累变异方向的自然选择是一个长期的缓慢的过程，是不间断的4。1866年奥地利科学家孟德尔发表了有着遗传
24、学上开篇巨著的植物杂交实验的论文，两个遗传学上的基本规律被他首次提出来分离率和自由组合率，这使得遗传学从此步入科学性。20世纪20年代以后，随着遗传学的发展，一些科学家用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论，形成了现代综合进化论。达尔文进化论和孟德尔的遗传学说正是遗传算法基本思想的借鉴和来源。作为达尔文进化论最重要的适者生存原理认为：首先，所有的物种是一个动态的过程并不断适应环境的。物种的后代又不断的继承其基本的特征和优点，但继承的同时后代由于变异等原因又会出现不同于父代的性状出现。基因遗传原理是孟德尔的遗传学说的核心，他认为遗传广泛存在于细胞中是以密码的方式，以基因的方式
25、包含与物种的染色体之内。不同的基因在其不同的位置上存在一种决定生物性状的物质。所以，每个基因产生的个体对环境具有某种适应性，基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。假设一长度为M的n个二进制编码串bi(i=1,2,3，n)组成了GA的初始种群。每串中，每个二进制编码信息就体现为染色体的基因。根据生物常用的进化术语，算法实现过程对群体的操作有以下三种： (1)选择(selection) 从初始群体中以一定的概率选择出若干个体的操作，选择操作有时也可以称之为复制(reproducdon)操作，根据其适应度的大小所体现的优劣程度来决定下一代
26、是否被淘汰或是遗传，一般来说，适应度大的个体更有机会存在下去，而适应度较小的则被淘汰。 (2)交叉(crossover) 在选中用于繁殖下一代的个体中，对两个不同个体的相同位置的基因进行交换，从而产生新的个体。 (3)变异(Mutation) 在选中的个体中，对个体中的某些基因执行异向转化。在串中，如果某位基因为1，产生变异时就说把他变成0；反之则由0变成1。2.1.2 基本遗传算法基本遗传算法的基本结构如下所示。其中，欲求解问题的每个变量(即种群中每条染色体)都使用长度和数量分别为l何n的二进制染色体串集表示，搜索范围的下限和上限分别对应于编码0和一l。算法通过对随机产生的染色体群体进行遗传
27、操作如选择、交叉和变异使得整个种群向着适应度高的群体方向进化。 初始化，随机生成长度为L数量为n的的初始群体(0) 计算个体的适应度 While(不符合终止评价) 计算种群所有个体的适应度 计算种群所有个体的选择概率 选择N个个体作为交叉和变异操作的父本 For i0;iPc 将父本直接保存到下一代群体P(t+1)中 Else 进行交叉操作，得到两个子代 按照概率Pm对两个子代执行变异操作 将变异后子代保存到P(t+1)中 end end end 得到适应度最高的值 以上伪代码中包含了四个基本参数:交叉概率和变异概率，以及种群规模N和染色体长度L。因DNA算法考量的也是与染色体相关联的DNA链
28、，而且DNA链的编码方式完全可以借鉴遗传算法的染色体编码。所以从算法角度来看最容易与DNA计算结合的算法就是遗传算法，本设计的研究工作就是遗传此算法为基础，通过改变其编码进制数和增加DNA链之间的操作来进行研究的。2.2 基于DNA计算的进化算法 DNA的基本元素是核苷酸。核苷酸分为4 类碱基: 腺嘌呤(A ) 、 鸟嘌呤(G) 、 胞嘧啶(C) 和胸腺嘧啶(T )。DNA 是由两条很长的核苷酸链组成的。每条染色体则是一段呈双股螺旋状的DNA , A、T、C 和G 在DNA链中的不同排列序列造成了其能够表述大量丰富的遗传信息。DNA 指导蛋白质的形成过程如下： 先从DNA的一条链 上转录，接着
29、逆转录成mRNA。在mRNA 中不间断排列着由3 个相邻碱基为一组构成的密码子，这些密码子对应着不同的氨基酸，总共 4*4*4=64 种密码子对应20 种基本的氨基酸。氨基酸作为基本物质构成蛋白质。若把上述原理数学化，单股DNA 无疑可看做4个字母的集合,DNA 串的不同碱基可视为译码信息, 各种酶的操作便视之为在DNA 序列上的操作, 各种酶作为相应类型的操作算子, 对DNA链进行分子水平上的操作。即DNA计算模型可建立在形式表达且对其进行分子操作的基础上5。DNA 遗传算法是基于DNA 编码遗传模型进行遗传操作的。DNA 遗传算法的结构与常规遗传算法的结构类似。2.2.1 DNA计算中的基
30、本术语下面简单介绍一下DNA进化算法中使用的基本概念和术语。(1)DNA链(染色体) 遗传物质的主要载体，是多个遗传因子的集合，由A、T、C、G编码集合组成。(2)遗传因子(基因) 控制生物性状遗传物质的功能和结构的基本单位，可对应于待求解问题的某个参数和多个参数的组合。(3)遗传子座 DNA链上遗传因子的位置。各个位置决定所遗传的信息。(4)基因型 遗传因子组合的模型，是性状DNA链的内部表现。(5)表现型 由DNA链决定性状的外部表现，或者说，是根据基因型形成的个体。(6)个体 指DNA链带有特征的实体。(7)DNA汤(群体) DNA链带有特征的个体的集合，该集合内的DNA链的多少为DNA
31、汤的大小。(8)适应度 一条DNA链所代表的外部表现对外部环境的适应程度。(9)编码 从表现型到基因型的映射。(10)译码 从基因型到表现型的映射。(11)选择 指以一定的概率从DNA汤中选择若干对DNA链的操作。选择的目的是使适应度大的DNA链有更多繁殖后代的机会，从而使优良特性得以遗传，他体现了自然界适者生存的思想。 (12)交叉 将两条DNA链进行互换重组的操作。交叉是DNA进化算法的核心。只有不断的交叉，才能不断的产生新的个体，从而得到优秀的个体。从信息论的观点看，交叉是一种信息交换并产生新信息的过程，交叉的同时也创造了新的信息。交叉的方式有单点、多点以及最近遗传学讨论的基因转移等多种方式。(13)变异 让DNA链中的遗传因子以一定的概率突然变化的操作。变异的目的是使DNA进化算法具有局部随机搜索功能，维持DNA汤多样性，避免出现早熟现象而过早地收敛。DNA链的变异主要有碱基的突变和碱基序列的变化等。(14)倒位 在DNA链中两个随机选择位置之间的某些碱基的顺序进行倒位。它可以使在父代中离得很远的位在后代中靠在一起，相当于重新定义基因块。2.2.2 有关对DNA进化算法的假设DNA进化
