智能优化理论-第4章DNA计算

第4章DNA计算目录概述DNA的结构DNA计算的原理DNA与遗传算法的集成复习思考题01概述概述计算机技术被认为是20世纪三大科学革命之一，电子计算机为社会的发展起到了巨大的促进作用。02计算机科学家们也将计算的问题划分为容易、困难和不可计算三类。03处理容易类的计算，目前的电子计算机能完全胜任，但处理困难类的问题时，电子计算机会随着问题规模的增大，计算所需的时间以指数级增长。01量子物理学已经成功地预测出芯片微处理器能力的增长不能长期地保持下去。计算机的小型化在技术上存在明显的限制。分子水平上进行计算的概念最早是在20世纪60年代早期由RichardFeynman提出的。概述01但是当时尚缺乏适用的材料、工具与方法，Feynman的“超微型计算机”想法只能是一种超前的、美好的愿望。02生物领域发展到了分子水平，使生物学的研究深入到了分子水平，到了80年代，随着人们对分子生物学理论的了解日益加深，现代生物化学、生物工程技术的日益完善，分子计算的条件事实上巳基本具备。031994年，美国南加州大学的LeonardM.Adleman博士用DNA计算的方法解决了有向Hamilton路问题，并成功地利用现代分子生物技术在DNA溶液的试管中进行了实验。概述概述01这一研究成果很快引起了计算机、数学、分子生物学等领域的科学家们的极大兴趣。02它的重要意义不仅在于算法和速度，更在于采用了一种全新的介质作为计算要件。以生物技术来解决电子计算机无法解决的困难问题，并且开发了这种媒体潜在的并行性。0302DNA的结构DNA中有4种碱基，即腺嘌呤(Adenine，A)、鸟嘌呤(Guanine，G)、胞嘧啶(Cytosine，C)和胸腺嘧啶(Thymine，T)。各种碱基间的不同组合就构成了异常丰富的遗传信息。科学家们指出．DNA含有大量的遗传密码，通过生化反应传递遗传信息。DNA链主要是由一个脱氧核苷酸上的5'-磷酸基和另一个脱氧核苷酸上的3'-羟基共价键连接而成。DNA的结构DNA由两条极长的核苷酸链利用碱基之间的氢键结合在一起，形成一条双股的螺旋结构，且一股的碱基序列与另一股的碱基序列互补。A和T配对．C和G配对。碱熬的上述配对关系称为Watson-Crick（WC）配对。DNA有两个最主要的功能：第一个功能是DNA携带遗传信息，能转录成RNA，RNA再转译成蛋白质；第二个功能是自我复制。DNA的结构DNA一般为长而无分支的双股线型分子，但有些为环形，也有少些为单股环形。每个染色体是一段双股螺旋的DNA。遗传信息以A、T、C和G在核苷酸中的排列顺序而体现，其排列顺序的多样性体现了丰富的遗传信息。从生物DNA到蛋白质的形成过程。首先，通过转录作用将DNA中携带的遗传信息转录到信使RNA（mRNA）中。DNA的结构在从DNA到蛋白质的形成过程中，大多数碱基并没有用来合成蛋白质．它们首先从DNA上转录，将没有用的部分拼接，拼接后就形成了mRNA。密码子对应于氨基酸的遗传密码表如表4.1所示。然后，通过翻译作用，将mRNA中携带的遗传信息转译成含特定氨基酸序列的蛋白质，蛋白质则构成了细胞。在生物DNA中，基因是储存遗传信息的基本单位，一个基因开始于起始密码子ATG，终止于终止密码子TAA、TAG或TGG。在mRNA中排列着由三个连续的碱基组成的密码子，这些密码子是合成蛋白质的密码。64种密码子对应20种氨基酸。DNA的结构03DNA计算的原理DNA计算是一种新的计算思维方式，同时也是关于化学和生物的一种新的思维方式。生物与数学的过程有各自的复杂性，但它们具有一个重要的共性，即生物所具有的复杂结构实际上是结构的编码在DNA序列中的原始信息经过一些简单的生化处理后得到的。求一个含有变量的可计算函数的值也可以通过求一系列含变量的简单函数的值来实现。DNA计算的原理DNA计算的本质就是利用大量不同的核酸分子杂交，产生类似于某种数学过程的一种组合的结果，并根据限定条件对其进行筛选的。大量随机的DNA相互杂交后，每个DNA链所携带的原始信息就会与其他DNA链所携带的信息重新组合，形成一种类似数学组合的结果。根据DNA分子之间的Watson-Crick互补原理，不同的DNA分子根据其不同的末端，从而具有不同的方向性。DNA计算的原理VS对一种特定的运算而言，这种结果的获得是通过对DNA进行一系列的连续操作来实现的。DNA计算就是利用不同形式的DNA链编码信息，然后将携有编码信息的DNA链进行互补杂交，最后，利用分子生物技术，如聚合酶链式反应PCR(PolymerizeChainReaction)、并行重叠组装技术POA(ParallelOverlapAssembly)、超声波降解、亲和层析、克隆、诱变、分子纯化、凝胶电泳、磁珠分离等，捕获运算结果。DNA计算的原理经典的计算科学理论是建立在一系列重要操作上的，大部分自动机语言理论模型都是这样的。DNA计算也是建立在一系列连续的分子操作上的，这些用于计算目的的分子生物操作在形式上具有多样性：切割、粘贴、分离、连接、插入和删除等。从理论上来讲，合理地使用这些分子生物操作可以建立与图灵机一样强大的新的计算模型。DNA计算的原理DNA计算的原理从DNA的原理和一些生物操作工具来看，DNA计算与数学操作非常相似。DNA单链可看做由四个不同符号A、G、C和T组成的链。它在数学上就像计算机中的编码“0”和“1”一样，可表示成四个字母的集合∑={A，G，C，T）来编码信息。04DNA与遗传算法的集成DNA链（染色体）表现型DNA汤（群体）倒位基因型遗传子座是多个遗传因子的集合，由A、T、C、G编码集合组成。是遗传物质的主要载体。DNA链上遗传因子的位置，各个位置决定所遗传的信息。是形成DNA链的内部表现，它决定了生物体的性状和特征。由DNA链决定形状的外部表现，或者说是根据基因型形成的个体。DNA链带有特征的个体的集合，该集合内的DNA链的多少为DNA汤的大小。在DNA链中两个随机选择位置之问的某些碱基序列进行倒位。它可以使在父代中离得很远的位在后代中靠在一起．相当于重新定义基因块。基本概念和术语不过一个是用试管在分子生物学实验室里实施运算，一个是用程序语言实现运算，图4.2给出了它们基本运算框架的异同。启发人们从两个不同的领域相互借鉴，利用分子生物学新理论、新技术进行遗传算法的扩展。遗传算法和DNA计算有很多相似之处，如对特定符号集编码的符号串进行操作、具有很高的并行性等。DNA遗传算法的关系和假设一些学者提出了基于DNA机理的改进的遗传算法，如带有双串DNA的遗传算法用于促进DNA复制的非对换变异。还提出了基于生物学DNA编码方法的遗传算法，这种方法具有DNA染包体中的重复性和基因表达的重叠性．并使交叉和变异操作变得容易。为了避免在DNA计算中，由于核酸碱基之间化学反应带来的误差，一些研究者提出了用于DNA进化计算中好的DNA译码算法。DNA遗传算法的关系和假设遗传算法可以直接使用DNA计算方法来实现，如JunghueiChen等人就成功地使用对DNA分子进行操作的遗传算法解决了一个最大数问题。目前有关遗传算法和DNA计算两者交叉领域的研究成果并不多见，但鉴于遗传算法已取得的巨大成功和DNA计算具有的极大潜力，未来二者结合会对生物计算技术以及相关领域产生革命性的推进作用。DNA遗传算法的关系和假设使用n个具有任意DNA链的个体组成初始代群体(DNA汤)一条DNA链由4种碱基A、T、C、G的结合体构成．可以表示多个基因。按编码规则，将DNA汤中每一个DNA链的密码子按表4.2（或表4.3）转化成所对应的参数值用于求解问题，并按某一标准计算其评价函数。DNA遗传算法的实现适应度的评价初始化及DNA链编码若其评价函数值高，表示该DNA链有较高的适应度。由于将DNA的4个碱基中的3个组合成密码子的情况有64种．在翻译参数时可将这64种组合对应于[0,63]区间上的任意一个数，用于问题的求解。这里考虑的翻译关系与生物DNA的遗传密码表不同，即不同的密码子对应于不同的参数。而在生物DNA中．允许不同的密码子对应相同的氨基酸（参见表4.2）。若其值在预定的范围内变化．那么密码子的参数和实际参数值之间的转换关系为式中，x∈[-9,9]。DNA遗传算法的实现函数有许多局部极值点，其最大值在x=0.126附近。在采用DNA-GA对此函数寻优的计算机仿真中，采用6位DNA编码，交叉率和变异率分别选取为0.9和0.1，每代个体为30个。以上结果是比较满意且合理的，同时也说明了DNA-GA在函数寻优中是有效的。DNA-GA收敛后，对此函数寻优得到的结果在x=0.125处取最大值。为了验证DNA-GA的有效性，我们以一个函数寻优的例子来加以验证。DNA遗传算法在函数寻优中的应用DNA-GA的结构与常见遗传算法的类似，是常规遗传算法的发展，包含着常规遗传算法所固有的优点。DNA-GA对参数编码进行优化，而不是直接操作参数本身，因此可以解决常规优化方法难以解决的问题。DNA-GA利用适应度进行搜索，无需导数等其他信息，利用随机操作指导着向最优化方向前进的搜索。010203与常规遗传算法的比较与常规遗传算法的比较DNA-GA具有智能化，即具有自组织、自适应和自学习性等，具有隐性并行性，使相对少的编码对应范围极大的解区域。DNA-GA比传统的二进制编码方法有很大的改进，更适合复杂知识的表达方式，且比较灵活，长度也大大缩短。由于编码的丰富性及译码的多样性，即使在变异概率低的情况下，也能保持一定水平的多样性。123更便于引入基因级操作，发展遗传操作算子，如倒位、分离、异位、多倍体结构等，能大大地丰富进化手段。例如倒位可以使在父代中离得很