1、第九章 人工生命与智能计算,9.1 人工作生命概述9.2 遗传算法9.3 粒子群优化算法9.4元胞自动机9.5 蚁群算法,1,人工生命,人工生命是指用计算机和精密机械等生成或构造表现自然生命系统行为特点的仿真系统或模型系统。自然生命系统的行为特点表现为自组织、自修复、自复制的基本性质，以及形成这些性质的混沌动力学、环境适应和进化。在现实世界中，普遍地存在着各类复杂系统，一般认为，非线性、不稳定性、不确定性是造成复杂性的根源。复杂事物只能照它复杂的面貌来理解。,2,第九章 人工生命,定义1:研究具有自然生命系统行为的人造系统。定义2:人工生命是研究怎样通过抽取生物现象中的基本动力规则来理解生命，
2、并且在物理媒体如计算机上重建这些现象，使它们成为新的实验方式和受操纵。定义3:在人工生命中的所有存在或将会存在的事物中，我们至少可以说这一领域从总体来说，代表了一种尝试，就是加重了生物学中合成理论的分量。,3,第一次会议,“人工生命关于生命系统合成与模拟的跨学科研讨会”。本次会议于1987年9月在美国新墨西哥的罗斯阿拉莫斯举行。本次会议的论文集共收录了24篇论文，内容主要分布在：人工生命研究的理论、生命现象的仿真、细胞自动机（简称CA）、遗传算法、进化仿真等5个方面，兰顿发表了题为“人工生命”的开拓性论文，他在文中提出了人工生命的概念，并讨论了它作为一门新兴的研究领域或学科存在的意义。兰顿被公
3、认为人工生命研究的创立者。这次会议标志着人工生命研究领域的诞生。,4,研究人工生命的原因,人工生命的研究可使我们更好地理解突发特征，个体在低级组织中的集合，通过我们的相互作用，常可产生特征。人工生命将会成为研究生物的一个特别有用的工具。对于发展新技术及增强我们控制自然的能力，人工生命系统是很有潜力的。人工生命的另一显著应用是遗传工程。,5,人工生命的探索,20世纪初，逻辑在算术机械运算中的运用，导致过程的抽象形式化。40年代末，50年代初，冯.诺伊曼提出了机器自增长的可能性理论。以计算机为工具，迎来了信息科学的发展。70年代以来，科拉德(Conrad)和他的同事研究人工仿生系统中的自适应、进化
4、和群体动力学，提出了不断完善的“人工世界”模型。80年代，人工神经网络又兴起，出现了许多神经网络模型和学习算法。与此同时，人工生命的研究也逐渐兴起。1987年召开了第一届国际人工生命会议。,6,人工生命的模型,1)计算机病毒2)计算机的进程3)生物统计学和个体胎生学4)机器人5)自催化(autocatalytic)网络6)细胞自动机7)人工核苷酸,7,人工生命的研究方法和战略,按照人工生命的组织机构，人工生命的内容大致可以分成两类：构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、酶系统、代谢系统等。在生物体及其群体中表现的外部系统。生物群体中环境适应系统和遗传进化系统等
5、。,8,模型法。根据内部和外部系统所表现的生命行为，建造信息模型。工作原理法。生命行为所显示的自律分散和非线性的行为，它的工作原理是混沌和分形，据此研究它的机理。,人工生命研究的方法,9,采用以计算机等信息处理机器为中心的硬件生成生命行为。一种是采用已有的信息处理机器和执行装置，实现具有人工生命行为的系统。另一种是用生物器件构造生命系统。这些都通称为生物计算机，是一种向人工生命接近的方法。用计算机仿真，研究开发显示生命体特征行为的模型软件。简单地说，神经网络系统和遗传算法等，都是采用信息数学模型，模拟人工生命的生成。基于工作原理，利用计算机仿真生成生命体。生命现象的基础是随物理熵的增大而杂乱无
6、章。生成这种现象的原理是混沌的分形、耗散结构、协同反应等，采用这些产生生命现象。通过计算机仿真，分析生命特有的行为生成，建立新的理论。利用上面3个策略，得到生命行为共同的一般性质，通过概括，建立生命的基本理论。这种策略形成自组织、超并行处理等理论。,人工生命研究的策略,10,9.2 遗传算法及应用,遗传算法的提出及发展遗传算法的基本原理遗传算法的构成要素遗传算法的实现步骤 遗传算法的应用,11,1 遗传算法的提出及发展,遗传算法(GeneticAlgorithm，GA)是一种基于进化论优胜劣汰、适者生存的物种遗传机制的随机化搜索算法。它是生物学和计算机科学结合的产物。它最早由美国密执根大学J.
7、Holland 教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。在人工智能研究中，认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”,12,遗传算法的发展,20世纪60年代，美国密植安大学的Holland教授及其学生们受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统计算优化的自适应概率优化技术-遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。,13,J.H.Holland 20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系
8、统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。,遗传算法的发展,14,J.D.Bagley 1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率
9、，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。,遗传算法的发展,15,20世纪70年代，Holland提出了遗传算法的基本定理-模式定理(Schema Theorem),奠定了遗传算法的理论基础。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性（Adaptation in Natural and Artificial Systems）。,遗传算法的发展,16,20世纪80年代，Holland实现了第一个基于遗传算法的机器学习系统-分类器系统，开创了基于遗传算法学习的新概念，为分类器系统构造出了一个完整的框架。,遗传算
10、法的发展,17,D.J.Goldberg 1989年，Goldberg出版了专著搜索、优化和机器学习中的遗传算法。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。,遗传算法的发展,18,J.R.Koza 1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念。Koza成功地将提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。,遗传算法的发展,19,2 遗传算法的基本原理,遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境
11、。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。,20,遗传算法与传统优化算法的主要不同,遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点开始搜索;遗传算法利用适应值信息,无
12、需导数或其它辅助信息;遗传算法利用概率转移规则,而非确定性规则。,21,遗传算法的缺点,编码不规范及编码存在表示的不准确性。单一的遗传算法编码不能全面地将优化问题的约束表示出来。易于陷入局部最优点，导致早熟。,22,3 遗传算法的构成要素,3.1染色体编码方法。基本遗传算法使用固定长度的二进制符号串表示群体的个体，其等位基因是由二值符号0，1所组成的。初始群体中各个个体的基因值可用均匀分布的随机数生成，如：x=1001110010 就可以表示一个个体，该个体的染色体长度是n=10。3.2个体适应度评价 基本遗传算法按与个体适用度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。
13、为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。根据不同种类的问题，必须预先确定好由目标函数值到个体适应度的转换规则。,23,3 遗传算法的构成要素,3.3 遗传算子 选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。,24,3 遗传算法的构成要素,3.4、运行参数N：群体大小，
14、即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为 0.40.99。Pm：变异概率，一般取为 0.00010.1。,25,遗传算法与传统优化算法的主要不同,遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;遗传算法不是从单个点,而是在群体中从一个点开始搜索;遗传算法利用适应值信息,无需导数或其它辅助信息;遗传算法利用概率转移规则,而非确定性规则。,26,4 遗传算法的应用步骤,遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对一个需要进行优化和计算的实际应用问题，一般可按下述步骤来求解问题的遗传算法。遗传算法的准备工作：1）
15、确定表示方案;2）确定适应值的度量;3）确定控制该算法的参数和变量;4）确定怎样指定结果及程序运行结束的标准。,27,4 遗传算法的应用步骤,遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间；建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法；,28,4 遗传算法的应用步骤,确定表示可行解的染色体编码方法，即确定出个体的基因型X及遗传算法的搜索空间；确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法；确定个体适应度的量化评价方法，即确定出由目标函数值 到个体适应
16、度的转换规则；,29,4 遗传算法的应用步骤,设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法；确定遗传算法的有关运行参数，即确定出遗传算法的 等参数。,30,基本遗传算法流程图,31,遗传算法举例,问题：求（1）编码：此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011 解码：13 24 8 19 适应度：169 576 64 361（3）适应度评价：,32,（4）选择：选择概率 个体：01101，11000，01000，10011 适应度：169 576 64 361
17、 选择概率：0.14 0.49 0.06 0.31 选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大 哪两个个体配对交叉是随机的 交叉点位置的选取是随机的（单点交叉）0110 1 01100 11 000 11 011 1100 0 11001 10 011 10 000,33,（6）变异：发生变异的概率很小（7）新群体的产生：保留上一代最优个体，一般为10%左右，至少1个 用新个体取代旧个体，随机取代或择优取代。11000，11011，11001，10011（8）重复上述操作：说明：GA的终止条件一般人为设置；GA只能求次优解或满意解。分析：按第二代
18、新群体进行遗传操作，若无变异，永远也找不到最优解择优取代有问题。若随机的将个体01101选入新群体中，有可能找到最优解。,34,第一代种群S1中各染色体的情况,35,选择-复制 设从区间0,1中产生4个随机数如下:,r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503,按赌轮选择法，染色体s1,s2,s3,s4的被选中次数依次为：1,2,0,1。于是，经复制得群体：,s1=11000（24）,s2=01101（13）,s3=11000（24）,s4=10011（19）,可以看出，在第一轮选择中适应度最高的染色体s2被选中两次，因而被复制两次；而适应度最低
19、的染色体s3一次也没有选中而遭淘汰。,36,交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s2与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）变异 设变异率pm=0.001。这样，群体S1中共有540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。现在，我们得到了第二代种群S2：s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）,37,第二代种群S2中各染色体的情况,38,
20、假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中（因为选择概率毕竟只是一种几率，所以4个染色体恰好都被选中的情况是存在的），我们得到群体：,s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）,然后，做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得,s1=11100（28）,s2=01001（9）,s3=11000（24）,s4=10011（19）,这一轮仍然不会发生变异。于是，得第三代种群S3：,s1=11100（28）,s2=01001（9）,s3=11000（24）,s4=10011（19）,39,第三代种群S4中各
21、染色体的情况,40,设这一轮的选择-复制结果为：,s1=11100（28）,s2=11100（28）,s3=11000（24）,s4=10011（19）,然后，做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得,s1=11111（31）,s2=11100（28）,s3=11000（24）,s4=10000（16）,这一轮仍然不会发生变异。于是，得第四代种群S4：,s1=11111（31）,s2=11100（28）,s3=11000（24）,s4=10000（16）,41,显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最
22、终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。,42,5 遗传算法的应用,43,遗传算法的应用,遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法的主要应用领域。,44,函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。,函数优化,45,组合优化,遗传算法是寻求
23、组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的NP完全问题非常有效。,46,生产调度问题,生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,47,自动控制,遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。,48,机器人学,机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于
24、对人工自适应系统的研究，所以机器人学自然成为遗传算法的一个重要应用领域。,49,图象处理,图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，遗传算法在这些图像处理中的优化计算方面得到了很好的应用。,50,人工生命,人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。,51,9.3 粒
25、子群优化算法,粒子群优化(Particle Swarm Optimization,PSO)，又称微粒群算法，是由J.Kennedy和RC Eberhart等于1995年开发的一种演化机制。粒子(particle)”是一个折衷的选择,因为既需要 将群体中的成员描述为没有质量、没有体积的,同时也需要描述它的速度和加速状态。PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化
26、问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。,52,特点,分布式搜寻 具记忆性组件较少，容易实现 适合在连续性的范围内搜寻,53,演算法介绍,每个寻优的问题解都被想象成一只鸟，我们也称为“Particle”。所有的Particle 都有一个fitness function 以判断目前的位置之好坏，每一个Particle必须赋予记忆性，能记得所搜寻到最佳位置。每一个Particle 还有一个速度以决
27、定飞行的距离与方向。,54,算法流程,1.Initial 将群族做初始化，以随机的方式求出每一Particle 之初始位置与速度。2.Evaluation：依据fitness function 计算出其fitness value 以作为判断每一Particle之好坏。3.Fine the Pbest：找出每一Particle 到目前为止的搜寻过程中最佳解，这个最佳解我们将之称为Pbest。4.Fine the Gbest：找出所有Particle 到目前为止所搜寻到的整体最佳解，此最佳解我们称之为Gbest。5.Update the Velocity：依据式(1)与式(2)更新每一Partic
28、le之速度与位置。6.回到步骤2.继续执行，直到获得一个令人满意的结果或符合终止条件为止。,55,粒子群优化:Swarm Search,Actually,we must adjust the v-vector before adding it to the x-vector as follows:vid=vid+1*rnd()*(pid-xid)+2*rnd()*(pgd-xid);xid=xid+vid;Where i is the particle,1,2 are learning rates governing the cognition and social components Wh
29、ere g represents the index of the particle with the best p-fitness,and Where d is the dth dimension.,56,Schwefels function,57,搜寻过程最初状态,58,搜寻过程经过5代,59,搜寻过程经过10代,60,搜寻过程经过15代,61,搜寻过程经过20代,62,搜寻过程经过25代,63,搜寻过程经过100代,64,搜寻过程经过500代,65,粒子群优化算法应用,图像分割与解译交通控制与规划智能调度与任务分配目标函数优化神经网络训练模糊控制系统 工程设计与优化,66,Thanks.,67,
