ComputationalIntelligence(2)

1,Chapter5:计算智能（2）：进化计算、人工生命,Outline5.1遗传算法5.2进化策略5.3进化编程5.4人工生命5.5小结,2,Chapter5:计算智能（2）：进化计算、人工生命,进化计算（EvolutionaryComputation）是通过模拟自然界中生物进化机制进行搜索的一种算法。生物进化论进化计算主要包括：遗传算法（GeneticAlgorithm,GA）进化策略（EvolutionStrategy）进化编程（EvolutionaryProgramming）或进化规划（EvolutionaryPlanning）,3,Chapter5:计算智能（2）：进化计算、人工生命,进化计算的研究起源于20世纪50年代。1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。1960年代，Rechenberg和Schwefel提出了进化策略;同一时期，Fogel,Owens和Walsh提出了进化规划。1975年，Holland出版了他的著名专著自然系统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法。1990年，Koza提出了遗传规划（GeneticProgramming）的概念，用于搜索解决特定问题的最适计算机程序。,4,5.1遗传算法,1960年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。遗传算法（GA）思想来源于生物进化过程,它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法。GA是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式，它为那些难以找到传统数学模型的难题提供了解决方法。特点：通用性鲁棒性（robustness）并行性次优解、满意解,5,5.1遗传算法,GA先将搜索结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。,6,5.1遗传算法,与自然界相似，GA对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在GA中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有复制、杂交、变异和反转。,7,5.1遗传算法,GA与传统优化方法的不同GA不是直接作用在参变量集上,而是利用参变量集的某种编码;GA不是从单个点,而是在群体中从一个点开始搜索;GA利用适应值信息,无需导数或其它辅助信息;GA利用概率转移规则,而非确定性规则。使用GA的几个关键确定表示方案;确定适应值的度量;确定控制该算法的参数和变量;确定程序运行结束的标准。,8,5.1遗传算法,GA的基本原理以Holland的基本遗传算法(SimpleGeneticAlgorithm，SGA)亦即简单遗传算法为例进行解释。SGA只使用选择算子、交叉算和变异算子这三种基本的遗传算子。其遗传操作简单、容易理解，是其它GA的雏形和基础。,9,5.1遗传算法,SGA的基本要素染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。适应度函数（fitnessfunction，又称为适应值适值函数）用来评价一个染色体的好坏。遗传算子选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。,10,5.1遗传算法,SGA的参数设置N：群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为0.40.99。Pm：变异概率，一般取为0.00010.1。,11,5.1遗传算法,SGA的求解步骤(1)初始化群体;(2)计算群体上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4)按概率Pc进行交叉操作;(5)按概率Pm进行突变操作;(6)若没有满足某种停止条件，则转第(2)步，否则进入下一步。(7)输出群体中适应度值最优的染色体作为问题的满意解或最优解。,12,5.1遗传算法,SGA的框图,13,5.1遗传算法,一般遗传算法的步骤(1)随机产生一个由确定长度的特征字符串组成的初始群体。(2)对该字符串群体迭代的执行下面的步和，直到满足停止标准：计算群体中每个个体字符串的适应值；应用复制、交叉和变异等遗传算子产生下一代群体。(3)把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。,产生初始群体,是否满足停止准则,计算每个个体的适应值,i=N?,GEN:=GEN+1,依概率选择遗传操作,执行复制,选择一个个体,i:=i+1,选择两个个体,选择一个个体,执行变异,i:=0,GEN:=0,复制到新群体,i:=i+1,将两个后代插入新群体,插入到新群体,执行杂交,指定结果,结束,是,否,是,否,变异,复制,交叉,基本遗传算法框图,15,遗传算法举例,问题：求（1）编码：此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011解码：1324819适应度：16957664361（3）适应度评价：,（4）选择：选择概率个体：01101，11000，01000，10011适应度：16957664361选择概率：0.140.490.060.31选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的（单点交叉）0110101100110001101111000110011001110000,遗传算法举例,轮盘式选择,首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇形，每个扇形的大小为。选择时转动轮盘，参考点r落到扇形i则选择个体i。,（6）变异：发生变异的概率很小（7）新群体的产生：保留上一代最优个体，一般为10%左右，至少1个用新个体取代旧个体，随机取代或择优取代。11000，11011，11001，10011（8）重复上述操作，直至满足某个条件而终止程序运行。说明：GA的终止条件一般人为设置；此外，GA通常只能求次优解或满意解。,遗传算法举例,19,5.2进化策略,20世纪60年代，德国柏林工业大学的I.Rechenberg和H.P.Schwefel等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法进行优化，因而利用生物变异的思想来随机改变参数值，获得了较好的结果。随后，他们对这种方法进行了深入的研究和发展，形成了一种新的进化计算方法进化策略(EvolutionStrategy,简称ES)。,20,5.2进化策略,早期的进化策略可以被看成使用浮点数表达，只使用变异作为其重组算子的一种进化计算方法。它主要用于各种带连续可变参数的优化问题。其基本思想为：随机产生一个适用于所给问题环境的初始种群，即搜索空间，种群中的每个个体为实数编码，计算每个个体的适应值；依据达尔文的进化原则，选择遗传算子(重组、突变等)对种群不断进行迭代优化，直到在某一代上找到最优解或近似最优解。,21,5.2进化策略,最早的进化策略只是基于单个个体组成的种群而进化的，且在进化过程中只使用变异算子。独特之处在于，个体被表达成一对浮点数组成的向量，其中x表示搜索空间的一个点，而表示标准偏差向量。变异是通过如下的方式实现的：变异之后的个体（后代）当且仅当有较好的适应值且满足所有的约束（如果有的话）时，才会被接收为种群的新成员。,22,5.2进化策略,虽然种群是由经历变异的单个个体组成，但是后代和父代进行竞争，而且在竞争阶段种群中临时地包含两个个体，因此，上述的进化策略被称为“两成员进化策略”，即“1+1-ES”。1973年，Rechenberg进行了多父代方法的早期工作，但还是采用单子代。1981年，Schwefel在Rechenberg工作的基础上迈进一步，研究了多父代和多子代的进化策略。,23,5.2进化策略,(+)ES和(,)ES这两种进化策略都采用含有个个体的父代群体，并通过重组和突变产生个新个体。它们的差别仅仅在于下一代群体的组成上。(+)ES是在原有个个体及新产生的个新个体中共（+）个个体，再择优选择个个体作为下一代群体。(,)ES则是只在新产生的个新个体中择优选择个个体作为下一代群体，这时要求。总之，在选择子代新个体时若需要根据父代个体的优劣进行取舍，则使用“+”记号，如(1+1)、(+1)及(+)；否则，改用逗号分隔，如(,)。近年来，(,)ES得到广泛的应用，这是由于这种进化策略使每个个体的寿命只有一代，更新进化很快，特别适合于目标函数有噪声干扰或优化程度明显受迭代次数影响的课题。,24,5.2进化策略,进化策略执行过程1）确定问题的表达方式个体由目标变量X和标准差两部分组成，每部分又可以有n个分量，即,25,5.2进化策略,进化策略执行过程2）随机生成初始群体，并计算其适应度。进化策略中的初始群体由个个体组成，每个个体的内又可以包含n个Xi、i分量。产生初始个体的方法是随机生成。为便于和传统的方法比较，可以从某个初始点出发，通过多次突变产生个初始个体，该初始点可从可行域中用随机方法选取。初始个体的标准差(0)=3.0。3）计算初始个体的适应度，如若满足条件，终止；否则，往下进行。,26,5.2进化策略,进化策略执行过程4）根据进化策略，用下述操作产生新群体：4.1)重组：将两个父代个体交换目标变量和标准差，产生新个体。一般目标变量采用离散重组，标准差采用中值重组。离散重组：对父代中两个个体实行随机交叉组合。中值重组：从个父代个体中用随机的方法任选两个个体，然后将父代个体各分量的平均值作为子代新个体的分量，构成的新个体。4.2)突变：对重组后的个体添加随机量，按照前述变异算子产生新个体。4.3)计算新个体适应度。4.4)选择：实行(+)或(,)选择策略，挑选一部分个体组成下一代群体。5）反复执行第4步，直到达到终止条件，选择最佳个体作为进化策略的结果。,27,5.2进化策略,进化策略与遗传算法的主要区别进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原理的算法。两者也存在着区别，其中最基本的区别是它们的研究领域不同。进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法。遗传算法从广义上说是一种自适应搜索技术。,28,5.3进化编程,进化编程(EvolutionaryProgramming，EP)，又称为进化规划（EvolutionaryPlanning），是由Fogel在1962年提出的一种模仿人类智能的方法。进化编程根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。它的提出是受自然生物进化机制的启发。,29,5.3进化编程,进化编程的过程，可理解为从所有可能的计算机程序形成的空间中，搜索具有高的适应度的计算机程序个体。进化编程设计强调群体行为的变化。进化编程系统的表示自然地面向任务级。一旦选定一种适应性表示，就可以定义依赖于该表示的变异操作，在具体的父辈行为上创建后代。,30,5.3进化编程,进化编程分为三个步骤：产生出初始群体。迭代完成下述子步骤，直至满足选种标准为止：执行群体中的每个程序。应用变异等操作创造新程序群体。在后代中适应值最高的计算机程序个体被指定为进化编程的结果。,进化编程的基本过程,32,5.4人工生命,自然界是生命之源。自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无穷。人工生命（ArtificialLife，AL）试图通过人工方法建造具有自然生命特征的人造系统。人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。,33,5.4人工生命,人工生命研究的起源和发展人类长期以来一直力图用科学技术方法模拟自然界，包括人脑本身。1943年McCulloch和Pitts提出了MP神经学网络模型。1948年Winner提出控制论，对动物与机器中的控制和通信问题进行研究。VonNeumann研究脑和计算机在组织上的相似性，用形式逻辑来表示脑。人工生命的许多早期研究工作也源于人工智能。Rosenblatt提出的感知机（perceptron）Stahl建立的细胞活动模型1970年代以来，Conrad等提出不断完善的“人工世界”模型以及Conway提出的细胞自动机对策论。1980年代，在美国，以圣塔菲研究所和MIT等机构为首设立了人工生命的研究组织，出版了学术专刊ArtificialLife，组办了人工生命方面的国际会议。1991年，欧洲人工智能学会开始举办ECAL(EuropeanConferenceonArtificialLife)会议；1996年，日本开始举办TheInternationalSymposiumonArtificialLifeandRobotics，并出版ArtificialLifeandRobotics国际学术刊物。1997年，在中国北京举行国内关于人工生命的第一次学术活动。,34,5.4人工生命,人工生命的定义和研究意义人工生命是一项抽象地提取控制生物现象的基本动态原理，并且通过物理媒介（如计算机）来模拟生命系统动态发展过程的研究工作。通俗地讲，人工生命即人造的生命，非自然的生命。然而，要对人工生命做出严格的定义，却需要对问题进行深入研究。,35,5.4人工生命,人工生命的定义和研究意义1987年兰德提出的人工生命定义为：“人工生命是研究能够演示出自然生命系统特征行为的人造系统”。通过计算机或其它机器对类似生命的行为进行综合研究，以便对传统生物科学起互补作用。兰德在计算机上演示了他们研制的具有生命特征的软件系统，并把这类具有生命现象和特征的人造系统称为人工生命系统。,36,5.4人工生命,人工生命的定义和研究意义自然生命的共同特征和现象自繁殖、自进化、自寻优自成长、自学习、自组织自稳定、自适应、自协调物质构造能量转换信息处理,37,5.4人工生命,研究人工生命的意义人工生命是自然生命的模拟、延伸与扩展，其研究开发有重大的科学意义和广泛的应用价值。开发基于人工生命的工程技术新方法、新系统、新产品为自然生命的研究提供新模型、新工具、新环境延伸人类寿命、减缓衰老、防治疾病扩展自然生命，人工进化、优生优育促进生命、信息、