您好,欢迎访问三七文档
第2章进化计算2.1进化计算导论进化是一个优化过程,目的是在不断变化的竞争环境中提高某生物(或系统)的生存能力。几个世纪以来,进化作为一个概念,曾被激烈地讨论过。直到今天,它仍是一个备受关注的话题。在不同的领域,进化可以有不同的解释。而本课程所关注的是生物中的进化概念。目前,生物进化仍是一个存在大量争论的概念,对于它的定义,Lamarckian和Darwinian的观点现已被广泛接受。Darwin(1809-1882)被认为是进化理论和共同起源法则的奠基人,而Lamarck(1744-1829)可能是把生物进化理论化的第一人。Jean-BaptisteLamarck的进化理论是关于遗传的,如获得性状的遗传。其主要观点是生物个体在生命期中逐渐适应环境,并将性状传给后代,后代也能不断适应。根据Lamarck的理论,适应的过程依赖于使用和丢弃这两个概念:在一段时间中,生物个体丢弃掉它所不需要的性状,表现出它需要的性状。CharlesDarwin的自然选择学说是生物进化的基础。Darwin的进化论可以描述为:在一个资源有限、种群稳定的世界中,每个生物个体都会与其他生物个体为了生存而竞争。拥有优良性状的个体会更加容易获得生存和繁殖的机会,它的性状也更易于传给后代。这些优良性状被下一代继承,经过一段时间便成为种群中的主要性状。Darwin理论的第二部分提到,在幼年生物体的发育过程中,随机事件会导致幼年生物体性状的随机改变。如果新出现的性状有益于生物体,则该生物获得生存的概率会有所提高。进化计算(EC)是指以进化过程作为计算模型的问题解决系统。如自然选择、适者生存、繁殖等都是这个问题解决系统的基本组成部分。Lamarck进化论一切物种都是其他物种演变和进化而来的,而生物的演变和进化是一个缓慢和连续的过程。环境的变化能够引起生物的变异,环境的变化迫使生物发生适应性的进化。有神经系统的动物发生变异的原因,除了环境变化和杂交外,更重要是通过用进废退和获得性状遗传。生物进化的方向从简单到复杂,从低到高。最原始的生物起源于自然发生。生物并不起源于共同祖先。拉马克曾以长颈鹿的进化为例,说明他的“用进废退”观点。长颈鹿的祖先颈部并不长,由于干旱等原因。在低处已找不到食物,迫使它伸长脖颈去吃高处的树叶,久而久之,它的颈部就变长了。一代又一代,遗传下去,它的脖子越来越长,终于进化为现在我们所见的长颈鹿。Darwin进化论包括两部分:遗传(基因)变异;自然选择生物不是静止的,而是进化的。物种不断变异,旧物种消灭,新物种产生。生物的进化是连续和逐渐,不会发生突变。生物之间存在一定的亲缘关系,他们具有共同的祖先。自然选择。生物过渡繁殖,但是它们的生存空间和食物有限,从而面临生存斗争,包括:种内、种间以及生物与环境的斗争。自然选择是达尔文进化论的核心。孟德尔学说1857年,身为神父,孟德尔通过对植物进行一系列仔细的实验。孟德尔发现植物的父母单独地把自身的性状传递给子。至关重要的是,他还发现性状不是单纯地混合在一起,而是保持着独立性:一株高的植物和一株矮的植物繁殖出来的后代要么是高的,要么是矮的,而不是介于两者之间。表明性状是分开独立地遗传给下一代,后来这称为遗传基因。让人惊奇的是,孟德尔的重要发现被人们忽略了数十年,直到20世纪初才被人们认可。孟德尔学说1、分离定律:基因作为独特的独立单位而代代相传。细胞中有成对的基本遗传单位,在杂交的生殖细胞中,一个来自雄性亲本,一个来自雌性亲本.2、独立分配定律:在一对染色体上的基因对中的等位基因能够独立遗传。孟德尔的这两条遗传基本定律就是新遗传学的起点,孟德尔也因此被后人称为现代遗传学的奠基人。新达尔文主义将达尔文进化论和孟德尔-摩根基因相结合,成为现被广泛接受的新达尔文主义。新达尔文注意认为,只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史,这些过程就是繁殖、变异、竞争、选择。繁殖是所有生命的共同特性;变异保证了任何生命系统能在正熵世界中连续繁殖自己;对于限制在有限区域中的不断膨胀的种群来说,竞争和选择是不可避免的结论。生物学中的遗传概念在生物细胞中,控制并决定生物遗传特性的物质是脱氧核糖核酸,简称DNA。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如,改变DNA长链中的特定一段(称为基因),即可改变人体的身高。细胞在分裂时,DNA通过复制而转移到新产生的细胞中,新的细胞就继承了上一代细胞的基因。生物学中的遗传概念有性生殖生物在繁殖下一代时,两个同元染色体之间通过交叉而重组,亦即在两个染色体的某一相同位置处DNA被切断,其前后两串分别交叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错,从而使DNA发生某种变异,产生新的染色体。这些新的染色体将决定新的个体(后代)的新的性状。生物学中的遗传概念在一个群体中,并不是所有的个体都能得到相同的繁殖机会,对生存环境适应度高的个体将获得更多的繁殖机会;对生存环境适应度较低的个体,其繁殖机会相对较少,即所谓自然选择。而生存下来的个体组成的群体,其品质不断得以改良,称为进化。生物的进化是经过无数次有利的进化积累而成的,不同的环境保留了不同的变异后代!TimeInitialpopulation(初始种群)Select(选择)Crossover(交叉)AnotherCrossoverAmutation(变异)AnotherMutationOldpopulation+childrenNewPopulation:Generation2Generation3Generation4,etc…遗传算法的基本思想首先实现从性状到基因得映射,即编码工作,然后从代表问题可能潜在解集得一个种群开始进行进化求解。初代种群(编码集合)产生后,按照优胜劣汰的原则,根据个体适应度大小挑选(选择)个体,进行复制、交叉、变异,产生出代表新的解集的群体,再对其进行挑选以及一系列遗传操作,如此往复,逐代演化产生出越来越好的近似解。概念说明选择:通过适应度的计算,淘汰不合理的个体。类似于自然界的物竞天择.复制:编码的拷贝,类似于细胞分裂中染色体的复制。交叉:编码的交叉重组,类似于染色体的交叉重组。变异:编码按小概率扰动产生的变化,类似于基因的突变。这个过程将导致种群像自然进化一样,后代种群比前代更加适应环境,末代种群中得最优个体经过解码(从基因到性状的映射),可以作为问题近似最优解。遗传算法历史1965年,Holland首次提出人工遗传操作的重要性,并把这些应用于自然系统和人工系统中。1967年,Bagley在他的论文中首次提出了遗传算法这一术语,并讨论了遗传算法在自动博弈中的应用。1970年,Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。遗传算法历史1975年Holland出版了他的著名专著《自然系统和人工系统的适应性》该书系统地阐述了遗传算法的基本理论和方法,并提出了对遗传算法极为重要的模式理论,该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年,DeJong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑。遗传算法历史在一系列研究工作的基础上,上世纪80年代由Goldberg进行归纳总结,形成了遗传算法的基本框架。产生初始种群计算适应度是否满足优化准则最佳个体选择交叉变异解码(基因到性状)YN父代子代开始结束2.1.1一般进化算法借助于对随机选择的若干个体进行自然选择的进化过程,可以被看作是在染色体值空间中的一个搜索过程。在这个意义上,进化算法就是一种对给定问题求最优解的随机搜索方法。该进化搜索主要受到以下几个部分的影响。(1)编码:与染色体一样,对问题的解编码。(2)适应度函数:用于求适应度的函数,表征个体的生存能力。(3)初始化:种群的初始化。(4)选择:选择算子。(5)繁殖(reproduction):繁殖算子。一个通用的进化算法:一般进化算法令代数计数器t=0;创建和初始化nx维的群体pop(0),包含ns个个体;While终止条件不为真do获得每个个体xi(t)的适应度值f(xi(t));采用复制算法来产生后代;选择新群体pop(t+1);进入下一代,即t=t+1;end编码在进化计算中,每个个体都代表一个优化问题的备选解;个体的性状由染色体(也叫基因组)表示。而性状是指最优化问题所搜索的变量,每个需要优化的变量被称为基因——携带信息的最小单位。这些变量在可行域中的一组值叫等位基因。个体的性状可以被分为两类进化信息:基因型和表现型。基因型描述了个体的基因组成,它继承于父代。表现型是一个个体在特定环境里所表现出的行为特征,它定义了个体的样貌。在设计进化算法中,一个重要的步骤是找到备选解的合适的表示方案(如染色体)。搜索算法的效率与复杂性很大程度上依赖于这个表示方案。不同典型方法中的不同进化算法往往使用不同的表示方案。多数进化算法把解表示为某种数据类型的向量,但遗传编程是个例外,它把个体表示为树的形式。以遗传算法为例进行说明解空间一个解的编码染色体编码其中的一个码和码所在的位置基因/基因位求下述二元函数的最大值:遗传算法的运算对象是表示个体的符号串,所以必须把变量x1,x2编码为一种符号串。本题中,用无符号二进制整数来表示。因x1,x2为0~7之间的整数,所以分别用3位无符号二进制整数来表示,将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型,表示一个可行解。例如,基因型X=101110所对应的表现型是:x=[5,6]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。初始种群进化算法是一种基于种群的随机搜索算法。因此,每个进化算法都会维护一个由备选解构成的种群。应用进化算法解决优化问题的第一步是产生一个初始种群。产生初始种群的标准方法是在可行域中产生随机值,并分配给每个染色体的每个基因。随机选择的目标是确保初始种群为整个搜索空间的均匀表示。如果初始种群没有覆盖搜索空间,则有可能使得未覆盖区域被搜索过程所忽略。初始种群的大小会影响计算复杂性和空间搜索能力。大量的个体能增加多样性,进而提高种群的空间搜索能力。然而,个体越多,每代的计算量越大。当每代的计算时间增加时,可能只需要较小的代数便能找到可以接受的解;另一方面,如果一个种群的个体数量较小,则只能探索空间中的较小部分。虽然每代的计算时间减少了,但进化算法需要更多的代数才能收敛得到一个与大种群相当的结果。X1=[011101]=[x1,x2]=[3,5]X2=[101011]=[x1,x2]=[5,3]X3=[011100]=[x1,x2]=[3,4]X4=[111001]=[x1,x2]=[7,1]遗传算法是对群体进行的进化操作,需要给其淮备一些表示起始搜索点的初始群体数据。本例中,群体规模的大小取为4,即群体由4个个体组成,每个个体可通过随机方法产生。适应度函数在达尔文式的进化模型里,拥有最好性状的个体获得生存和繁殖的机会更大。在进化算法中,为确定一个个体的生存能力,我们用一个数学函数来表征染色体所表示的解有多好。所谓适应度函数f,将把一个染色体映射成一个标量值:f:Гnx→R式中,Г代表nx维染色体元素的数据类型。适应度函数可以用目标函数来表示。本例中,目标函数总取非负值,并且是以求函数最大值为优化目标,故可直接利用目标函数值作为个体的适应度。注意:不同的优化问题要求适应度函数的形式不同。(1)在无约束优化问题中,适应度函数即为目标函数。(2)在带约束的优化问题中,进化算法的适应度函数要包含两个目标:一个原始的目标函数,另一个是约束惩罚函数。(3)在多目标优化问题(MOP)中,可以通过带权重的聚集方法解决,适应度函数为全部子目标的加权和。另一种解决方法为基于Pareto的优化算法。(4)在动态和噪声问题中,解的函数值随着时间
本文标题:第2章进化计算
链接地址:https://www.777doc.com/doc-2155256 .html