人工智能与专家系统XXXX2

第九章人工生命与智能计算9.1人工作生命概述9.2遗传算法9.3粒子群优化算法9.4元胞自动机9.5蚁群算法1人工生命人工生命是指用计算机和精密机械等生成或构造表现自然生命系统行为特点的仿真系统或模型系统。自然生命系统的行为特点表现为自组织、自修复、自复制的基本性质，以及形成这些性质的混沌动力学、环境适应和进化。在现实世界中，普遍地存在着各类复杂系统，一般认为，非线性、不稳定性、不确定性是造成复杂性的根源。复杂事物只能照它复杂的面貌来理解。2第九章人工生命定义1:研究具有自然生命系统行为的人造系统。定义2:人工生命是研究怎样通过抽取生物现象中的基本动力规则来理解生命，并且在物理媒体如计算机上重建这些现象，使它们成为新的实验方式和受操纵。定义3:在人工生命中的所有存在或将会存在的事物中，我们至少可以说这一领域从总体来说，代表了一种尝试，就是加重了生物学中合成理论的分量。3第一次会议

“人工生命——关于生命系统合成与模拟的跨学科研讨会”。本次会议于1987年9月在美国新墨西哥的罗斯阿拉莫斯举行。本次会议的论文集共收录了24篇论文，内容主要分布在：人工生命研究的理论、生命现象的仿真、细胞自动机（简称CA）、遗传算法、进化仿真等5个方面，兰顿发表了题为“人工生命”的开拓性论文，他在文中提出了人工生命的概念，并讨论了它作为一门新兴的研究领域或学科存在的意义。兰顿被公认为人工生命研究的创立者。这次会议标志着人工生命研究领域的诞生。4研究人工生命的原因人工生命的研究可使我们更好地理解突发特征，个体在低级组织中的集合，通过我们的相互作用，常可产生特征。人工生命将会成为研究生物的一个特别有用的工具。对于发展新技术及增强我们控制自然的能力，人工生命系统是很有潜力的。人工生命的另一显著应用是遗传工程。5人工生命的探索20世纪初，逻辑在算术机械运算中的运用，导致过程的抽象形式化。40年代末，50年代初，冯.诺伊曼提出了机器自增长的可能性理论。以计算机为工具，迎来了信息科学的发展。70年代以来，科拉德(Conrad)和他的同事研究人工仿生系统中的自适应、进化和群体动力学，提出了不断完善的“人工世界”模型。80年代，人工神经网络又兴起，出现了许多神经网络模型和学习算法。与此同时，人工生命的研究也逐渐兴起。1987年召开了第一届国际人工生命会议。6人工生命的模型1)计算机病毒2)计算机的进程3)生物统计学和个体胎生学4)机器人5)自催化(autocatalytic)网络6)细胞自动机7)人工核苷酸7人工生命的研究方法和战略按照人工生命的组织机构，人工生命的内容大致可以分成两类：构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、酶系统、代谢系统等。在生物体及其群体中表现的外部系统。生物群体中环境适应系统和遗传进化系统等。8模型法。根据内部和外部系统所表现的生命行为，建造信息模型。工作原理法。生命行为所显示的自律分散和非线性的行为，它的工作原理是混沌和分形，据此研究它的机理。人工生命研究的方法9采用以计算机等信息处理机器为中心的硬件生成生命行为。一种是采用已有的信息处理机器和执行装置，实现具有人工生命行为的系统。另一种是用生物器件构造生命系统。这些都通称为生物计算机，是一种向人工生命接近的方法。用计算机仿真，研究开发显示生命体特征行为的模型软件。简单地说，神经网络系统和遗传算法等，都是采用信息数学模型，模拟人工生命的生成。基于工作原理，利用计算机仿真生成生命体。生命现象的基础是随物理熵的增大而杂乱无章。生成这种现象的原理是混沌的分形、耗散结构、协同反应等，采用这些产生生命现象。通过计算机仿真，分析生命特有的行为生成，建立新的理论。利用上面3个策略，得到生命行为共同的一般性质，通过概括，建立生命的基本理论。这种策略形成自组织、超并行处理等理论。人工生命研究的策略109.2遗遗传算法及及应用遗传算法的的提出及发发展遗传算法的的基本原理理遗传算法的的构成要素素遗传算法的的实现步骤骤遗传算法的的应用111遗传算算法的提出出及发展遗传算法(GeneticAlgorithm，GA)是一一种基于进进化论优胜胜劣汰、适适者生存的的物种遗传传机制的随随机化搜索索算法。它它是生物学学和计算机机科学结合合的产物。。它最早由美美国密执根根大学J.Holland教教授提出出，其主要要特点是群群体搜索策策略和群体体中个体之之间的信息息交换，搜搜索不依赖赖于梯度信信息。在人工智能能研究中，，认为“遗遗传算法、、自适应系系统、细胞胞自动机、、混沌理论论与人工智智能一样，，都是对今今后十年的的计算技术术有重大影影响的关键键技术”12遗传算法的的发展20世纪60年代，，美国密植植安大学的的Holland教教授及其学学生们受到到生物模拟拟技术的启启发，创造造出了一种种基于生物物遗传和进进化机制的的适合于复复杂系统计计算优化的的自适应概概率优化技技术-----遗传传算法。下下面是在遗遗传算法的的发展进程程中一些关关键人物所所做出的一一些主要贡贡献。1320世纪60年代，，Holland认认识到了生生物的遗传传和自然进进化现象与与人工自适适应系统的的相似关系系，运用生生物遗传和和进化的思思想来研究究自然和人人工自适应应系统的生生成以及它它们与环境境的关系，，提出在研研究和设计计人工自适适应系统时时，可以借借鉴生物遗遗传的机制制，以群体体的方法进进行自适应应搜索，并并且充分认认识到了交交叉、变异异等运算策策略在自适适应系统中中的重要性性。遗传算法的的发展141967年年，Holland的学生Bagley在其博博士论文中中首次提出出了“遗传传算法”一一词，并发发表了遗传传算法应用用方面的第第一篇论文文。他发展展了复制、、交叉、变变异、显性性、倒位等等遗传算子子，在个体体编码上使使用了双倍倍体的编码码方法。这这些都与目目前遗传算算法中所使使用的算子子和方法类类似。他还还敏锐地意意识到了在在遗传算法法执行的不不同阶段可可以使用不不同的选择择率，这将将有利于防防止遗传算算法的早熟熟现象，从从而创立了了自适应遗遗传算法的的概念。遗传算法的的发展1520世纪70年代，，Holland提提出了遗传传算法的基基本定理---模式式定理(SchemaTheorem),奠奠定了遗传传算法的理理论基础。。1975年，Holland出版了了第一本系系统论述遗遗传算法和和人工自适适应系统的的专著《自自然系统和和人工系统统的自适应应性（AdaptationinNaturalandArtificialSystems）》》。遗传算法的的发展1620世纪80年代，，Holland实实现了第一一个基于遗遗传算法的的机器学习习系统----分类类器系统，，开创了基基于遗传算算法学习的的新概念，，为分类器器系统构造造出了一个个完整的框框架。遗传算法的的发展171989年年，Goldberg出版了了专著《搜搜索、优化化和机器学学习中的遗遗传算法》》。该书系系统总结了了遗传算法法的主要研研究成果，，全面而完完整地论述述了遗传算算法的基本本原理及其其应用。遗传算法的的发展181992年年，Koza将遗传传算法应用用于计算机机程序的优优化设计及及自动生成成，，提出出了遗传编编程的概念念。Koza成功地地将提出的的遗传编程程方法应用用于人工智智能、机器器学习、符符号处理等等方面。遗传算法的的发展192遗传算算法的基本本原理遗传算法的的基本思想想是基于Darwin进化论论和Mendel的的遗传学说说。Darwin进进化论最重重要的是适适者生存原原理。它认认为每一物物种在发展展中越来越越适应环境境。物种每每个个体的的基本特征征由后代所所继承，但但后代又会会产生一些些异于父代代的新变化化。在环境境变化时，，只有那些些能适应环环境的个体体特征方能能保留下来来。Mendel遗传学学说最重要要的是基因因遗传原理理。认为遗遗传以密码码方式存在在细胞中，，并以基因因形式包含含在染色体体内。每个个基因有特特殊的位置置并控制某某种特殊性性质；所以以，每个基基因产生的的个体对环环境具有某某种适应性性。基因突突变和基因因杂交可产产生更适应应于环境的的后代。经经过存优去去劣的自然然淘汰，适适应性高的的基因结构构得以保存存下来。20遗传算法与与传统优化化算法的主主要不同遗传算法不不是直接作作用在参变变量集上,而是利利用参变量量集的某种种编码;遗传算法不不是从单个个点,而而是在群体体中从一个个点开始搜搜索;遗传算法利利用适应值值信息,无无需导数数或其它辅辅助信息;遗传算法利利用概率转转移规则,而非确确定性规则则。21遗传算法的的缺点编码不规范范及编码存存在表示的的不准确性性。单一的遗传传算法编码码不能全面面地将优化化问题的约约束表示出出来。易于陷入局局部最优点点，导致早早熟。223遗传算算法的构成成要素3.1染色色体编码方方法。基本遗传算算法使用固固定长度的的二进制符符号串表示示群体的个个体，其等等位基因是是由二值符符号{0，，1}所组组成的。初初始群体中中各个个体体的基因值值可用均匀匀分布的随随机数生成成，如：x=1001110010就就可以表表示一个个个体，该个个体的染色色体长度是是n=10。3.2个个体适应度度评价基本遗传算算法按与个个体适用度度成正比的的概率来决决定当前群群体中每个个个体遗传传到下一代代群体中的的机会多少少。为正确确计算这个个概率，这这里要求所所有个体的的适应度必必须为正数数或零。根根据不同种种类的问题题，必须预预先确定好好由目标函函数值到个个体适应度度的转换规规则。233遗传算算法的构成成要素3.3遗遗传算子子•选择算子(selection)：：又称为复复制算子。。按照某种种策略从父父代中挑选选个体进入入下一代，，如使用比比例选择、、轮盘式选选择。•交叉算子(crossover)：又又称为杂交交算子。将将从群体中中选择的两两个个体，，按照某种种策略使两两个个体相相互交换部部分染色体体，从而形形成两个新新的个体。。如使用单单点一致交交叉。•变异算子(mutation)：按照照一定的概概率（一般般较小），，改变染色色体中某些些基因的值值。243遗传算算法的构成成要素3.4、运运行参数N：群体大大小，即群群体中包含含的个体的的数量。T：遗传算算法终止的的进化代数数。Pc：交叉概率率，一般取取为0.4～0.99。Pm：变异概率率，一般取取为0.0001～0.1。25遗传算法与与传统优化化算法的主主要不同遗传算法不不是直接作作用在参变变量集上,而是利利用参变量量集的某种种编码;遗传算法不不是从单个个点,而而是在群体体中从一个个点开始搜搜索;遗传算法利利用适应值值信息,无无需导数数或其它辅辅助信息;遗传算法利利用概率转转移规则,而非确确定性规则则。264遗传算法的的应用步骤骤遗传算法提提供了一种种求解复杂杂系统优化化问题的通通用框架，，它不依赖赖于问题的的领域和种种类。对一一个需要进进行优化和和计算的实实际应用问问题，一般般可按下述述步骤来求求解问题的的遗传算法遗传算法的准备工作：1）确定表示方案;2）确定适应值的度量;3）确定控制该算法的参数和变量;4）确定怎样指定结果及程序运行结束的标准。274遗传算算法的应用用步骤遗传算法提提供了一种种求解复杂杂系统优化化问题的通通用框架。。对于具体体问题，可可按下述步步骤来构造造：①确定决策策变量及其其各种约束束条件，即即确定出个个体的表现现型X和问题的解解空间；②建立优化化模型，即即描述出目目标函数的的类型及其其数学描述述形式或量量化方法；；284遗传算算法的应用用步骤③确定表示示可行解的的染色体编编码方法，，即确定出出个体的基基因型X及遗传算法法的搜索空空间；④确定解码码方法，即即确定出由由个体基因因型X到个体表现现型X的对应关系系或转换方方法；⑤确定个体体适应度的的量化评价价方法，即即确定出由由目标函数数值到到个体适适应度的转转换规则；；294遗传算算法的应用用步骤⑥设计遗传传算子，即即确定出选选择运算、、交叉运算算、变异运运算等遗传传算子的具具体操作方方法；⑦确定遗传传算法的有有关运行参参数，即确确定出遗传传算法的等等参参数。30基本遗传算算法流程图图引入新个体变异随机创建初始群体自然选择复制、杂交显示结果结束是否是否满足选中标准？计算群体中每个个体的适应值31遗传算法举例例问题：求（1）编码：：此时取均长为为5，每个染染色体（2）初始群群体生成：群群体大小视情情况而定，此此处设置为4，随机产生生四个个体：：编码：01101，11000，，01000，10011解码：1324819（3）适应度度评价：32（4）选择：：选择概率个体：01101，11000，，01000，10011选择结果：01101，，11000，11000，10011（5）交叉操操作：发生交交叉的概率较较大哪两个个体配配对交叉是随随机的交叉点位置的的选取是随机机的（单点交交叉）33（6）变异：：发生变异的的概率很小（7）新群体体的产生：保留上一代最最优个体，一一般为10%左右，至少少1个用新个体取代代旧个体，随随机取代或择择优取代。11000，，11011，11001，10011（8）重复上上述操作：说明：GA的的终止条件一一般人为设置置；GA只能求次次优解或满意意解。分析：按第二二代新群体进进行遗传操作作，若无变异异，永远也找找不到最优解解——择优取取代有问题。。若随机的将个个体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被选中两次，，因而被复制制两次；而适适应度最低的的染色体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假设这一轮选选择-复制操作中，，种群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=0100139第三代种群S4中各染色体的的情况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”作为最最终结结果输输出。。然后，，将染染色体体“11111”解码码为表表现型型，即即得所所求的的最优优解：：31。将31代入函函数y=x2中，即即得原原问题题的解解，即即函数数y=x2的最大大值为为961。425遗遗传算算法的的应用用应用领域具体说明控制煤气管道控制，防避导弹控制，机器人控制规划生产规划，并行任务分配设计VLSI布局，背包问题，图划分问题图像处理模式识别，特征抽取信号处理滤波器设计机器人路径规划人工生命生命的遗传进化人工神经网络权值训练和网络结构生成43遗传算算法的的应用用遗传算算法提提供了了一种种求解解复杂杂系统统优化化问题题的通通用框框架，，它不不依赖赖于问问题的的具体体领域域，对对问题题的种种类有有很强强的鲁鲁棒性性，所所以广广泛应应用于于很多多学科科。下下面列列举一一些遗遗传算算法的的主要要应用用领域域。44函数优优化是是遗传传算法法的经经典应应用领领域，，也是是对遗遗传算算法进进行性性能测测试评评价的的常用用算例例。对对于一一些非非线性性、多多模型型、多多目标标的函函数优优化问问题，，用其其他优优化方方法较较难求求解，，而遗遗传算算法却却可以以方便便地得得到较较好的的结果果。函数优优化45组合优优化遗传算算法是是寻求求组合合优化化问题题满意意解的的最佳佳工具具之一一，实实践证证明，，遗传传算法法对于于组合合优化化问题题中的的NP完全全问题题非常常有效效。46生产调调度问问题生产调调度问问题在在很多多情况况下所所建立立起来来的数数学模模型难难以精精确求求解，，即使使经过过一些些简化化之后后可以以进行行求解解也会会因简简化得得太多多而使使求解解结果果与实实际相相差太太远。。现在在遗传传算法法已经经成为为解决决复杂杂调度度问题题的有有效工工具。。47自动控控制遗传算算法已已经在在自动动控制制领域域中得得到了了很好好的应应用，，例如如基于于遗传传算法法的模模糊控控制器器的优优化设设计、、基于于遗传传算法法的参参数辨辨识、、基于于遗传传算法法的模模糊控控制规规则的的学习习、利利用遗遗传算算法进进行人人工神神经网网络的的结构构优化化设计计和权权值学学习等等。48机器人人学机器人人是一一类复复杂的的难以以精确确建模模的人人工系系统，，而遗遗传算算法的的起源源就来来自于于对人人工自自适应应系统统的研研究，，所以以机器器人学学自然然成为为遗传传算法法的一一个重重要应应用领领域。。49图象处处理图像处处理是是计算算机视视觉中中的一一个重重要研研究领领域。。在图图像处处理过过程中中，如如扫描描、特特征提提取、、图像像分割割等不不可避避免地地存在在一些些误差差，这这些误误差会会影响响图像像处理理的效效果。。如何何使这这些误误差最最小是是使计计算机机视觉觉达到到实用用化的的重要要要求求，遗遗传算算法在在这些些图像像处理理中的的优化化计算算方面面得到到了很很好的的应用用。50人工生生命人工生生命是是用计计算机机、机机械等等人工工媒体体模拟拟或构构造出出的具具有自自然生生物系系统特特有行行为的的人造造系统统。自自组织织能力力和自自学习习能力力是人人工生生命的的两大大重要要特征征。人人工生生命与与遗传传算法法有着着密切切的关关系，，基于于遗传传算法法的进进化模模型是是研究究人工工生命命现象象的重重要理理论基基础。。519.3粒粒子群群优化化算法法粒子群群优化化(ParticleSwarmOptimization,PSO)，又又称微微粒群群算法法，是是由J.Kennedy和和RCEberhart等等于1995年年开发发的一一种演演化机机制。。粒粒子(particle)””是一一个折折衷的的选择择,因因为既既需要要将将群体体中的的成员员描述述为没没有质质量、、没有有体积积的,同时时也需需要描描述它它的速速度和和加速速状态态。PSO模拟拟鸟群群的捕捕食行行为。。设想想这样样一个个场景景：一一群鸟鸟在随随机搜搜索食食物。。在这这个区区域里里只有有一块块食物物。所所有的的鸟都都不知知道食食物在在那里里。但但是他他们知知道当当前的的位置置离食食物还还有多多远。。那么么找到到食物物的最最优策策略是是什么么呢。。最简简单有有效的的就是是搜寻寻目前前离食食物最最近的的鸟的的周围围区域域。PSO从从这种模模型中得得到启示示并用于于解决优优化问题题。PSO中，，每个优优化问题题的解都都是搜索索空间中中的一只只鸟。我我们称之之为“粒粒子”。。所有的的例子都都有一个个由被优优化的函函数决定定的适应应值(fitnessvalue)，每每个粒子子还有一一个速度度决定他他们飞翔翔的方向向和距离离。然后后粒子们们就追随随当前的的最优粒粒子在解解空间中中搜索。。52特点分布式搜搜寻具记忆性性组件较少少，容易易实现适合在连续性的范围内内搜寻53演算法介绍每个寻优优的问题题解都被被想象成成一只鸟鸟，我们们也称为为“Particle”。所有的Particle都都有一个