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