遗传算法则是一种在分子水平上模拟生物进化过程来用求解复杂问题的有效算法，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计算的相关应用，主要有以下几个方面：
第2页 共27页
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”编码的信息模型，不能表达丰富的遗传信息，且遗传信息对生物体的生长、发育的调控作用也没有在传
第3页 共27页
统遗传算法的计算模型中反映出来，尤其是起关键作用的DNA编码机理和调控作用在现有的计算智能中没有体现出来。
DNA的生物背景使我们能够进一步的分析和模仿遗传信息调控系统的自生成、自组织功能，引入基因工程机理改造系统结构而和参数，实现基于遗传机理的在线优化，从而建立分子水平的基因DNA控制机理的遗传信息模型。
1.4 本课题研究方法
本设计首先对基本DNA进化算法进行理论分析，在实现基本算法的基础上，发现算法存在的不足，针对算法中各种操作的概率值选择，改变常用的赋以恒定大小的方法，采用自适应的方法，同时，针对传统遗传算法和DNA进化算法全局内寻优效果不佳的特点，提出了DNA进化算法和模拟退火算法结合的构想，针对典型的复杂测试函数，通过多次仿真实验比较原算法和改进算法的结果，证实算法的有效性和可行性。
2 研究内容
2.1 遗传算法简介
遗传算法(Genetic Algorithms—GA)是一类建立在自然选择和群体遗传机理基础上的通用问题求解算法，其研究的历史可以追溯于上世纪的1962年，由美国的密执安大学著名学者J.H.Holland教授提出来的。他从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。在此之后经过不到30年的发展，遗传算法已经取得了较为丰硕的应用成果，尤其是最近十年来在全球范围内形成的研究进化计算的热潮，人们逐渐意识到传统人工智能方法的局限性，以及后来的人工生命研究兴起，使得遗传算法受到广泛的关注。从1985年在美国卡耐基·梅隆大学召开的第一届遗传算法会议(International Conference on Genetic Algorithms:ICCGA'85),到1997年5月IEEE的Transaction on Evolutionary Computation创刊，遗传算法也由早期的主要研究组合优化问题以及复杂函数优化问题求解扩展到遍及科学、工程、商业等领域，有着良好的应用前景[3]。 2.1.1 遗传算法的生物学基础
首先，为了更好的理解遗传算法，我们在这里先了解一下有关生物进化和遗传学方面的有关基本知识。
众所周知，生物进化的基本步骤包括生长，繁殖，新陈代谢和遗传变异。所谓“生命”正是个体不断进化的累积，现代的生物是在长期复杂进化过程中最终得以发展起来的。达尔文(1858)年用自然选择(natural selection)来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面：
第4页 共27页
(1)遗传(heredity) 这是生物的普遍特征，亲代把生物信息交给子代，子代按照所得信息而发育，分化，因而子代总是和亲代具有相同和相似的性状。生物有这个特征，物种才能稳定存在。
(2)变异(variation) 亲代和子代之间以及子代与不同个体之间总是有些差异，这种现象称为变异。变异是随机发生的，变异的选择和积累是生命多 样性的根源。
(3)生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断的进行，其结果是适者生存，具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变异被定向着一个方向积累，所有物种的个体性状逐渐偏离原来的的祖先，从而最终进化为新物种。这种逐渐积累变异方向的自然选择是一个长期的缓慢的过程，是不间断的[4]。
1866年奥地利科学家孟德尔发表了有着遗传学上开篇巨著的《植物杂交实验》的论文，两个遗传学上的基本规律被他首次提出来——分离率和自由组合率，这使得遗传学从此步入科学性。20世纪20年代以后，随着遗传学的发展，一些科学家用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论，形成了现代综合进化论。
达尔文进化论和孟德尔的遗传学说正是遗传算法基本思想的借鉴和来源。作为达尔文进化论最重要的适者生存原理认为：首先，所有的物种是一个动态的过程并不断适应环境的。物种的后代又不断的继承其基本的特征和优点，但继承的同时后代由于变异等原因又会出现不同于父代的性状出现。基因遗传原理是孟德尔的遗传学说的核心，他认为遗传广泛存在于细胞中是以密码的方式，以基因的方式包含与物种的染色体之内。不同的基因在其不同的位置上存在一种决定生物性状的物质。所以，每个基因产生的个体对环境具有某种适应性，基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。
假设一长度为M的n个二进制编码串bi(i=1,2,3，·····，n)组成了GA的初始种群。每串中，每个二进制编码信息就体现为染色体的基因。根据生物常用的进化术语，算法实现过程对群体的操作有以下三种：
(1)选择(selection) 从初始群体中以一定的概率选择出若干个体的操作，选择操作有时也可以称之为复制(reproducdon)操作，根据其适应度的大小所体现的优劣程度来决定下一代是否被淘汰或是遗传，一般来说，适应度大的个体更有机会存在下去，而适应度较小的则被淘汰。
(2)交叉(crossover) 在选中用于繁殖下一代的个体中，对两个不同个体的
第5页 共27页
相同位置的基因进行交换，从而产生新的个体。
(3)变异(Mutation) 在选中的个体中，对个体中的某些基因执行异向转化。在串中，如果某位基因为1，产生变异时就说把他变成0；反之则由0变成1。 2.1.2 基本遗传算法
基本遗传算法的基本结构如下所示。其中，欲求解问题的每个变量(即种群中每条染色体)都使用长度和数量分别为l何n的二进制染色体串集表示，搜索范围的下限和上限分别对应于编码0和2l一l。算法通过对随机产生的染色体群体进行遗传操作如选择、交叉和变异使得整个种群向着适应度高的群体方向进化。
````` `````````````````````````````````````````````````
初始化，随机生成长度为L数量为n的的初始群体(0) 计算个体的适应度 While(不符合终止评价) 计算种群所有个体的适应度 计算种群所有个体的选择概率
选择N个个体作为交叉和变异操作的父本 For i<0;i 根据选择概率在P(t)中选择两个父本 r=rand if r>Pc 将父本直接保存到下一代群体P(t+1)中 Else 进行交叉操作，得到两个子代 按照概率Pm对两个子代执行变异操作 将变异后子代保存到P(t+1)中 end end end 得到适应度最高的值 ````````````````````````````````````````````````````````````` 以上伪代码中包含了四个基本参数:交叉概率pc和变异概率pm，以及种群规模N和染色体长度L。因DNA算法考量的也是与染色体相关联的DNA链，而且DNA链的编码方式完全可以借鉴遗传算法的染色体编码。所以从算法角度来看最容易与DNA计算结合的算法就是遗传算法，本设计的研究工作就是 第6页 共27页