发布时间 : 星期一 文章DNA进化算法及其改进研究更新完毕开始阅读ee197a242f60ddccda38a04a
(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页