智能优化理论- 课件 第3、4章 遗传算法、DNA计算

第3章遗传算法目录contents遗传算法寻优的基本思路遗传算法的理论基础遗传算法的实现及改进算法遗传算法寻优的基本思路01遗传算法是一种基于自然选择和基因遗传学原理的搜索算法，将“适者生存”这一基本的达尔文进化原理引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着算法的运行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。好的特征被不断地继承下来，坏的特性被逐渐淘汰。新一代个体中包含着上一代个体的大量信息，新一代的个体不断地在总体特性上胜过旧的一代，从而使整个群体向前进化发展。遗传算法寻优的基本思路研究遗传算法的目的主要有两个：一是通过它的研究来进一步解释自然界的适应过程；二是为了将自然生物系统的重要机理运用到人工系统的设计中。遗传算法的中心问题是鲁棒性，它能在许多不同的环境中通过效率及功能之间的协调平衡以求生存。人工系统很难达到如生物系统那样的鲁棒性。遗传算法正是吸取了自然生物系统“适者生存”的进化原理，使它能够提供一个在复杂空间中进行鲁棒搜索的方法。遗传算法寻优的基本思路输入标题02010403遗传算法寻优的基本思路遗传算法具有计算简单及功能强的特点，它对于搜索空间基本上不需要什么限制性的假设（如连续、导数存在及单峰等）。枚举法最大缺点是计算效率太低，对于一个实际问题，常常由于太大的搜索空间而不可能将所有的情况都搜索到。枚举法可以克服上述解析法的两个缺点，即它可以寻找到全局的极值，而且也不需要目标函数是连续光滑的。常规的寻优方法主要有3种类型：解析法、枚举法和随机法。解析法寻优通过让目标函数的梯度为零，进而求解一组非线性方程来寻求局部极值。遗传算法的理论基础0203表现型生物个体表现出来的性状，即具有特定基因型的个体在一定环境条件下表现出来的性状特征的总和。01基因是DNA分子片段，含有大量遗传信息，是控制生物体性状的基本遗传单位。02染色体包含一定数目的基因，是基因的物质载体，也是细胞中遗传信息的物质载体。遗传算法的基本概念遗传算法的基本概念01种群：每个物种由一定数量的个体组成，所有个体的总和称为种群。02适应度：用于衡量种群中每个个体的优劣程度，是度量每个个体对其生存环境的适应能力的标准。03遗传算法中，适应度函数根据目标函数设定，它的大小直接影响到种群中每个个体的生存概率。04一种群为遗传算法提供了搜索解的遗传进化搜索空间。010203通过一个简单的例子详细描述遗传算法的基本操作过程，目的在于清晰地展现遗传算法的理论基础。设需要求解的优化问题为寻找当自变量x在0-31之间取整数值时函数的最大值。枚举的方法是将x取尽所有可能值，观察是否得到最高的目标函数值。尽管对如此简单的问题该法是可靠的．但这是一种效率很低的方法。下面运用遗传算法来求解这个问题。遗传算法的基本操作针对本例中自变量的定义域，可以考虑采用二进制数来对其编码，这里恰好可用5位数来表示，如01010对应11111对应。许多其他的优化方法是从定义域空间的某个单个点出发来求解问题，并且根据某些规则，它相当于按照一定的路线，进行点到点的顺序搜索。遗传算法的第一步是将x编码为有限长度的串。编码的方法很多，这里仅举一种简单易行的方法。遗传算法的基本操作对于多峰值问题的求解很容易陷入局部极值。而遗传算法则是从一个种群（由若干个串组成，每个串对应一个自变量值）开始，不断地产生和测试新一代的种群。这种方法一开始便扩大了搜索的范围，因而可期望较快地完成问题的求解。初始种群的生成往往是随机产生的。对于本例，若设种群大小为4，即含有4个个体，则需按位随机生成4个5位二进制串，如可以通过掷硬币的方法来生成随机的串。遗传算法的基本操作若用计算机，可考虑首先产生0-l之间均匀分布的随机数．然后规定产生的随机数在0-0.5之间代表0，0.5-1之间的随机数代表1。若用上述方法，随机生成以下4个位串：01101，11000，01000，10011。位串1-4可分别解码为如下十进制的数遗传算法的基本操作位串1位串3位串2遗传算法的基本操作这样便完成了遗传算法的准备工作。位串4选择、交叉和变异。下面来介绍遗传算法的3个基本操作步骤遗传算法的基本操作01适应度越大，被选中的概率就越大．从而遗传到下一代的概率越大。优良个体在种群中具有较强的繁殖能力，而适应度较差的个体会受到排挤，甚至被淘汰。在选择算子的作用下，种群的整体质量得到逐步提高。在遗传算法中，以适应度为指标，把当前种群中适应度较高的个体选择出来，为下一步遗传操作做准备。020304遗传算法的基本操作123遗传算法的特点之一是它不对实际决策变量直接进行操作，而是对表示解的个体编码进行选择、交叉、变异等遗传运算。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。好的编码方法可以使得交叉运算、变异运算等遗传操作简单易行，而差的编码方法则可能使得这些操作难以实现。遗传个体编码遗传个体编码假设某一个体的编码是则对应的解码公式为进制编码方法有下述一些优点：编码、解码操作简单易行。遗传个体编码03便于利用模式定理对算法进行理论分析。01交叉、变异等遗传操作便于实现。02符合最小字符集编码原则。遗传个体编码遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数(fitnessfunction)为依据，利用种群中每个个体的适应度值来进行搜索。适应度函数的选取至关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数转换而成的。对目标函数值域的某种映射变换称为适应度的尺度变换。几种常见的适应度函数：直接以待求解的目标函数转化为适应度函数，改进的“界限构造法”和保守估计法。适应度函数的作用：在选择操作时会出现一些问题，如超常个体和种群中个体适应度差异较小的情况。适应度函数的设计：通常，适应度函数设计主要满足以下条件：单值、连续、非负和最大化；合理性和一致性；计算量小；通用性强。适应度函数及其尺度变换遗传算法的实现及改进算法03遗传算法需要提前设定控制参数，包括种群大小、交叉概率、变异概率和终止条件。种群大小影响算法效率，太小会降低多样性，太大则会影响收敛速度。交叉概率一般为0.400～0.990，变异概率在0.001～0.100范围内。遗传算法的实现终止条件分为两类：一类是预先设定的最大函数评价次数NFE，另一类是未找到最优解则终止算法。交叉操作借鉴生物进化中两性繁殖的作用方式，对两个个体进行基因对换操作产生新个体。变异操作通过对染色体的某些基因位点进行突变来产生新的个体，变异的主要作用在于保持种群的多样性。010203遗传算法的实现遗传算法的实现在种群中多数个体趋同的情况下，交叉操作能够产生的不同于父代个体的数量非常有限，甚至重复产生相同的解，而变异操作可以较为有效地异化种群中的个体，增加多样性，从而在一定程度上避免算法陷入早熟收敛。遗传算法的改进研究编码策略是遗传算法的基础工作之一，在问题求解中扮演着重要的角色。实际工程优化问题中的变量往往不能直接被遗传算法作用，需要采用编码策略将实际变量转化为可以被遗传算法直接操作的对象。编码过程实质上是一种“映射”过程，即在优化问题与算法涉及的操作对象之间建立一个一一对应法则。遗传算法的改进研究针对不同的问题，人们提出了不同的编码方式，包括二进制编码、格雷编码和实数编码等。格雷码克服了二进制码的不足，连续两个整数对应的编码之间仅有一个码位不同，其余完全相同。二进制编码具有最小字符编码原理和模式定理，但存在局部搜索能力不强、连续函数离散化误差大、不能反映问题固有结构等缺点。实数编码则针对多维、高精度要求的连续变量优化问题，将每个基因值用实数表示，提高了编码的精度和运行效率。自适应遗传算法中，交叉概率和变异概率的选择是影响算法行为和性能的关键所在。交叉概率越大，新个体产生的速度就越快。然而，当交叉概率过大时，遗传模式被破坏的可能性也会变大。如果交叉概率过小，会使搜索过程变得缓慢，甚至停滞不前。遗传算法的经典变体遗传算法的经典变体变异概率太小，不易产生新的个体结构；太大则变成随机搜索算法。02Srinivas等首次提出一种自适应遗传算法(AdaptiveGeneticAlgorithm，AGA)，其中交叉概率与变异概率能够随着适应度的大小而改变。03当群体中各个个体的适应度值趋于一致或者趋于局部最优时，增加交叉和变异概率；而当群体适应度值比较分散时，减小交叉和变异概率。01遗传算法的经典变体种群中具有最大适应值的个体的交叉概率和变异概率为零，这增大了进化趋向局部最优解的可能性。对适应度值高于群体平均适应度值的个体，给予较低的交叉和变异概率，使该个体得以保护进入下一代；而低于平均适应度值的个体，基于较高的交叉和变异概率，使该个体被淘汰。改进的自适应遗传算法使种群中具有最大适应值的个体的交叉概率和变异概率不为零。VS一个刻画种群多样性的函数，在此基础上提出交叉和变异算子的点数随种群多样性而变化。混合遗传算法的实质是将不同算法的优点有机结合，改善单纯遗传算法的性能。遗传算法的经典变体改进的遗传算法举例01改进的遗传算法在一个高低不同的层次上都使用了遗传算法。02生物模型中，遗传算法是对一个群体进行操作，该群体相当于自然界中的一群人。第一步的选择是以现实世界中的优胜劣汰现象为背景的。03010203第二步的交叉则相当于人类的结婚和生育。第三步的变异则与自然界中偶然发生的变异是一致的。包含着对模式的操作，遗传算法不断地产生出更加优良的个体。改进的遗传算法举例标准遗传算法中的几个典型操作均可与生物（尤其是人类）的进化过程相对应。一个种群进化到某些特征相对优势的状态后便不再有很大变化。正如人类不断向前进化一样。改进的遗传算法举例定期地大量移民和通婚可以打破各个民族的平衡态并推动他们达到更高层的平衡态。人类完全可以有目的地通过和平的方式来进行各民族的移民和通婚，从而达到人类进化的目的。改进的遗传算法举例THANKYOU感谢观看第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）。若其值在预定的范围内变化．那么密码子的参数和实际