搜索
遗传算法GeneticAlgorithm(GA)主要内容•遗传算法简介–基本原理–研究进展•遗传算法的流程–流程结构–应用举例•遗传算法的改进–算子选择–参数设置–混合遗传算法–并行遗传算法•遗传算法的应用–遗传算法在生物信息学中的应用遗传算法是什么？遗传算法（GeneticAlgorithm，GA）是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。遗传算法的思想来源是怎样的？它由谁提出的？GA思想源于自然界“自然选择”和“优胜劣汰”的进化规律，通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。它最早由美国密歇根大学教授JohnH.Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。遗传算法简介•产生60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。•70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；•发展1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了《遗传算法手册》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。•达尔文(Darwin)的进化论–进化论是生物学最基本的理论之一。生物学上的所谓进化或者演化（Evolution），旧称“天演”，是指生物在变异、遗传与自然选择作用下的演变发展，物种淘汰和物种产生过程。地球上原来无生命，大约在30多亿年前，在一定的条件下，形成了原始生命，其后，生物不断的进化，直至今天世界上存在着170多万个物种。–达尔文用自然选择来解释生物进化。自然选择就是指生物由于环境中某些因素的影响而使得有利于一些个体的生存，而不利于另外一些个体生存的演化过程。–简而言之——物竞天择，适者生存•达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。•孟德尔(Mendel)的遗传学–遗传学是研究基因及它们在生物遗传中的作用的科学分支。遗传学最早的应用在有历史记载之初就已经出现了，即驯养动物及植物的选择育种。遗传信息以化学方法被编码在DNA（脱氧核糖核酸）中。–1865年，孟德尔首先记录了豌豆某些特性的遗传模式，表明它们遵守简单的统计学规律。由他的统计分析中，孟德尔定义了一个概念：遗传的基本单位——等位基因。他描述的等位基因类于现在的基因。直到孟德尔死后，20世纪初另外的科学家重新发现这个定律之后，孟德尔的工作的重要性才被大家了解。–改变一个生物的DNA从而达到某种目的被称为基因工程。种群淘汰的个体新种群淘汰选择交配变异群体父代染色体1父代染色体2子代染色体1子代染色体2生物进化过程遗传基因重组过程群体竞争淘汰的群体变异子群种群婚配生物遗传学基础•遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；•遗传学基本概念与术语基因型（genotype）：遗传因子组合的模型，染色体的内部表现；表现型（phenotype）：由染色体决定性状的外部表现，基因型形成的个体；ATCGTAATCATA•遗传学基本概念与术语个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；种群大小：种群中个体的数量，也叫群体规模。•遗传学基本概念与术语进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：个体性能的数量值，度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;•遗传学基本概念与术语选择（selection）：指决定以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;•遗传学基本概念与术语变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。•进化论与遗传学的融合1930～1947年，达尔文进化论与遗传学走向融合，Th.Dobzhansky1937年发表的《遗传学与物种起源》是融合进化论与遗传学的代表作。•生物进化与智能学的关系生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。•如何借鉴？–对于一个优化问题，一定数量的候选解（生命个体）被表示为抽象的数字串（染色体），通过进化向更好的解发展。–选解一般为二进制数字串（即0和1），但也可能有其他表示。一开始，生命个体完全随机产生，之后一代一代的进化，在进化过程中的每一代，每一个个体的适应程度被评价，通过自然选择和变异产生新的生命群体，该群体就是下一代的个体。选择运算群体p(t)交叉运算变异运算解码群体p(t+1)解集合个体评价遗传空间解空间编码遗传算法原理•在遗传算法中，问题的每个有效解被称为一个“染色体(chromosome)”，也称为“串”，对应于群体中的每个生物个体(individual）。•染色体的具体形式是一个使用特定编码方式生成的编码串，编码串中的每一个编码单元称为基因(gene)•遗传算法通过比较适应值(fitnessvalue)区分染色体的优劣，适应值越大的染色体越优秀。•评估函数(evaluationfunction)用来计算并确定染色体对应的适应值。遗传算法原理•选择算子(selection)按照一定的规则对群体的染色体进行选择，得到父代种群。一般情况下，越优秀的染色体被选中的次数越多。•交叉算子(crossover)作用于每两个成功交配的父代染色体，染色体交换各自的部分基因，产生两个子代染色体。子代染色体取代父代染色体进入新种群，而没有交配的染色体则直接进入新种群。•变异算子(mutation)使新种群进行小概率的变异。染色体发生变异的基因改变数值，得到新的染色体。经过变异的新种群替代原有群体进入下一次进化。•遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。•遗传算法对求解问题的本身一无所知，它所需要的仅仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。•在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。再对这个新种群进行下一轮进化。这就是遗传算法的基本原理。遗传算法原理遗传算法原理•Holland给出了著名的模式定理(SchemaTheory)，为遗传算法提供了理论支持。•模式(schema)是指群体中编码的某些位置具有相似结构的染色体集合。假设染色体的编码是由0或1组成的二进制符号序列，模式01***0则表示以01开头且以0结尾的编码串对应的染色体的集合，即{010000，010010，010100，010110，011000，011010，011100，011110}。遗传算法原理•模式的阶(schemaorder):模式中具有确定取值的基因个数。如模式01***0的阶为3•模式的定义长度(schemaddefininglength)是指模式中第一个具有确定取值的基因到最后一个具有确定取值的基因的距离，例如模式01***0的定义长度为5而模式*1****的定义长度为0遗传算法原理•Holland的模式定理提出，遗传算法的实质是通过选择、交叉、变异的遗传算子对模式进行搜索。•低阶、定义长度较小且平均适应值高于群体平均适应值的模式在群体中的比例将呈指数级增长。•随着进化的不断进行，较优染色体的个数将快速增加。•模式定理证明了遗传算法寻求全局最优解的可能性，但不能保证算法一定能找到全局最优解。遗传算法原理•积木块假设(BuildingBlockHypothesis)，对模式定理做了补充，说明遗传算法具有能够找到全局最优解的能力。•积木块(buildingblock)是指低阶、定义长度较小且平均适应值高于群体平均适应值的模式。•积木块假设认为在遗传算法运行过程中，积木块在遗传算子的影响下能够相互结合，产生新的更加优秀的积木块，最终接近全局最优解。研究内容和方向遗传算法的流程•七个重要问题:–染色体的编码–群体的初始化–适应值评价–选择群体–种群交配–种群变异–算法流程选择运算群体p(t)交叉运算变异运算解码群体p(t+1)解集合个体评价遗传空间解空间编码染色体的编码•原因：遗传算法只能处理染色体，不能直接在问题解集上进行相应操作。•应用遗传算法,需要解决问题解的表示,即染色体的编码•编码:将问题结构变换为位串形式编码表示的过程；•解码或译码:将位串形式编码表示变换为原问题结构的过程。解空间一个解的编码染色体(chromosome)编码解码•编码方法–二进制编码方法–浮点数编码方法–格雷码(Gray)–符号编码二进制编码方法产生的染色体是一个二进制符号序列，染色体的每一个基因只能取值0或1。假定问题定义的有效解取值空间为[Umin，Umax],其中D为有效解的变量维数，使用L位二进制符号串表示解的一维变量，则我们可以得到如表4.2所示的编码方式:•二进制编码方法假设[Umin，Umax]为[1,64]，采用6位二进制符号串进行编码，则某个二进制符号串010101代表了数值22L位二进制编码的精度为:二进制编码的最大缺点是长度较大，当要求采用较高的精度或表示较大范围的数时，必须通过增加L来达到要求。●一维染色体编码指问题空间映射到染色体空间后，其相应的基因呈一维排列构成染色体。一维染色体常用的符号集是二值符号集{0，1}●如果问题解空间是整数，其编码需要两步确定1.确定编码长度。如果问题解空间范围为x，那么编码长度为2.确定编码xl2log●确定编码，将整数转换为二进制表示形式。方法：除2取余法。例如：9=(1001)2910014210●如果所求解空间包含负值。如果解空间为整数，可使用添加符号位的方法解决，即正数符号位为0，负数为1+9=(01001)2-9=(11001)2如果所求解空间为实数空间？1.确定编码长度假设范围：[a,b]精度：小数点后