第5章 计算智能（2）.ppt

1、第5章 计算智能(2),进化计算 人工生命,2,进化计算（算法）包括： 遗传算法(genetic algorithms，GA) 进化策略(evolution strategies) 进化编程(evolutionary programming) 遗传编程(genetic programming) 人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。 人工生命是人工智能和计算智能的一个新的研究热点。进化计算为人工生命提供计算理论和有效的开发工具。,3,5.1 遗传算法,遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行

2、的一种数学仿真，是进化计算的最重要的形式。 遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。 进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。,4,5.1.1 遗传算法的基本机理,霍兰德75的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适当的改进，来分析遗传算法的结构和机理。 编码与解码 适应度函数 遗传操作,5.1 遗传算法,5,编码与解码,许多问题的结构可以简化为位串编码表示 编码：将问题结构变换为位串形式编码表示的过程为编码 解码：将位串形式编码表示变换为问题结构的过程为解码 GA首先在解空间中选择一群点为初始，每个

3、点为二进制数字串（基因），其优劣程度由适应度函数来衡量,6,编码与解码,二进制编码：简单，但长度较大 浮点数编码：每个染色体用某个范围内的浮点数表示，个体编码的长度等于其问题的变量个数（浮点数向量），也称为真值编码方法，适用于多维、高精度要求的连续函数 格雷码：连续的两个整数所对应的编码值之间只有一个位不同，其它完全相同 符号编码：取自一个无数值含义而只有代码含义的符号集,7,适应度函数,评价函数，表示基因的适用能力，也就是基因的优劣程度 要有效地反映每个染色体与问题的最有解染色体之间的差距,8,遗传操作,选择操作：也称为复制操作，根据个体的适应度函数值所度量的优劣程度决定在下一代是被淘汰还是

4、被遗传，赌轮选择机制 交叉操作：两个个体基因字串部分值进行交换 变异操作：改变基因串上某位数码,9,5.1.2 遗传算法的求解步骤,遗传算法是一种基于空间搜索的算法，是一个最优化的过程。 1. 遗传算法的特点 (1) 遗传算法是对参数集合的编码而非针对参数本身进行进化 (2) 遗传算法是从问题解的编码组开始而非从单个解开始搜索 (3) 遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索； (4) 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。 利用简单的编码技术和繁殖机制来表示负责现象。同时能够并行操作,5.1 遗传算法,10,2. 遗传算法的框图(

5、图5.2),(1) 随机方式形成染色体，初始化群体; (2) 计算群体上每个个体的适应度值; (3) 按由个体适应度值所决定的某个规则选 择将进入下一代的个体; (4) 按概率Pc进行交叉操作; (5) 按概率Pc进行突变操作; (6) 若没有满足某种停止条件，则转第(2)步， 否则进入下一步。 (7) 输出群体中适应度值最优的染色体作为问题的满意解或最优解。 停止条件：进化代数限制；没有明显进化；,5.1 遗传算法,11,图5.2 算法框图,5.1 遗传算法,12,一般遗传算法的主要步骤如下： (1) 随机产生一个由确定长度的特征字符串组成的初始群体。 (2) 对该字符串群体迭代的执行下面的

6、步和 ，直到满足停止标准： 计算群体中每个个体字符串的适应值； 应用复制、交叉和变异等遗传算子产生下一代群体。 (3) 把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。,5.1 遗传算法,13,产生初始群体,是否满足停止准则,计算每个个体的适应值,i=M?,GEN:=GEN+1,依概率选择遗传操作,执行复制,选择一个个体,i:=i+1,选择两个个体,选择一个个体,执行变异,i:=0,GEN:=0,复制到新群体,i:=i+1,将两个后代插入新群体,插入到新群体,执行杂交,指定结果,结束,是,否,是,否,变异,复制,交叉,5.1 遗传算法,14,遗传算法的一

7、般结构表示,Procedure: Genetic Algorithms begint 0;initialize P(t);evaluate P(t);while (not termination condition ) dobeginrecombine P(t) to yield C(t);evaluate C(t);select P(t+1) from P(t) and C(t);t t+1;end end,5.1 遗传算法,15,3. 遗传算法求解举例,5.1 遗传算法,用遗传算法求解函数 f(x)=x*sin(10pi*x)+1.0 的最大值，变量的取值范围【1，2】 染色体表示，二进制

8、表示方法 种群初始化 适应度函数 遗传操作 算法参数：种群规模，算法执行次数、复制概率、杂交概率和变异概率,16,遗传算法归纳为五个基本组成部份,方案表示 群体初始化 适应度函数 遗传操作 算法参数,5.1 遗传算法,17,5.2 进化策略,进化策略(Evolution Strategies，ES)是一类模仿自然进化原理以求解参数优化问题的算法。 它是由雷切伯格（Rechenberg）、施韦费尔（Schwefel）和彼得比纳特（Peter Bienert）于1964年提出的，并在德国共同建立的。,18,5.2.1 进化策略的算法模型,寻求与函数极值关联的实n维矢量x。 随机选择父矢量的初始群体

9、。 父矢量xi, i=1,p产生子代矢量xi以及预先选择x的标准偏差来产生子代矢量xi 。 对误差 (i=1,p)排序以选择和决定保持哪些矢量，最小误差为选择对象。 继续产生新的试验数据以及选择最小误差矢量。,5.2 进化策略,19,5.2.2 进化策略和遗传算法的区别,进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原理的算法。 两者也存在着区别，其中最基本的区别是它们的研究领域不同。 进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法。 遗传算法从广义上说是一种自适应搜索技术。,5.2 进化策略,20,除了研究领域不同，还有：,表示个体的方式不同：二进制

10、矢量和浮点矢量 选择的过程不同 复制参数不同，遗传算法参数恒定，但是进化策略是变化的,21,5.3 进化编程,进化编程(Evolutionary Programming，EP)，又称为进化规划（Evolutionary Planning），是由福格尔（Fogel）在1962年提出的一种模仿人类智能的方法。 进化编程根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。 它的提出是受自然生物进化机制的启发。,22,为有限状态机的演化而提出进化规划来预测问题 状态机的状态变化表是通过对应的离散有界集上进行均匀随机变异来修改,23,

11、5.3.1 进化编程的机理与表示,进化编程的过程，可理解为从所有可能的计算机程序形成的空间中，搜索具有高的适应度的计算机程序个体。 进化编程设计强调群体行为的变化。进化编程系统的表示自然地面向任务级。一旦选定一种适应性表示，就可以定义依赖于该表示的变异操作，在具体的父辈行为上创建后代。,5.3 进化编程,24,随机产生的计算机程序种群开始，这些程序适合于问题空间领域的函数组成 适应度来评价各个函数 智能行为：预测周围的环境，并且将预测转化为实现预计目标的适当的反应。该环境可以取自有限字符数字集合符号序列，从而可以采用状态变化来反应环境，从而可以采用有限状态机来表达,25,5.3.2 进化编程的

12、步骤,进化编程分为三个步骤： 产生出初始群体。 迭代完成下述子步骤，直至满足选种标准为止： 执行群体中的每个程序。 应用变异等操作创造新程序群体。 在后代中适应值最高的计算机程序个体被指定为进化编程的结果。,5.3 进化编程,26,图5.6 进化编程的基本过程,5.3 进化编程,27,遗传算法、进化策略和进化编程比较,遗传算法和进化编程把变异作为主要搜索算子，而遗传算法，它是次要的 交叉在遗传算法中非常重要，但是进化编程省略，在进化策略中与自适应结合使用 遗传算法与进化编程都强调随机选择机制，进化策略的选择是确定的 进化策略和进化编程确定的把某些个体排除在被选择之外，而遗传算法一般都是对每个个

13、体指定一个非零的选择概率,28,5.4 人工生命,自然界是生命之源。自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无穷。 人工生命（Artificial Life，AL）试图通过人工方法建造具有自然生命特征的人造系统。 人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。,29,5.4.1 人工生命研究的起源和发展,人类长期以来一直力图用科学技术方法模拟自然界，包括人脑本身。1943年麦卡络奇和皮茨提出了MP神经学网络模型。 人工生命的许多早期研究工作也源于人工智能。 20世纪70年代以来，康拉德（Conrad）等提出不断完善的“人工世界”模型。

14、 80年代 90年代,5.4 人工生命,30,5.4.2 人工生命的定义和研究意义,人工生命是一项抽象地提取控制生物现象的基本动态原理，并且通过物理媒介（如计算机）来模拟生命系统动态发展过程的研究工作。 通俗地讲，人工生命即人造的生命，非自然的生命。然而，要对人工生命做出严格的定义，却需要对问题进行深入研究。,5.4 人工生命,31,人工生命系统,1987年兰德提出的人工生命定义为：“人工生命是研究能够演示出自然生命系统特征行为的人造系统”。 通过计算机或其它机器对类似生命的行为进行综合研究，以便对传统生物科学起互补作用。 兰德在计算机上演示了他们研制的具有生命特征的软件系统，并把这类具有生命

15、现象和特征的人造系统称为人工生命系统。,5.4 人工生命,32,自然生命的共同特征和现象,自繁殖、自进化、自寻优 自成长、自学习、自组织 自稳定、自适应、自协调 物质构造 能量转换 信息处理,5.4 人工生命,33,研究人工生命的意义,人工生命是自然生命的模拟、延伸与扩展，其研究开发有重大的科学意义和广泛的应用价值。 开发基于人工生命的工程技术新方法、新系统、新产品 为自然生命的研究提供新模型、新工具、新环境 延伸人类寿命、减缓衰老、防治疾病 扩展自然生命，人工进化、优生优育 促进生命、信息、系统科学的交叉与发展,5.4 人工生命,34,5.4.3 人工生命的研究内容和方法 1. 人工生命的研

16、究内容,人工生命的研究内容大致可分为两类：(1) 构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、酶系统、代谢系统等。(2) 在生物体及其群体的外部系统，包括环境适应系统和遗传进化系统等。,5.4 人工生命,35,人工生命的科学框架,生命现象仿生系统 生命现象的建模与仿真 进化动力学 人工生命的计算理论和工具 进化机器人 进化和学习等的结合 人工生命的应用,5.4 人工生命,36,2. 人工生命的研究方法,（1）信息模型法根据内部和外部系统所表现的生命行为来建造信息模型。 （2）工作原理法生命行为所显示的自律分数和非线性行为，其工作原理是混沌和分形，以此为基础研究人工生

17、命的机理。,5.4 人工生命,37,人工生命的研究技术途径 (1) 工程技术途径,利用计算机、自动化、微电子、精密机械、光电通信、人工智能、神经网络等有关工程技术方法和途径，研究开发、设计制造人工生命。通过计算机屏幕，以三维动画，虚拟现实的软件方法或采用光机电一体化的硬件装置来演示和体现人工生命。,5.4 人工生命,38,(2) 生物科学途径,利用生物科学方法和技术，通过人工合成、基因控制，无性繁殖过程，培育生成人工生命。 由于伦理学、社会学、人类学等方面的问题，通过生物科学途径生成的人工生命，如克隆人引起了不少争论。需要研究和制订相应的社会监督、国家法律和国际公约。,5.4 人工生命,39,5.4.4 人工生命的实例,人工脑 波兰人工智能和心理学教授安奇布勒（Andrzej Buller）及一些日本学者在日本现代通讯研究所进化系统研究室对人工脑的研究，已取得重要进展。 计算机病毒 计算机进程 细胞自动机 人工核苷酸,5.4 人工生命,40,5.5 小结,进化计算 遗传算法 进化策略 进化编程 人工生命 计算智能研究的最新领域之一 重要科学意义和社会效益 研究内容、发展前景和应用领域,