DNA进化算法及其改进研究

分类号：分类号：TP301.6TP301.6 U U D D C C：D10621-408-(2012)D10621-408-(2012) 2757-02757-0 密密 级：公级：公 开开 编编 号：号：20080731382008073138 DNA 进化算法及其应用研究进化算法及其应用研究 论文作者姓名：论文作者姓名： 申请学位专业：申请学位专业：自动化自动化 申请学位类别：申请学位类别：工学学士工学学士 指指导导教教师师姓姓名名 ( (职职称称 ) )： 论文提交日期：论文提交日期：20122012 年年 0606 月月 0606 日日 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 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 引言.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 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.11.1 课题背景课题背景 DNA 进化算法是基于生物 DNA 编码和进化机制的一类仿生优化算法，能 有效的解决复杂的组合优化问题，近年来受到了研究学者越来越多的关注。该 算法通过模拟 DNA 的编码方式取代传统进化算法的 0、1 编码，具有种群多样 性丰富、收敛速度快等特点。 遗传算法则是一种在分子水平上模拟生物进化过程来用求解复杂问题的有 效算法，DNA 计算是利用生物分子的各种生化反应来完成计算过程，两种很自 然的具有某种特殊的关系，应该可以互相参考，用 DNA 编码表示系统携带的 信息，模拟 DNA 分子的各种操作以发现和处理信息，在进化过程中不断获取 和更新信息，既可以充分发挥开创性 DNA 计算的思想，又可以解决诸如自动 控制、模式识别、决策问题、机器学习等工程领域中广泛存在的各种复杂优化 问题。理论上 DNA 计算的实验应当在 DNA 计算机上进行，但是 DNA 计算机 的制造与 DNA 计算一样还处于起始阶段，因而借助于遗传算法来研究 DNA 进 化算法是可行的方法。 1.21.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.31.3 本课题研究的意义本课题研究的意义 有关 DNA 计算的相关应用，主要有以下几个方面： 1.3.11.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.21.3.2 DNA 计算与软计算的集成计算与软计算的集成 生物信息系统向生物智能的方向发展可导向“计算智能” ，这些计算智能技 术用于计算领域可看成“软计算” 。现有的计算智能主要包括神经网络、进化计 算、免疫计算及模拟人类大脑思维方式的模糊系统等，一直是智能科学领域的 研究热点，且已经被广泛应用于各个领域。但到目前为止，计算智能的理论研 究只是停留在对生物系统的简单模拟，对生物系统的研究结果也仅局限于理解 生物过程、仿真生命、计算模型、分布计算及智能机器人等方面。如遗传算法， 虽然在不可微函数、复杂及非线性系统寻优等问题上显示出突出的作用，但其 实质是对生物进化的一种简单抽象，即基于“0”和“1”编码的信息模型，不能表 达丰富的遗传信息，且遗传信息对生物体的生长、发育的调控作用也没有在传 统遗传算法的计算模型中反映出来，尤其是起关键作用的 DNA 编码机理和调 控作用在现有的计算智能中没有体现出来。 DNA 的生物背景使我们能够进一步的分析和模仿遗传信息调控系统的自生 成、自组织功能，引入基因工程机理改造系统结构而和参数，实现基于遗传机 理的在线优化，从而建立分子水平的基因 DNA 控制机理的遗传信息模型。 1.41.4 本课题研究方法本课题研究方法 本设计首先对基本 DNA 进化算法进行理论分析，在实现基本算法的基础 上，发现算法存在的不足，针对算法中各种操作的概率值选择，改变常用的赋 以恒定大小的方法，采用自适应的方法，同时，针对传统遗传算法和 DNA 进 化算法全局内寻优效果不佳的特点，提出了 DNA 进化算法和模拟退火算法结 合的构想，针对典型的复杂测试函数，通过多次仿真实验比较原算法和改进算 法的结果，证实算法的有效性和可行性。 2 2 研究内容研究内容 2.12.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.12.1.1 遗传算法的生物学基础遗传算法的生物学基础 首先，为了更好的理解遗传算法，我们在这里先了解一下有关生物进化和 遗传学方面的有关基本知识。 众所周知，生物进化的基本步骤包括生长，繁殖，新陈代谢和遗传变异。 所谓“生命”正是个体不断进化的累积，现代的生物是在长期复杂进化过程中 最终得以发展起来的。达尔文(1858)年用自然选择(natural selection)来解释物种 的起源和生物的进化，其自然选择学说包括以下三个方面： (1)遗传(heredity) 这是生物的普遍特征，亲代把生物信息交给子代，子代按照所 得信息而发育，分化，因而子代总是和亲代具有相同和相似的性状。生物有这 个特征，物种才能稳定存在。 (2)变异(variation) 亲代和子代之间以及子代与不同个体之间总是有些差异，这 种现象称为变异。变异是随机发生的，变异的选择和积累是生命多 样性的 根源。 (3)生存斗争和适者生存 自然选择来自繁殖过剩和生存斗争。由于弱肉强食的 生存斗争不断的进行，其结果是适者生存，具有适应性变异的个体被保留下来， 不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变 异被定向着一个方向积累，所有物种的个体性状逐渐偏离原来的的祖先，从而 最终进化为新物种。这种逐渐积累变异方向的自然选择是一个长期的缓慢的过 程，是不间断的4。 1866 年奥地利科学家孟德尔发表了有着遗传学上开篇巨著的植物杂交实 验的论文，两个遗传学上的基本规律被他首次提出来分离率和自由组合 率，这使得遗传学从此步入科学性。20 世纪 20 年代以后，随着遗传学的发展， 一些科学家用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论， 形成了现代综合进化论。 达尔文进化论和孟德尔的遗传学说正是遗传算法基本思想的借鉴和来源。 作为达尔文进化论最重要的适者生存原理认为：首先，所有的物种是一个动态 的过程并不断适应环境的。物种的后代又不断的继承其基本的特征和优点，但 继承的同时后代由于变异等原因又会出现不同于父代的性状出现。基因遗传原 理是孟德尔的遗传学说的核心，他认为遗传广泛存在于细胞中是以密码的方式， 以基因的方式包含与物种的染色体之内。不同的基因在其不同的位置上存在一 种决定生物性状的物质。所以，每个基因产生的个体对环境具有某种适应性， 基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰， 适应性高的基因结构得以保存下来。 假设一长度为 M 的 n 个二进制编码串 bi(i=1,2,3，n )组成了 GA 的 初始种群。每串中，每个二进制编码信息就体现为染色体的基因。根据生物常 用的进化术语，算法实现过程对群体的操作有以下三种： (1)选择(selection) 从初始群体中以一定的概率选择出若干个体的操作，选 择操作有时也可以称之为复制(reproducdon)操作，根据其适应度的大小所体现 的优劣程度来决定下一代是否被淘汰或是遗传，一般来说，适应度大的个体更 有机会存在下去，而适应度较小的则被淘汰。 (2)交叉(crossover) 在选中用于繁殖下一代的个体中，对两个不同个体的 相同位置的基因进行交换，从而产生新的个体。 (3)变异(Mutation) 在选中的个体中，对个体中的某些基因执行异向转化。 在串中，如果某位基因为 1，产生变异时就说把他变成 0；反之则由 0 变成 1。 2.1.22.1.2 基本遗传算法基本遗传算法 基本遗传算法的基本结构如下所示。其中，欲求解问题的每个变量(即种群 中每条染色体)都使用长度和数量分别为 l 何 n 的二进制染色体串集表示，搜索 范围的下限和上限分别对应于编码 0 和一 l。算法通过对随机产生的染色体群 l 2 体进行遗传操作如选择、交叉和变异使得整个种群向着适应度高的群体方向进 化。 初始化，随机生成长度为 L 数量为 n 的的初始群体(0) 计算个体的适应度 While(不符合终止评价) 计算种群所有个体的适应度 计算种群所有个体的选择概率 选择 N 个个体作为交叉和变异操作的父本 For i0;iPc 将父本直接保存到下一代群体 P(t+1)中 Else 进行交叉操作，得到两个子代 按照概率 Pm 对两个子代执行变异操作 将变异后子代保存到 P(t+1)中 end end end 得到适应度最高的值 以上伪代码中包含了四个基本参数:交叉概率和变异概率，以及种群 c p m p 规模 N 和染色体长度 L。因 DNA 算法考量的也是与染色体相关联的 DNA 链， 而且 DNA 链的编码方式完全可以借鉴遗传算法的染色体编码。所以从算法角 度来看最容易与 DNA 计算结合的算法就是遗传算法，本设计的研究工作就是 遗传此算法为基础，通过改变其编码进制数和增加 DNA 链之间的操作来进行 研究的。 2.22.2 基于基于 DNA 计算的进化算法计算的进化算法 DNA 的基本元素是核苷酸。核苷酸分为 4 类碱基: 腺嘌呤(A ) 、 鸟嘌呤 (G) 、 胞嘧啶(C) 和胸腺嘧啶(T )。DNA 是由两条很长的核苷酸链组成的。每 条染色体则是一段呈双股螺旋状的 DNA , A、T、C 和 G 在 DNA 链中的不同 排列序列造成了其能够表述大量丰富的遗传信息。DNA 指导蛋白质的形成过 程如下： 先从 DNA 的一条链 上转录，接着逆转录成 mRNA。在 mRNA 中不 间断排列着由 3 个相邻碱基为一组构成的密码子，这些密码子对应着不同的氨 基酸，总共 4*4*4=64 种密码子对应 20 种基本的氨基酸。氨基酸作为基本物 质构成蛋白质。 若把上述原理数学化，单股 DNA 无疑可看做 4 个字母的集合 ,DNA 串的不同碱基可视为译码信息, 各种酶的操作便视之为在 GC,T,A, DNA 序列上的操作, 各种酶作为相应类型的操作算子, 对 DNA 链进行分子水 平上的操作。即 DNA 计算模型可建立在形式表达且对其进行分 GC,T,A, 子操作的基础上5。 DNA 遗传算法是基于 DNA 编码遗传模型进行遗传操作的。DNA 遗传算 法的结构与常规遗传算法的结构类似。 2.2.1 DNA 计算中的基本术语计算中的基本术语 下面简单介绍一下 DNA 进化算法中使用的基本概念和术语。 (1)DNA 链(染色体) 遗传物质的主要载体，是多个遗传因子的集合，由 A、T、C、G 编码集合组成。 (2)遗传因子(基因) 控制生物性状遗传物质的功能和结构的基本单位，可对 应于待求解问题的某个参数和多个参数的组合。 (3)遗传子座 DNA 链上遗传因子的位置。各个位置决定所遗传的信息。 (4)基因型 遗传因子组合的模型，是性状 DNA 链的内部表现。 (5)表现型 由 DNA 链决定性状的外部表现，或者说，是根据基因型形成 的个体。 (6)个体 指 DNA 链带有特征的实体。 (7)DNA 汤(群体) DNA 链带有特征的个体的集合，该集合内的 DNA 链的 多少为 DNA 汤的大小。 (8)适应度 一条 DNA 链所代表的外部表现对外部环境的适应程度。 (9)编码 从表现型到基因型的映射。 (10)译码 从基因型到表现型的映射。 (11)选择 指以一定的概率从 DNA 汤中选择若干对 DNA 链的操作。选 择的目的是使适应度大的 DNA 链有更多繁殖后代的机会，从而使优良特性得 以遗传，他体现了自然界适者生存的思想。 (12)交叉 将两条 DNA 链进行互换重组的操作。交叉是 DNA 进化算法 的核心。只有不断的交叉，才能不断的产生新的个体，从而得到优秀的个体。 从信息论的观点看，交叉是一种信息交换并产生新信息的过程，交叉的同时也 创造了新的信息。交叉的方式有单点、多点以及最近遗传学讨论的基因转移等 多种方式。 (13)变异 让 DNA 链中的遗传因子以一定的概率突然变化的操作。变异 的目的是使 DNA 进化算法具有局部随机搜索功能，维持 DNA 汤多样性，避免 出现早熟现象而过早地收敛。DNA 链的变异主要有碱基的突变和碱基序列的变 化等。 (14)倒位 在 DNA 链中两个随机选择位置之间的某些碱基的顺序进行倒 位。它可以使在父代中离得很远的位在后代中靠在一起，相当于重新定义基因 块。 2.2.2 有关对有关对 DNA 进化算法的假设进化算法的假设 DNA 进化算法(DNA-GA)采取模仿 DNA 链编码，增加遗传算法的操作， 与遗传算法的模型有着参考借鉴的关系，故与遗传算法类似，可以对该模型提 出下列假设： (1) 每条 DNA 链是由 A、T、C 和 G 四种碱基不同的排列组成的一个固定 (或可变)长度的字符串，其中每一位都具有有限数目的等位基因。 (2) DNA 汤(群体)由有限条 DNA 链组成。 (3) 对任意一条 DNA 链都可进行不同的遗传操作。 (4) 每一条 DNA 链对应一相应的适应度，表示该 DNA 链生存与复制的能 力。适应度越大，表示其生存能力越强。 2.2.3 DNA 进化算法的结构进化算法的结构 如上所述，DNA 进化算法(DNA-GA)的结构类似于常规遗传算法。以下为 DNA-GA 求解具体问题的基本步骤。 (1)种群初始化及 DNA 链编码 使用 n 个具有随机编码的 DNA 链的群体组成 的初始世代群体(DNA 汤)P(t)。每条 DNA 链由 A、T、C、G 四种碱基结合构成， 可表示不同的基因。DNA-GA 初始化时，实际求解问题的设计参数是通过 来编码形成每一条 DNA 链。DNA 编码是整个算法的关键环节， GC,T,A, 后续的计算完全是基于初始编码的基础上完成的，DNA 链的长度和汤池的大小 也决定了最终问题求解的收敛速度和精度。DNA-GA 的任务就是从初始化后的 DNA 汤出发，模拟进化过程，经过多次的迭代计算选择出优秀的群体和个体， 最终满足求解问题的要求。 起始 初始化 实际问题的DNA 链编码 计算适应度 得到解？ 选择 交叉 变异 倒位结束 否 是 图 1 DNA 进化算法流程图 编码 本设计在 DNA 链编码过程中，用 0 代表 A，用 1 代表 T，用 2 代 表 C，用 3 代表 G。这样就把 DNA 链实现为一条四进制的数字码串，在实现算 法时，首先初始化 DNA 汤的过程中，利用 MATLAB 中 Rand 函数随机产生 0.0 至 1.0 之间的数据，不同范围内的数据统一规定为相应不同的碱基。如本算法 主程序中若随机数在 0.0 与 0.25 之间，碱基对应为 0；若随机数在 0.25 与 0.5 之间，碱基对应为 1；若随机数在 0.5 与 0.75 之间，碱基定义为 2，若随机数在 0.75 与 1.0 之间，碱基对应为 3。 编码机制 遗传算法中，常用的有二进制编码和浮点数编码两种机制， 本设计中采用二进制编码的原理，只是相应的改变为四进制编码。另浮点数编 码在这里不再表述。 假设群众中个体的数目为，表示第 代的第 个个体，。n i t xtiin， 2 , 1 每个个体用 位四进制表示。这样每个个体，,这样每个个体l i t x ml IBIB 1 , 0 基因位数目。个体可以表示为维的行向量，即 =mlL i t xml i t x 。第 代种群可以表示为一个 )() 1) 1()2() 1()() 1 (mli t lmi t li t li t li t i t xxxxxx t t X 的矩阵= 。个体的第 k 个长度为 的四进制码串化为实数mln t X T n ttt xxx 21i t xl 的解码函数为 (1) )4( 14 , 1 1 )( j t j jkli t l kk k i t x uv ukx）（ 式中和分别为第 k 个实数范围的上限和下限。 k v k u (2)适应度函数 常用的适应度函数有如下三种： 直接把要求的目标函数视之为适应度函数，即： 如目标函数为最大化问题 (2)()(xfxfFit 如目标函数为最小问题 (3)()(xfxfFit 显然采取这种适应度函数既简单又直观，但是也存在两个问题，一是一般 的轮盘赌选择中，对于概率有着非负的要求，这一点可能不能够满足；另有时 候待求解的函数在函数值的分布上相差较大，从而得到的平均适应度偏离理论 值较远，对种群的平均性能不利，影响算法的性能。 若目标函数为最小问题，则 (4) maxmax )(),( ,0 )( cxfxfc xfFit 其他 式中为的最大值估计。 max c)(xf 若目标函数为最大问题，则 (5) minmin )(,)( ,0 )( cxfcxf xfFit 其他 式中为的最小值估计。 max c)(xf 这种方法是对第一种方法的改进，可以称之为“界限构造法”，但存在的问 题是有时候存在界限预先估计困难，以至于不可能精确。 若目标函数为最小问题 (6) 0)(, 0 )(1 1 )( xfcc xfc xfFit， 若目标函数为最大问题 (7)0)(, 0, )(1 1 )( xfcc xfc xfFit 该方法类似于第二种方法，c 为目标函数界限的保守估计值。 本设计直接采用的是第一种适应度计算策略。 (3)选择 以适当的概率从 DNA 汤中选择出 m 个 DNA 链个体并作为)(tP 父本母本用于繁育后代，而产生的新个体投入到下一代。选择的意义在) 1( tP 于使那些适应度函数值大的 DNA 链有更多更大的留下来并参与下一代的机会， 这样优良特性便可以遗传下去，体现了大自然优胜劣汰的原理，与常规的标准 遗传算法类似，DNA-GA 算法选择操作常用的方法有适应度比例法、期望值法、 排位次序法、精华保存法和轮盘赌法。下面简单介绍一下常用的两种： 按比例的适应度分配：按比例的适应度也可称之为选择的蒙特卡罗法，是 利用比例于各个个体适应度的概率决定其子孙的去留的可能性，若某个个体 i， 其适应度为 fi ，则其被选取的概率表示为： (8) m i i i i f f p 1 轮盘赌选择法(roulette wheel selection ) 这是一种最简单的选择策略，表 1 表示了 11 个个体适应度、不同个体的选择概率和累积概率。为了选择出可作为 父本母本的个体，要对种群进行进行多轮选择。在每一轮中利用函数产生一个 0,1均匀随机数，并将该随机数的大小作为选择指针来确定哪些是被选个体， 如图 2 所示，如果第一轮随机数为 0.81，第 6 个个体累积概率为 0.82，则它被 选中，若第二产生的轮随机数为 0.32，则第二个个体累积概率为 0.34 的被选中； 依此原理类推，如第 3、4、5、6 轮随机数为 0.96，0.01,0.65,0.42，则第 9,1,5,3 个个体以此被选中。因为其对应的累积概率分别为 0.98、0.18、0.73、0.49。这 样经过这种办法选择产生的交配种群由以下个体组成：1、2、3、5、6、9。 表 1 轮盘赌选择法的选择概率计算 个体1234567891011 适应 度 2.01.81.61.41.21.00.80.60.40.20.1 选择 概率 0.180.160.150.130.110.090.070.060.030.020.0 累积 概率 0.180.340.490.620.730.820.890.950.981.001.00 0 个 体 0.18 0.49 0.62 0.730.820.341.00 0.95 1 2 345 6 第 四 轮 第 二 轮 第 六 轮 第 五 轮 第 一 轮 第 三 轮 图 2 轮盘赌选择法 (4)交叉 对于选中的用于繁殖后代的每一对 DNA 链个体，将其中部分 内容进行互换。交叉位置是随机产生的。通过交叉这种方法，凭借交叉点，产 生了新的 DNA 链，基因得以极大的改变，交叉分为单点交叉以及多点交叉等 好几种方式。而多点交叉又有即点交叉和标准交叉两种方式。图三给出的是 n 一个简单单点交叉的例子，如图： TGAGGCCGTA|GTACGATACGTAGAT AGTATGAACT|GCACGCCGTACTACT TGAGGCCGTA|GCACGCCGTACTACT AGTATGAACT|GTACGATACGTAGAT 图 4 单点交叉示意图 (5)变异 在 DNA 群体中以相应的概率随机的选取若干个 DNA 链个体， 对其中选中的 DNA 链个体，随机的选取某一位进行 DNA 链中的碱基排列顺序 的变化。DNA 链中的变化有碱基的替换、丢失和嵌入。碱基的取代有以下两种： 一种是相同类型的碱基之间的转换变异，如嘌呤替换嘌呤，嘧啶代替嘧啶，A 替换 G，T 替换 C；另一类是异类型碱基的互相替换：嘌呤被嘧啶替换，如 A 被 T 替换。图四是一个染色体中碱基 T 变成 A 的变异例子： TGAGGCCGTAGTACGATACGTAGAT TGAGGCCGTAGTACGAAACGTAGAT 图 4 点变异例子 (6)倒位 从 DNA 群中以一定的概率随机选取若干个 DNA 链个体，选中 这些 DNA 链个体后，随机的选中某两点位置，把他们之间的碱基顺序进行互 相倒位。倒位的目的在于尝试找到更好的进化特性的基因顺序。倒位操作是可 选的，根据问题的需要而定。图五给出的是倒位的例子： TGAGGCCGTA|GTACGATA|CGTAGAT TGAGGCCGTA|ATAGCATG|CGTAGAT 图