DNA进化算法及其改进研究

分类号：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页

遗传算法则是一种在分子水平上模拟生物进化过程来用求解复杂问题的有效算法，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页

遗传此算法为基础，通过改变其编码进制数和增加DNA链之间的操作来进行研究的。

2.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个字母的集合

?{A,T,C,G},DNA 串的不同碱基可视为译码信息, 各种酶的操作便视之为

在DNA 序列上的操作, 各种酶作为相应类型的操作算子, 对DNA链进行分子水平上的操作。即DNA计算模型可建立在形式表达?{A,T,C,G}且对其进行分子操作的基础上[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)译码 从基因型到表现型的映射。

第7页 共27页

(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初始化时，实际求解问题的设计参数是通过?{A,T,C,G}来编码形成每一条DNA链。DNA编码是整个算法的关键环节，后续的计算完全是基于初始编码的基础上完成的，DNA链的长度和汤池的大小也决定了最终问题求解的收敛速度和精度。DNA-GA的任务就是从初始化后的

第8页 共27页

DNA汤出发，模拟进化过程，经过多次的迭代计算选择出优秀的群体和个体，最终满足求解问题的要求。

起始初始化实际问题的DNA链编码计算适应度得到解？是否选择交叉变异结束倒位

图1 DNA进化算法流程图

编码 本设计在DNA链编码过程中，用0代表A，用1代表T，用2代表C，用3代表G。这样就把DNA链实现为一条四进制的数字码串，在实现算法时，首先初始化DNA汤的过程中，利用MATLAB中Rand函数随机产生0.0至1.0之间的数据，不同范围内的数据统一规定为相应不同的碱基。如本算法

第9页 共27页

主程序中若随机数在0.0与0.25之间，碱基对应为0；若随机数在0.25与0.5之间，碱基对应为1；若随机数在0.5与0.75之间，碱基定义为2，若随机数在0.75与1.0之间，碱基对应为3。

编码机制 遗传算法中，常用的有二进制编码和浮点数编码两种机制，本设计中采用二进制编码的原理，只是相应的改变为四进制编码。另浮点数编码在这里不再表述。

1,2，?，n?。假设群众中个体的数目为n，xti表示第t代的第i个个体，i??每个个体用l位四进制表示。这样每个个体xti??IB?，IB??0,1?,这样每个个体

ml基因位数目L?ml。个体xti可以表示为ml维的行向量，即

xti=xt?xtxt?i(1)i(l)i(l?1)n?ml的矩阵Xt= xt1xt2?xtn。个体xti的第k个长度为l的四进制码串化为实数

??xti(2l)?xti((m?1)l?1)?xti(ml)。第t代种群Xt可以表示为一个

??T的解码函数?为

tvk?uki(kl?j)j?1?（x,k）?uk?(x?4) (1) ?tl4?1j?1式中vk和uk分别为第k个实数范围的上限和下限。

it(2)适应度函数

常用的适应度函数有如下三种：

? 直接把要求的目标函数视之为适应度函数，即：

如目标函数为最大化问题 Fit(f(x))?f(x) (2) 如目标函数为最小问题 Fit(f(x))??f(x) (3) 显然采取这种适应度函数既简单又直观，但是也存在两个问题，一是一般的轮盘赌选择中，对于概率有着非负的要求，这一点可能不能够满足；另有时候待求解的函数在函数值的分布上相差较大，从而得到的平均适应度偏离理论值较远，对种群的平均性能不利，影响算法的性能。

? 若目标函数为最小问题，则

Fit(f(x))??cmax?f(x),f(x)?cmax0,其他 (4)

式中cmax为f(x)的最大值估计。 若目标函数为最大问题，则

Fit(f(x))??f(x)?cmi,nf(x)?cm0,其他in (5)

式中cmax为f(x)的最小值估计。

这种方法是对第一种方法的改进，可以称之为“界限构造法”，但存在的问题是有时候存在界限预先估计困难，以至于不可能精确。

? 若目标函数为最小问题

第10页 共27页

Fit(f(x))?

1，c?0,c?f(x)?01?c?f(x) (6)

1,c?0,c?f(x)?0 (7)

1?c?f(x) 若目标函数为最大问题 Fit(f(x))?该方法类似于第二种方法，c为目标函数界限的保守估计值。 本设计直接采用的是第一种适应度计算策略。

(3)选择 以适当的概率从DNA汤中P(t)选择出m个DNA链个体并作为父本母本用于繁育后代，而产生的新个体投入到下一代P(t?1)。选择的意义在于使那些适应度函数值大的DNA链有更多更大的留下来并参与下一代的机会，这样优良特性便可以遗传下去，体现了大自然优胜劣汰的原理，与常规的标准遗传算法类似，DNA-GA算法选择操作常用的方法有适应度比例法、期望值法、排位次序法、精华保存法和轮盘赌法。下面简单介绍一下常用的两种：

按比例的适应度分配：按比例的适应度也可称之为选择的蒙特卡罗法，是利用比例于各个个体适应度的概率决定其子孙的去留的可能性，若某个个体i，其适应度为fi ，则其被选取的概率表示为：

pi?fi?i?1m

fi (8)

轮盘赌选择法(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 轮盘赌选择法的选择概率计算 个体 适应度 选择概率 累积概率

0.18

0.34

0.49

0.62

0.73

0.82

0.89

0.95

0.98

1.00

1.00

0.18

0.16

0.15

0.13

0.11

0.09

0.07

0.06

0.03

0.02

0.0

1 2.0

2 1.8

3 1.6

4 1.4

5 1.2

6 1.0

7 0.8

8 0.6

9 0.4

10 0.2

11 0.1

第11页 共27页

第四轮1个体0第二轮2第六轮34第五轮5第一轮6第三轮 0.180.340.490.620.730.820.951.00 图2 轮盘赌选择法

(4)交叉 对于选中的用于繁殖后代的每一对DNA链个体，将其中部分内容进行互换。交叉位置是随机产生的。通过交叉这种方法，凭借交叉点，产生了新的DNA链，基因得以极大的改变，交叉分为单点交叉以及多点交叉等好几种方式。而多点交叉又有即n?点交叉和标准交叉两种方式。图三给出的是一个简单单点交叉的例子，如图：

|

···AGTATGAACT|GCACGCCGTACTACT···

···TGAGGCCGTAGTACGATACGTAGAT···

?

| ···AGTATGAACT|GTACGATACGTAGAT···

图4 单点交叉示意图

···TGAGGCCGTAGCACGCCGTACTACT···

(5)变异 在DNA群体中以相应的概率随机的选取若干个DNA链个体，对其中选中的DNA链个体，随机的选取某一位进行DNA链中的碱基排列顺序的变化。DNA链中的变化有碱基的替换、丢失和嵌入。碱基的取代有以下两种：一种是相同类型的碱基之间的转换变异，如嘌呤替换嘌呤，嘧啶代替嘧啶，A替换G，T替换C；另一类是异类型碱基的互相替换：嘌呤被嘧啶替换，如A被T替换。图四是一个染色体中碱基T变成A的变异例子： ···TGAGGCCGTAGTACGATACGTAGAT···

?

图4 点变异例子

···TGAGGCCGTAGTACGAAACGTAGAT···

(6)倒位 从DNA群中以一定的概率随机选取若干个DNA链个体，选中这些DNA链个体后，随机的选中某两点位置，把他们之间的碱基顺序进行互

第12页 共27页

相倒位。倒位的目的在于尝试找到更好的进化特性的基因顺序。倒位操作是可选的，根据问题的需要而定。图五给出的是倒位的例子：

···TGAGGCCGTAGTACGATACGTAGAT···

?

||

|

···TGAGGCCGTAATAGCATGCGTAGAT···

图5 倒位操作的例子

|

(7)循环往复 对于新产生的每一代DNA汤，反复回到步骤(2)，再进行评价、适应度计算、选择、交叉、变异和倒位操作。如此循环，在动态中经历了无数次状态，DNA汤更丰富了，包含了各种情况，群体中个体适应度不断提高，平均适应度不断提高，直到找到最优解后或者达到某一限制后个体的适应度和平均适应度不再提高，此时迭代过程收敛，算法自然结束了。 2.2.4 DNA进化算法与常规遗传算法的比较

基于DNA计算的进化算法是常规遗传算法的发展，自然容纳了常规遗传算法如下的基本特点：

(1)都是对参数构成的编码种群进行进化，而不是对某个特定参数。 (2)由于算法是对编码种群的各种操作，而不受函数性质的限制(诸如连续性、是否存在导数、单多重极值等)，所以可求解一般优化方法难以解决的一些问题。

(3)都是单纯利用适应度大小进行搜索，无需其他任何信息。 (4)都是利用随机操作指导着向最优化方向前进的搜索。 (5)都有智能的特点，即可以自组织和自学习。

(6)都具有隐形并行性，使得相对少的编码覆盖范围很大的解区域。 此外，DNA进化算法还具有普通遗传算法不具备的特性：

(1)DNA编码方法与传统遗传算法使用的二进制编码方法相比有了进步，使得种群信息更丰富，更适合表达较复杂知识，且更加灵活，其长度也较遗传算法大大的缩短。

(2)DNA进化算法中，能够更方便引入分子水平操作，使用各种遗传操作算子，如倒位、异位、交叉等，这极大的扩展了进化方法，如倒位操作，可以使在上一代中相差很远的后代聚集在一起，这样便相当于重新定义了基因群，使得其更加紧凑，不易被交换所分裂。

(3)DNA进化算法中，因为编码的丰富性和译码的多样性，所以即使变异概率较低，仍然能保持一定水平的多样性。

(4)DNA染色体长度可变的特点，使得更容易完成插入和删除碱基序列的操作，更加适合于优化复杂知识。

第13页 共27页

2.2.5 基本DNA算法的实现 基本DNA进化算法的伪码如下所示： ·······················································

初始化，产生DNA链长度为dna_length,种群规模为soap_size的dna汤 For k=1:1:D(迭代数) 解码过程； 计算适应度； 适应度排序； 找出最优解； for i=1:1:soap_size

执行选择操作(采用轮盘赌法)； end

for i=1:2：soap_size if rand

For i=1:1:soap_size If rand

执行变异操作(包括碱基的替换，丢失和插入) End End

For i=1:1:soap_size If rand

· ·························································

3 改进方法研究

根据基本实现算法中采用适应度比例选择、交叉、变异和倒位等特征，我们可以从改进种群初始化产生的方法、选择方法的改进、交叉点的计算、变异概率的选择、插入长度的改进和倒位点的确定等方面加以改进。另外，针对本

第14页 共27页

算法所存在的易出现“早熟”现象和局部搜索能力较差的问题，采取DNA算法和模拟退火算法结合的方法，以获得更好的性能。

3.1 自适应DNA进化算法

本设计在实现基本算法过程中，是通过不断地选择、交叉、变异和倒位操作的迭代过程，最终收敛于最佳解的算法，选择操作使得适应度函数值较高的个体有着更大的复制概率，它能加快算法的收敛速度，因为其种群越来越优秀。交叉操作则是通过重组基因和染色体从而产生更优秀的个体，寻优的搜索功能主要通过它来实现，但是种群中如果发生基因丢失，而这些丢失的基因恰好又是最佳解所包含的信息时，交叉操作则有可能搜索不到最优解，这时候，变异操作则可能恢复丢失的基因。

传统的算法中，交叉在变异之前，且“优秀”的个体和“劣质”的个体经受相同的交叉、变异和倒位操作的概率，这样的话，基本上很难保证丢失的基因的恢复，而且即使是恢复了有效基因的个体的适应度值也不一定高，经过选择操作后又会造成有效基因的丢失[6]。

为此，本设计提出，在算法实现过程中，改变交叉操作和变异操作的先后顺序，同时，对交叉和变异操作以及倒位操作采取自适应概率的方法。

这种算法的特点之一是先进行变异操作，保持了群体的多样性，之后再通过交叉等操作就能有效地找到最优解。DNA算法中的交叉、变异和倒位操作的概率的选取对算法的性能有着很大的影响：如果交叉和变异概率过大，有可能使算法变为随机搜索，而交叉和变异概率太小的话又会使算法早熟，未能找到最优解而陷入了局部最优点。本算法采用的自适应公式如下：

?k1?(k1?k2)(f?fav?fmax?favgPc??

k1,f??favg??')g,f??favg (9)

上式中k1与k2按照经验取值，如本改进后算法中k1=0.9，k2=0.2，f?为参与交叉操作的两个DNA个体中较大适应度值那一个，fmax和favg分别为种群中最大适应度值和平均适应度值。

(k3?k4)(fmax?fk3???fmax?favg????k3,f?favg)Pm

,f?favg(10)

上式中k3和k4同样按照经验取值，本改进后算法设计中k3=0.1，k4=0.05，

f为变异个体适应度值，fmax和favg分别为种群中最大适应度值和平均适应度值。

第15页 共27页

(k5?k6)(fmax?fk5???fmax?favgP??i??k5,f?favg),f?favg (11)

上式中k5和k6同样按照经验取值，本改进后算法设计中k5=0.3，k6=0.04，

f为变异个体适应度值，fmax和favg分别为种群中最大适应度值和平均适应度值。

在实现DNA进化算法的过程中，最核心的是其仿生优化特性，在算法中体现的就是进化操作，我们认为进化操作有利于种群向好的方向进化，就如同自然界的生物的进化过程一样，是向着更加适应环境的方向进行的。以上给出的自适应算法，在种群中个体适应度较小时，进化操作的概率较大，有利于种群向好的方向进化，种群中个体适应度较大时，进化概率较小，有利于保护现有种群，所以改进后可以较快的找到最优解。总之，通过自适应改进后保护了优秀个体，加速了适应度较差的个体进化速度，有助于算法逐渐靠近最优状态

[7]

。

3.2 与模拟退火算法结合的DNA算法

模拟退火算法 简称SAA (Simulated Annealing Algorithms)),该算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

模拟退火算法最早由Kirkpatrick等应用于组合优化领域，它是基于Mente-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神

第16页 共27页

经网络、信号处理等领域。

基本DNA算法和模拟退火算法各有优缺点，首先DNA进化算法类似于遗传算法，局部的搜索能力较弱，但是其对搜索整体过程方面的把握比较有优势，模拟退火算法则反之，它拥有较好的局部搜索能力，但是不容易使搜索过程进入很理想的区域，所以，将这两种算法结合起来，应该会出现比较好的结果。本设计的改进算法实现过程中，首先用基本型DNA进化算法找出一个解，当然，这个解可能不是最优解，由于DNA进化算法具有较为优异的全局寻优性能的特点，故可假设求出的解与理论最优点相距不远了，而由于模拟退火算法有着较强的局部搜索能力，所以在之前基本算法的计算基础上，一定范围内的精细的模拟退火搜索很快能够找到最优值。

本设计中，模拟退火算法程序基本框架如下：

·······················································

初始化(初始点为原算法求得点) While(1)

Tem=tem * 衰减因子(退火操作) For i=0:1:马科夫链长度 While(1)

在初始点附近随机选下一点 判断新产生点是否在搜索范围内 End

%判断新产生点是否比原来最佳点更优 If(新产生点由于原最佳点) 保存新点最为最佳点 End

%接受新产生的点为下一迭代的开始点 If(新产生点与原来更优) 将原来点赋值为新点的值 End End

%结束条件为根据上一个最优解与最新的一个最优解的

之差小于某个容差

End

························································

第17页 共27页

起始初始化实际问题的DNA链编码计算适应度控制退火参数执行退火操作产生新个体是得到解？否选择交叉评价当前种群个体变异否达到最优目标？是结束倒位图6 与模拟退火结合的混合算法流程图

4 研究结果

本设计对以下三个典型函数进行优化来测试算法的性能，三个函数具有不

第18页 共27页

同的性质，其中第一个和第三个函数是利用算法求解最小值，对第二个函数求解最大值，三个典型函数均为二元函数，在算法设计过程中，首先初始化生成一个20行30列的DNA汤，即每一代运算可运算出20个不同的适应度值(即为函数值)，每一列有30位编码，前15位为x1编码对应映射至某个数值，后15位为x2的编码对应映射另一数值，然后用这20对x1和x2运算出20个不同的适应度，对这20个适应度值进行按大小顺序的排列，排列完成后就可以按顺序找到最大或最小值了，这20个适应度值是在一代计算中完成的，也就是说每一代进化后都会产生20个适应度值，我们求解出的则是这20个适应度值中最大或最小的那个。

以下为试验中用到的三个函数： (1) F1函数

?(x1??)F(x,x)??cosx()?cosx()?e12 1122?(x2??)2 (12)

其中x1和x2的取值范围均为-100至100，函数最小值为-1.00，最优点为(3.1410,3.1416)。

(2) Shaffer函数

sin2x2?y2?0.5F（x,y）?0.5?,?100?x?10,0?100?y?100222(1?0.001)(x?y) (13)

此函数有无限个局部极大值, 它们的取值均为0.9903,其中只有一个为全局极大点( 0, 0), 极大值为1。 （3） Camel函数

1f(x,y)?4x2?2.1x4?x6?xy?4y2?4y4,?5?x?5,?5?y?53

(14)

函数有6个局部极小点,其中有两个(- 0.0898,0.7126)和( 0.0898, - 0.7126) 为全局最小点, 最小值为- 1.0316。

本设计使用Matlab7.12软件来实现，采用蒙特卡洛统计法，每种算法各运行50次,对50次运算结果取平均值，同时统计找到最优点次数和找到最优点平均代数，并将几个函数的测试结果分别进行比较。其中找到最优点次数次数是指50次运算下找到全局最优解的次数。

找到最优解的代数是搜索时找到全局最优解时所需的进化代数, 如果在到终止代数( 200代)还不能搜索到最优解的以200代计,在结果分析时，因为测试函数性质是已知的，故算法运算过程中，若与理论值偏差较大的点，本设计中将其排除(因为即使不知道测试函数的最大值或最小值，在多次计算过程中也可判断出测试函数最大或最小值的趋势，至少能够确定出与理论值非常接近的一

第19页 共27页

点)。

4.1 基本算法的实验结果

在测试基本算法的实验中，各参数设置为：选择概率pc=0.8，变异和倒位概率均为0.01，DNA链的长度为30，DNA汤规模为20，进化代数为200代。

表 2基本算法实验结果

函数

找到最优点次数

找到最优点平

均代数

陷入局部最优

点次数

均值

最优点值

F1函数 Camel函数 Shaffer函数

9 0 10

24 未找到 128

16 7 28

-0.9991 -0.8557 0.990284

-1.000 -1.031628 1.000

从上表中可以看出，基本DNA算法对F1函数的50次运算结果中，直接找

到理论最优点次数为9次，这9次运算的平均找到最优点代数为24代，陷入局部最优点次数16次，50次运算中挑选出数据25组，剩下25组认为偏差较大，不参与统计，均值为-0.9991，接近理论值。

对Camel函数的实验中，基本算法未能找到最优点，陷入局部最优解7次，均值-0.8557，大致接近理论最小值。

对Shaffer函数的实验结果中，找到10次最优点，平均代数128代，28次陷入局部最优，12次出现偏差较大值，略去，均值为0.990284，仍然接近理论最大值。

从以上的统计结果我们可以看出，该算法基本上能够对典型测试函数进行寻优，但是多次实验中不能每次找到最优点，更多情况下陷入局部最优解，另外有较大偏差值的产生。最后，针对不同的函数，情况也不一样。

4.2 采取自适应方法改进的DNA进化算法实验结果

在测试自适应改进后算法的实验中，交叉概率、变异概率和倒位概率均采用自适应的方法，故为动态概率，其他参数同基本算法一致。

表3自适应改进算法实验结果 函数

找到最优点次

数

找到最优点平

均代数

陷入局部最优

点次数

均值

最优点值

F1函数 Camel函数 Shaffer函数

13 5 12

38 46 75

33 40 30

-0.9996 -0.9271 0.9903

-1.000 -1.031628 1.000

上表中，改进后的DNA进化算法对F1函数的50次运算结果中，找到最优

第20页 共27页

点13次，陷入局部最优点33次，除去偏差较大点4次，较大偏差点出现次数明显比基本型算法少，46次有效数据均值-0.9996，比基本型算法有所改进。

对Camel函数的50次实验结果中，5次找到理论最优点，陷入局部最优点40次，较大偏差出现5次，45次有效数据均值-0.9271，比基本型算法有所改进。

在对Shaffer函数的50次实验结果中，12次找到理论最优点，平均代数75,30次陷入局部最优，42次有效数据的均值0.9903。

从以上数据分析可以得知，自适应改进后的算法与基本型算法相比，效果有所改进，找到理论最优点次数增多，所用进化代数减少了，均值更加靠近理论值了。

4.3 采用与模拟退火算法结合的混合算法实验结果

在测试与模拟退火算法结合的混合算法实验中，进化操作概率同基本算法一致，DNA长度30，DNA汤规模20，进化代数为200代，模拟退火初始温度为100，马科夫链长度10000，温度衰减因子为0.95，搜索步长0.02，容差为1e-8。

表 4 DNA-SA算法实验结果

函数

找到最优点次数

陷入局部最优点次

数

F1函数 Camel函数 Shaffer函数

50 50 30

0 0 20

-1.000 -1.031628 0.9998

-1.000 -1.031628 1.000

均值

最优点值

采用与模拟退火算法结合的算法后，对于前两个函数，50次实验每次均找到了理论最优点值，没有出现陷入局部最优点的情况。每次运算结果均为理论最优点，对Shaffer函数的50次运算结果中，30次找到理论最优点，没有出现较大偏差的情况，50次实验的均值为0.9998，以及非常接近理论最大值了。

改进后算法的模拟退火操作在基本DNA进化算法之后，故本表中不再涉及进化代数的问题。

基于统计结果，我们可以看出与模拟退火算法结合的混合算法有着极优的寻优功能，这也证明了模拟退火算法有良好的局部寻优能力的结论，其唯一缺点是运算时间和结果两个方面存在矛盾，这是因为如果想要得到很好的结果的话，每一次退火操作之后，又要经过马科夫链长度那么多次迭代计算，而为了结果精确，马科夫链长度往往会选择较长。

4.4 典型测试函数运行效果图

运算结果如下列图示，由于算法运算每次都是随机的，故效果图只定性的

第21页 共27页

分析适应度随进化代数之间的关系。

0-0.1-0.2-0.3-0.4BestF-0.5-0.6-0.7-0.8-0.9-1020406080100Times120140160180200

图7 F1函数运行效果图

上图横坐标表示进化代数，纵坐标为每一代对应的最佳适应度值，从上图可以看出，算法在大概50代以后趋于收敛，求得适应度值接近-1。

1412108x 104BestF6420-2020406080100Times120140160180200

图8 camel函数运行效果图

同上，横坐标表示进化代数，纵坐标为每一代对应的最佳适应度值，从上

第22页 共27页

图可以看出，算法在大概50代以后趋于收敛，求得适应度值接近-1。

10.950.90.85BestF0.80.750.70.65020406080

100Times120140160180200

图9 shaffer函数运行效果图

从上图可以得知，算法运行过程中，30代以后趋于收敛，收敛前适应度值随进化代数增加而直接增大。

4.5 几种方法的比较

通过对表2、表3和表4的分析得知，基本算法在计算过程中，能够寻找到最优点，但是对于50次试验的统计规律看，寻优次数并不多，而且，偏离理论最优点幅度较大的次数较多。采用自适应算法后，寻优的速度较基本算法要快一些，这一点我们可以从找到最优点平均进化代数中读出来，找到最优点的机会也明显大了一些，因为找到最优点次数有所增加，另外，陷入局部最优值的次数也有所增加，说明偏离理论最优点较大的机会更少了，但是总体说来改进效果仍然不是非常理想。表4中数据位采用与模拟退火算法结合的算法，很明显的是寻优效果最好，且前两个函数的运行基本上能够达到每一次都能找到最优点，但因为算法是先让基本算法寻优，再对寻优找到的结果附近有模拟退火操作，所以计算时间偏长。

另外，对于不同的测试函数，同种方法达到的效果也不一样，比如在基本算法与模拟退火结合的混合算法中，shaffer函数存在收敛于局部最优点的情况，而改进后对于另外两个函数，效果很理想。

第23页 共27页

结 论

DNA计算是一个崭新的研究领域，DNA进化算法是基于生物DNA编码和进化机制的一类仿生优化算法，对解决复杂的组合优化问题非常有效，传统的遗传算法是一种在分子水平模拟生物进化过程并能够在电子计算机上实现求解复杂问题的有效算法，故可作为研究DNA进化算法的桥梁。

本研究在借鉴标准遗传算法的基础上，对于DNA链上的生物信息，也就是四个碱基A、T、C和G，分别赋以0、1、2、3，用四进制代替传统遗传算法的二进制对DNA链进行编码，同时，丰富了变异操作，增加了倒位操作，以期得到较遗传算法更好的效果。

在对典型测试函数的测试实验中可以表明，基本DNA算法虽然能够达到找到最优点的要求，但是主要问题在于实验50次，找到最优点的次数较少，更多的时候是陷入局部最优值或者偏离理论值过大，为此，本设计中引入了两种改进方法：对算法中的进化操作概率赋以自适应动态改变的自适应算法和与模拟退火算法结合的混合算法。

自适应算法在一定程度上改进了遗传性能，但不足之处在于，它们往往都是对适应度低的个体以恒定较高的概率进行交叉，而对于适应度高的个体以自适应变化的、但总体较低的概率进行交叉操作。这样对于保护种群中的优势个体不被破坏是有效的，但对于新的优势个体的产生反而是不利的，算法一旦陷入局部最优，很难跳出[8]。

模拟退火算法有着非常好的局部寻优能力，所有本设计设想能否先用DNA进化算法搜索出一个值，理论上这点与最优点不会相差太远，然后利用模拟退火算法的超强局部搜索能力，很高质量的找到最优点，实验结果证明这种设想是正确的。

DNA算法作为一个新兴的研究领域，目前学术界对其研究的论文数量远不如其他很成熟的算法那般多，相信经过学术界的进一步研究，DNA算法会越来越成熟，由于笔者水平有限，本研究中难免可能有一些不正确之处，请各位老师指正。

第24页 共27页

参考文献

[1]丁永生.计算智能——理论、技术与应用[M].北京：科学出版社，2004

[2]陶吉利.基于DNA计算的遗传算法及其应用研究[D].杭州：浙江大学，博士论文，2010 [3]王小平、曹立民.遗传算法—理论、应用与软件实现[M].西安：西安交大出版社，2002 [4]陈向东.遗传算法在车间生产计划中的应用[D].长春：长春理工大学，硕士论文，2003 [5]李继云.智能款式设计系统研究与实现[D].上海：东华大学，硕士论文，2003

[6]常东.基于市场机制的QOS控制模型MQC的改进遗传算法求解[J].计算机学报，2004，16(3):71-82

[7]王宏生，孟国艳.人工智能及其应用[M].北京：国防工业出版社，2009

[8]陈世哲等.IC芯片视觉检测中快速图像匹配定位[J].光电子·激光，2005,20(5)：60-71

第25页 共27页

致 谢

本研究及学位论文是在我的导师 副教授的亲切关怀和悉心指导下完成

的。他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我。从课题的选择到项目的最终完成，朱老师都始终给予我细心的指导和不懈的支持。几个月以来，朱老师不仅在学业上给我以精心指导，同时还在思想上给我以无微不至的关怀，在此谨向朱老师致以诚挚的谢意和崇高的敬意。

在此，我还要感谢一同选作朱老师毕业设计各位同学，正是由于你们的帮助和支持，以及我们的相互学习，我才能克服一个一个的困难和疑惑，直至本文的顺利完成。特别感谢我们的师兄吴思东同学，在朱老师赴美期间，耐心负责我们的进度，给予我不少的帮助。

在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意!最后我还要感谢培养我长大含辛茹苦的父母，谢谢你们!

作者简介：

姓 名： 性别： 男 出生年月： 民族： 汉族 E-mail:

第26页 共27页

声 明

本论文的工作是2011年11 月至2012年 6 月在 控制工程学院完成的。文中除了特别加以标注地方外，不包含他人已经发表或撰写过的研究成果，也不包含为获得 或其他教学机构的学位或证书而使用过的材料。除非另有说明，本文的工作是原始性工作。

关于学位论文使用权和研究成果知识产权的说明：

本人完全了解 有关保管使用学位论文的规定，其中包括： (1)学校有权保管并向有关部门递交学位论文的原件与复印件。 (2)学校可以采用影印、缩印或其他复制方式保存学位论文。 (3)学校可以学术交流为目的复制、赠送和交换学位论文。 (4)学校可允许学位论文被查阅或借阅。

(5)学校可以公布学位论文的全部或部分内容(保密学位论文在解密后遵守此规定)。

除非另有科研合同和其他法律文书的制约，本论文的科研成果属于 特此声明！

作者签名：

年 月 日

第27页 共27页

声 明

本论文的工作是2011年11 月至2012年 6 月在 控制工程学院完成的。文中除了特别加以标注地方外，不包含他人已经发表或撰写过的研究成果，也不包含为获得 或其他教学机构的学位或证书而使用过的材料。除非另有说明，本文的工作是原始性工作。

关于学位论文使用权和研究成果知识产权的说明：

本人完全了解 有关保管使用学位论文的规定，其中包括： (1)学校有权保管并向有关部门递交学位论文的原件与复印件。 (2)学校可以采用影印、缩印或其他复制方式保存学位论文。 (3)学校可以学术交流为目的复制、赠送和交换学位论文。 (4)学校可允许学位论文被查阅或借阅。

(5)学校可以公布学位论文的全部或部分内容(保密学位论文在解密后遵守此规定)。

除非另有科研合同和其他法律文书的制约，本论文的科研成果属于 特此声明！

作者签名：

年 月 日

第27页 共27页

本文来源：https://www.bwwdw.com/article/ew67.html