人工智能课件七

第5章计算智能(2):进化计算人工生命5.1遗传算法5.2进化策略5.3进化编程5.4人工生命1/22/20231第5章计算智能(2):进化计算人工生命5.1遗传算法5.2进化策略5.3进化编程5.4人工生命1/22/20232第5章计算智能(2):进化计算人工生命5.1遗传算法5.2进化策略5.3进化编程5.4人工生命1/22/202335.1遗传算法遗传算法是为那些难以找到传统数学模型的难题找出一个解决方法。遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。霍兰德(Holland)在他的著作《AdaptationinNaturalandArtificialSystems》首次提出遗传算法。1/22/20234基本概念种群：初始给定的多个解的集合，它是问题解空间的一个子集。个体：种群中的单个元素，通常由一个用于描述其基本遗传结构的数据结构来表示，如用0，1组成的长度为l的串来表示个体。染色体：对个体进行编码后得到的编码串。染色体中的每一位成为基因，若干基因构成的有效信息段称为基因组。适应度函数：用来对种群中个体的适应型进行度量的函数。1/22/202355.1遗传算法基本机理我们以霍兰德(Holland)的遗传算法通常被称为“简单遗传算法”(简称SGA)来分析遗传算法的结构和机理。结合推销员旅行问题(货郎担问题(TravellingSalesmanProblem，简记为TSP))加以说明：设有n个城市，城市i和城市j之间的距离为d(i，j)，i,j=1,...,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。1/22/202365.1遗传算法基本机理1.编码与解码

我们可以把复杂的问题结构化为简单的位串形式编码表示，这个过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码。我们把位串形式编码表示叫染色体，有时也叫个体。对TSP可以按一条回路城市的次序进行编码，比如码串134567829表示从城市1开始，依次是城市3,4,5,6,7,8,2,9，最后回到城市1。一般情况是从城市w1开始，依次经过城市w2,……，wn，最后回到城市w1，我们就有如下编码表示：

w1w2……wn由于是回路，记wn+1=w1。它其实是1，……，n的一个循环排列。要注意w1,w2,……，wn是互不相同的。1/22/202375.1遗传算法基本机理2.适应度函数为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。通过适应度函数来决定染色体的优、劣程度，它体现了自然进化中的优胜劣汰原则。对优化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长度的倒数就可以为TSP的适应度函数：请注意其中wn+1=w1。适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距，一个染色体与问题的最优解染色体之间的差距小，则对应的适应度函数值之差就小，否则就大。适应度函数的取值大小与求解问题对象的意义有很大的关系。1/22/202385.1遗传算法基本机理遗传操作简单遗传算法的遗传操作主要有三种:选择、交叉、变异。选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制，令Σfi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi／Σfi。1/22/202395.1遗遗传算算法基本机理理交叉操作作的简单单方式是是将被选选择出的的两个个个体P1和P2作为父父母个体体，将两两者的部部分码值值进行交交换。假假设有如如下八位位长的二二个体：：产生一个个在1到到7之间间的随机机数c，，假如现现在产生生的是3，将P1和P2的低低三位交交换：P1的高高五位与与P2的的低三位位组成数数串10001001，这就就是P1和P2的一个个后代Q1个体体；P2的高五五位与P1的低低三位组组成数串串11011110，，这就是是P1和和P2的的一个后后代Q2个体。。其交换换过程如如下图所所示：1/7/2023105.1遗遗传算算法基本机理理变异操作作的简单单方式是是改变数数码串的的某个位位置上的的数码。。我们先先以最简简单的二二进制编编码表示示方式来来说明，，二进制制编码表表示的每每一个位位置的数数码只有有0与1这两个个可能，，比如有有如下二二进制编编码表示示：1/7/2023115.1遗遗传算算法基本机理理其码长为为8，随随机产生生一个1至8之之间的数数k，假假如现在在k=5，对从从右往左左的第5位进行行变异操操作，将将原来的的0变为为1，得得到如下下数码串串：二进制编编码表示示时的简简单变异异操作是是将0与与1互换换：0变变异为1，1变变异为0。现现在在对TSP的变变异操作作作简单单介绍，，随机产产生一个个1至n之间的的数k，，决定对对回路中中的第k个城市市的代码码wk作作变异操操作，又又产生一一个1至至n之间间的数w，替代代wk，，并将wk加到到尾部，，得到：：w1w2………wk-1wwk+1………wnwk你发现这这个串有有n+1个数码码，注意意数w其其实在此此串中出出现重复复了，必必须删除除与数w相重复复的，得得到合法法的染色色体。1/7/202312生物进化化与遗传传算法之之间的对对应关系系生物进化中的概念遗传算法中的作用环境适应函数适应性适应值函数适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择一组解交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程1/7/2023135.1遗传传算法求解步骤遗传算法类似似于自然进化化，通过作用用于染色体上上的基因寻找找好的染色体体来求解问题题。与自然界相似似，遗传算法法对求解问题题的本身一无无所知，它所所需要的仅是是对算法所产产生的每个染染色体进行评评价，并基于于适应值来选选择染色体，，使适应性好好的染色体有有更多的繁殖殖机会。在遗传算法中中，通过随机机方式产生若若干个所求解解问题的数字字编码，即染染色体，形成成初始群体；；通过适应度度函数给每个个个体一个数数值评价，淘淘汰低适应度度的个体，选选择高适应度度的个体参加加遗传操作，，经过遗传操操作后的个体体集合形成下下一代新的种种群。对这个个新种群进行行下一轮进化化。1/7/2023145.1遗遗传算算法求解步步骤1/7/2023155.1遗遗传算算法收敛性性一般的的遗传传算法法不一一定收收敛，，采用用优秀秀个体体保护护法就就是将将每代代中的的最优优个体体，直直接进进入子子代，，相应应淘汰汰其子子代中中适应应度最最差的的个体体，使使种群群规模模不变变。求到的的解通通常只只是所所要解解决问问题的的最优优解的的一个个近似似解，，或者者叫满满意解解。近近似解解与问问题真真正的的最优优解的的差是是一个个统计计意义义下的的量，，也就就是说说每次次程序序运行行得到到的解解的质质量可可能是是有较较大的的差别别的。。1/7/2023165.1遗遗传算算法发展现现状如果一一个应应用问问题不不能求求得目目标函函数的的全局局最优优值,而只只能或或只希希望求求一定定意义义下的的“满满意解解”，，这时时,可可供选选择的的方法法之一一自然然是遗遗传算算法，，因为为遗传传算法法比其其他算算法有有更多多的优优势。。近年来来遗传传算法法在商商业应应用方方面取取得了了一系系列重重要成成果。。比如如通用用电器器公司司的计计算机机辅助助设计计系统统Engeneous,这是是一个个采用用了遗遗传算算法以以及其其他传传统的的优化化技术术做为为寻优优手段段的混混合系系统(hybridsystem)。Engeneous已成成功地地应用用于汽汽轮机机设计计,并并改善善了新新的波波音777发动动机的的性能能，这这是目目前正正在研研究和和应用用的一一个重重要方方面。。1/7/2023175.1遗遗传算算法发展现现状遗传算算法具具有隐隐并行行性，，它可可容易易改造造成为为并行行/分分布式式算法法，用用来解解决那那些复复杂性性问题题。到目前前，遗遗传算算法的的理论论机制制仍不不是很很清楚楚，这这可能能和生生命科科学的的研究究一样样，将将是一一个永永恒的的研究究课题题，但但也是是一个个难题题。已已有很很多学学者对对遗传传算法法作了了一些些深入入的研研究，，近几几十年年来，，遗传传算法法的文文献已已相当当多。。1/7/2023185.2进进化策略进化策略(evolutionstrategies,ES)是一类模模仿自然进进化原理以以求解参数数优化问题题的算法。。它是雷切伯伯格、施韦韦费尔和彼彼得.比纳纳特于1964年提提出来的，，并在德国国共同建立立。试探答案的的组成部分分被看做是是个体的行行为特性，，而不是染染色体中的的基因。雷切伯格1973年年进行了多多父代单子子代的工作作，施韦费费尔1981年创造造性使用了了多父代多多子代。1/7/2023195.2进进化策略进化策略是是可替代工工程师直觉觉的一种方方法。直到到最近，当当没有分析析对象函数数可用，传传统的优化化方法不存存在，工程程师必须依依赖于他们们的直觉时时，进化策策略才被用用于优化技术问题中。和遗传算法法不同，进进化策略仅仅用到突变操作。1/7/2023205.2进进化策略进化算法开始初始种群评价产生机制形成下一代种群停机输出NY1/7/2023215.2进进化策略与遗传算法法的区别(1)进化化策略和遗传算法表表示个体的的方式不同同，进化策策略在浮点点矢量上运运行，而遗遗传算法一一般运行在在二进制矢矢量上。(2)进化化策略和遗传算法的的选择过程程不同。(3)进化化策略和遗传算法的的复制参数数不同，遗遗传算法的的复制参数数在进化过过程中保持持恒定，而而进化策略略时时改变变它们。1/7/2023225.3进进化编编程又称进化化规划：：根据正正确预测测的符号号数来度度量适应应值。通通过变异异，为父父代群体体中的每每个机器器状态产产生一个个子代。。父代和和子代中中最好的的部分被被选择生生存下来来。1/7/2023235.3进进化编编程的步步骤产生初始始群体，，它由关关于问题题(计算算机程序序)的函函数随机机组合而而成迭代完成成下述过过程，直直到满足足选种标标准为止止(1)执执行群体体中的每每个程序序，根据据它解决决问题的的能力，，给它指指定一个个适应值值(2)应应用变异异等操作作创造的的计算机机程序群群体。在后代中中适应值值最高的的计算机机程序个个体被指指定为进进化编程程的结果果。1/7/2023245.4人人工生生命人工生命命是指具具有生命命特征的的人造系系统。人工生命命是20世纪80年代代后期开开始兴起起的一种种新的学学科领域域，也是是计算机机科学继继人工智智能之后后出现的的新的发发展方向向之一。。世界上首首先提出出“人工工生命””概念的的人，是是美国洛洛斯·阿阿莫斯国国家实验验室的克克里斯··兰顿博博士。1/7/2023255.4人人工生生命人工生命命的研究究现状与与人工智智能早期期历史可可以说是是并行的的。40年代代末，50年代代初，冯冯.诺伊伊曼提出出了…..1956年达特特默斯的的夏季讨讨论会上上……60年代代，罗森森勃拉特特(Rosenblatt)研究感感知机，，70年代代以来，，乔姆斯斯基(Chomsky)的形形式语言言理论应应用在程程序设计计语言的的规范说说明和开开发编译译程序1/7/2023265.4人人工生生命人工生命命是形成成新的信信息处理理体系强强大的推推动力，，并成为为研究生生物的一一个特别别有用的的工具。。人工生生命的研研究可能能将信息息科学和和生命科科学结合合起来，，形成生生命信息息科学。。在21世纪初初人工生生命的研研究将会会蓬勃发发展，并并取得突突破性进进展。人工生命命研究的的科学问问题如下下：生命自组组织和自自复制,发育和和变异,系统复复杂性,进化和和适应动动力学,智能主主体,自自主系统统,机器器人和人人工脑：：1/7/2023275.4人人工生命实例人工脑澳大利亚一一名科学家家正在发明明全球首个个模仿人脑脑的人工脑脑袋，相信信在约10年后，这这人工脑的的智力便能能超越人脑脑40倍倍。正在日本进进行研究的的澳大利亚亚科学家加加里斯表示示，他发明明的“细胞胞自动机””（CAM）便可以以制造出用用硅制成的的7500万人工神神经细胞-一种类似似人脑细胞胞的功能。。这个神经经细胞网络络跟人脑一一样随机连连结，且会会按照达尔尔文的进化化论，像人人脑神经细细胞般出现现错误情况况。但整个个电路每分分钟仍能运运作数千次次。加里斯预计计，完成这这第一代人人工脑后，，便会将之之发展为一一只机械猫猫。此后研研究便会发发展第二代代，至2007年，，神经细胞胞会超过100亿个个，即已达达到一个弱弱智人士的的智力，要要再发展至至普通成人人智力亦非非难事。1/7/2023285.4人人工生生命实例计算机机病毒毒20世世纪80年年代，，计算算机技技术的的飞速速发展展带来来的负负面效效应。。计算算机病病毒指指在计计算机机上传传染的的与生生物学学中的的病毒毒具有有相似似生命命现象象的有有害程程序。。它能能够通通过自自身繁繁殖，，把自自己复复制到到计算算机内内已存存储的的其他他程序序上的的计算算机程程序。。计算机机病毒毒一般般是恶恶性的的，人人为的的用计计算机机语言言写成成的可可存储储的、、可执执行的的计算算机非非法程程序。。1/7/2023295.4人人工生生命实例计算机机进程程类似于于计算算机病病毒，，把进进程当当作生生命体体，可可在时时间空空间中中繁殖殖，从从环境