13 人工智能与专家系统(XXXX)

1第九章人工生命与智能计算9.1人工作生命概述9.2遗传算法9.3粒子群优化算法9.4元胞自动机9.5蚁群算法2人工生命人工生命是指用计算机和精密机械等生成或构造表现自然生命系统行为特点的仿真系统或模型系统。自然生命系统的行为特点表现为自组织、自修复、自复制的基本性质，以及形成这些性质的混沌动力学、环境适应和进化。在现实世界中，普遍地存在着各类复杂系统，一般认为，非线性、不稳定性、不确定性是造成复杂性的根源。复杂事物只能照它复杂的面貌来理解。3第九章人工生命定义1:研究具有自然生命系统行为的人造系统。定义2:人工生命是研究怎样通过抽取生物现象中的基本动力规则来理解生命，并且在物理媒体如计算机上重建这些现象，使它们成为新的实验方式和受操纵。定义3:在人工生命中的所有存在或将会存在的事物中，我们至少可以说这一领域从总体来说，代表了一种尝试，就是加重了生物学中合成理论的分量。4第一次会议“人工生命——关于生命系统合成与模拟的跨学科研讨会”。本次会议于1987年9月在美国新墨西哥的罗斯阿拉莫斯举行。本次会议的论文集共收录了24篇论文，内容主要分布在：人工生命研究的理论、生命现象的仿真、细胞自动机（简称CA）、遗传算法、进化仿真等5个方面，兰顿发表了题为“人工生命”的开拓性论文，他在文中提出了人工生命的概念，并讨论了它作为一门新兴的研究领域或学科存在的意义。兰顿被公认为人工生命研究的创立者。这次会议标志着人工生命研究领域的诞生。5研究人工生命的原因人工生命的研究可使我们更好地理解突发特征，个体在低级组织中的集合，通过我们的相互作用，常可产生特征。人工生命将会成为研究生物的一个特别有用的工具。对于发展新技术及增强我们控制自然的能力，人工生命系统是很有潜力的。人工生命的另一显著应用是遗传工程。6人工生命的探索20世纪初，逻辑在算术机械运算中的运用，导致过程的抽象形式化。40年代末，50年代初，冯.诺伊曼提出了机器自增长的可能性理论。以计算机为工具，迎来了信息科学的发展。70年代以来，科拉德(Conrad)和他的同事研究人工仿生系统中的自适应、进化和群体动力学，提出了不断完善的“人工世界”模型。80年代，人工神经网络又兴起，出现了许多神经网络模型和学习算法。与此同时，人工生命的研究也逐渐兴起。1987年召开了第一届国际人工生命会议。7人工生命的模型1)计算机病毒2)计算机的进程3)生物统计学和个体胎生学4)机器人5)自催化(autocatalytic)网络6)细胞自动机7)人工核苷酸8人工生命的研究方法和战略按照人工生命的组织机构，人工生命的内容大致可以分成两类：1)构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、酶系统、代谢系统等。2)在生物体及其群体中表现的外部系统。生物群体中环境适应系统和遗传进化系统等。91)模型法。•根据内部和外部系统所表现的生命行为，建造信息模型。2)工作原理法。•生命行为所显示的自律分散和非线性的行为，它的工作原理是混沌和分形，据此研究它的机理。人工生命研究的方法101)采用以计算机等信息处理机器为中心的硬件生成生命行为。•一种是采用已有的信息处理机器和执行装置，实现具有人工生命行为的系统。•另一种是用生物器件构造生命系统。这些都通称为生物计算机，是一种向人工生命接近的方法。2)用计算机仿真，研究开发显示生命体特征行为的模型软件。简单地说，神经网络系统和遗传算法等，都是采用信息数学模型，模拟人工生命的生成。3)基于工作原理，利用计算机仿真生成生命体。生命现象的基础是随物理熵的增大而杂乱无章。生成这种现象的原理是混沌的分形、耗散结构、协同反应等，采用这些产生生命现象。4)通过计算机仿真，分析生命特有的行为生成，建立新的理论。利用上面3个策略，得到生命行为共同的一般性质，通过概括，建立生命的基本理论。这种策略形成自组织、超并行处理等理论。人工生命研究的策略119.2遗传算法及应用遗传算法的提出及发展遗传算法的基本原理遗传算法的构成要素遗传算法的实现步骤遗传算法的应用121遗传算法的提出及发展遗传算法(GeneticAlgorithm，GA)是一种基于进化论优胜劣汰、适者生存的物种遗传机制的随机化搜索算法。它是生物学和计算机科学结合的产物。它最早由美国密执根大学J.Holland教授提出，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。在人工智能研究中，认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样，都是对今后十年的计算技术有重大影响的关键技术”13遗传算法的发展20世纪60年代，美国密植安大学的Holland教授及其学生们受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统计算优化的自适应概率优化技术-----遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。14J.H.Holland20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。遗传算法的发展15J.D.Bagley1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。遗传算法的发展1620世纪70年代，Holland提出了遗传算法的基本定理---模式定理(SchemaTheorem),奠定了遗传算法的理论基础。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性（AdaptationinNaturalandArtificialSystems）》。遗传算法的发展1720世纪80年代，Holland实现了第一个基于遗传算法的机器学习系统----分类器系统，开创了基于遗传算法学习的新概念，为分类器系统构造出了一个完整的框架。遗传算法的发展18D.J.Goldberg1989年，Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。遗传算法的发展19J.R.Koza1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，，提出了遗传编程的概念。Koza成功地将提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。遗传算法的发展202遗传算法的基本原理遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。21遗传算法与传统优化算法的主要不同1)遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;2)遗传算法不是从单个点,而是在群体中从一个点开始搜索;3)遗传算法利用适应值信息,无需导数或其它辅助信息;4)遗传算法利用概率转移规则,而非确定性规则。22遗传算法的缺点编码不规范及编码存在表示的不准确性。单一的遗传算法编码不能全面地将优化问题的约束表示出来。易于陷入局部最优点，导致早熟。233遗传算法的构成要素3.1染色体编码方法。基本遗传算法使用固定长度的二进制符号串表示群体的个体，其等位基因是由二值符号{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数生成，如：x=1001110010就可以表示一个个体，该个体的染色体长度是n=10。3.2个体适应度评价基本遗传算法按与个体适用度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。根据不同种类的问题，必须预先确定好由目标函数值到个体适应度的转换规则。243遗传算法的构成要素3.3遗传算子•选择算子(selection)：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。•交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。•变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。253遗传算法的构成要素3.4、运行参数N：群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为0.4～0.99。Pm：变异概率，一般取为0.0001～0.1。26遗传算法与传统优化算法的主要不同1)遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;2)遗传算法不是从单个点,而是在群体中从一个点开始搜索;3)遗传算法利用适应值信息,无需导数或其它辅助信息;4)遗传算法利用概率转移规则,而非确定性规则。274遗传算法的应用步骤遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对一个需要进行优化和计算的实际应用问题，一般可按下述步骤来求解问题的遗传算法。遗传算法的准备工作：1）确定表示方案;2）确定适应值的度量;3）确定控制该算法的参数和变量;4）确定怎样指定结果及程序运行结束的标准。284遗传算法的应用步骤遗传算法提供了一种求解复杂系统优化问题的通用框架。对于具体问题，可按下述步骤来构造：①确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间；②建立优化模型，即描述出目标函数的类型及其数学描述形式或量化方法；294遗传算法的应用步骤③确定表示可行解的染色体编码方法，即确定出个体的基因型X及遗传算法的搜索空间；④确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法；⑤确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；)(Xf304遗传算法的应用步骤⑥设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法；⑦确定遗传算法的有关运行参数，即确定出遗传算法的等参数。mcppTM、、、31基本遗传算法流程图引入新个体变异随机创建初始群体自然选择复制、杂交显示结果结束是否是否满足选中标准？计算群体中每个个体的适应值32遗传算法举例问题：求（1）编码：此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体：编码：01101，11000，01000，10011解码：1324819适应度：16957664361（3）适应度评价：]31,0[,)(2xxxfMax11111~00000x5}1,0{2)(xxfitness33（4）选择：选择概率个体：01101，11000，01000，10011适应度：16957664361选择概率：0.140.490.060.31选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的（单点交叉）011010110011000110111100011001