搜索
第5章计算智能(2)进化计算人工生命•进化计算包括：–遗传算法(geneticalgorithms，GA)–进化策略(evolutionstrategies)–进化编程(evolutionaryprogramming)–遗传编程(geneticprogramming)•人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。•人工生命是人工智能和计算智能的一个新的研究热点。5.1遗传算法•遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。•遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。•进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。•遗传算法自从1965年提出以来，在国际上已经形成了一个比较活跃的研究领域，已召开了多次比较重要的国际会议和创办了很多相关的国际刊物.•遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。5.1.1遗传算法的基本机理•霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适当的改进，来分析遗传算法的结构和机理。•编码与解码•适应度函数•遗传操作5.1遗传算法1.编码与译码•许多应用问题结构很复杂，但可以化为简单的位串形式编码表示，将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫译码。•把位串形式编码表示叫染色体或基因型（基因表达），有时也叫个体。•原问题结构称为表现型。例：货郎担问题(TravellingSalesmanProblem，简记为TSP)：设有n个城市，城市i和城市j之间的距离为d(i，j)i,j=1,...,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。•对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是互不相同的。2.适应度函数•为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。通过适应度函数来决定染色体的优、劣程度，它体现了自然进化中的优胜劣汰原则。对优化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长度的倒数就可以为TSP的适应度函数：•其中wn+1=w1。适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距，一个染色体与问题的最优解染色体之间的差距小，则对应的适应度函数值之差就小，否则就大。适应度函数的取值大小与求解问题对象的意义有很大的关系。3.遗传操作•简单遗传算法的遗传操作主要有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。•选择操作也叫复制操作，根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。●选择操作——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法——适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pc)()(iicxfxfPxi为种群中第i个染色体，选择操作具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=∑f(xi)3）产生一个随机数N，0〈N〈sum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。染色体的适应度和所占的比例用转轮方法进行选择举例1：具有6个染色体的二进制编码、适应度值、Pc累计值。染色体编号12345678910适应度8217721211737被选概率0.110.030.220.090.030.160.140.090.040.09适应度累计8102734364859666976随机数2349761312757所选染色体号码37103137染色体被选的概率被选的染色体个数举例2：10个染色体种群按比例的选择过程●交叉操作方法:随机选择两个染色体(双亲染色体),随机指定一点或多点交叉位置,进行交换,可得两个新的染色体(子辈染色体).新的子辈染色体:A’11010001B’01011110模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.●变异复制不能产生新个体,交叉产生新的染色体5.1.2遗传算法的求解步骤1.遗传算法的特点(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。5.1遗传算法2.遗传算法的框图(图5.2)(1)初始化群体;(2)计算群体上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4)按概率Pc进行交叉操作;(5)按概率Pm进行突变操作;(6)若没有满足某种停止条件，则转第(2)步，否则进入下一步。(7)输出群体中适应度值最优的染色体作为问题的满意解或最优解。5.1遗传算法初始化种群变异操作计算适应度值选择操作交叉操作进化的种群终止条件开始图5.2算法框图(参考）5.1遗传算法一般遗传算法的主要步骤如下：(1)随机产生一个由确定长度的特征字符串组成的初始群体。(2)对该字符串群体迭代的执行下面的步①和②，直到满足停止标准：①计算群体中每个个体字符串的适应值；②应用选择、交叉和变异等遗传算子产生下一代群体。(3)把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。5.1遗传算法产生初始群体是否满足停止准则计算每个个体的适应值i=M?GEN:=GEN+1依概率选择遗传操作执行复制选择一个个体i:=i+1选择两个个体选择一个个体执行变异i:=0GEN:=0复制到新群体i:=i+1将两个后代插入新群体插入到新群体执行杂交指定结果结束是否是否变异复制交叉5.1遗传算法遗传算法的一般结构表示•Procedure:GeneticAlgorithms•begin•t←0;•initializeP(t);evaluateP(t);•while(notterminationcondition)do•begin•recombineP(t)toyieldC(t);•evaluateC(t);•selectP(t+1)fromP(t)andC(t);•t←t+1;•end•end5.1遗传算法5.1.3遗传算法求解举例5.1遗传算法设f(x)=x·sin(10π·x)+1.0，用SGA求参数设置二进制编码(每个染色体用22位二进制串表示)种群大小为4染色体长为22位举例：用遗传算法求解最优化问题64遗传算法归纳为五个基本组成部份•方案表示（编码和解码）•群体初始化•适应度函数•遗传操作•算法参数:种群规模、Pc、Pm5.1遗传算法简单遗传算法（GA）的基本参数①种群规模P:参与进化的染色体总数.②代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0G1③选择方法:转轮法,精英选择法,竞争法.④交叉率:Pc一般为60~100%.⑤变异率:Pm一般为0.1~10%实验:种群大小popsize=10;变异概率取Pm=0.01，交叉概率取Pc=0.2;选择方法：转轮法举例：14步骤1）编码：确定二进制的位数；组成个体（染色体）位的二进制的值，的第是相应于。和分别为和的最大值和最小值。是和或是，精度二进制位数取决于运算nqbqqqqqyxqqbqqqqqnNnnnnn08,21212minmaxminmax10minminmaxminmax步骤2）选择种群数P和初始个体，计算适应度值，P=20；步骤3）确定选择方法；交换率PC；变异率Pm。选择方法用竞争法；PC=0.7,Pm=0.05计算结果：①8代后，f(x,y)=0.998757,②41代后，f(x,y)=1.00000,x=3.000290,y=2.999924.③160次适应度计算，达到最优值。5.2进化策略•进化策略(EvolutionStrategies，ES)是一类模仿自然进化原理以求解参数优化问题的算法。•它是由雷切伯格（Rechenberg）、施韦费尔（Schwefel）和彼得·比纳特（PeterBienert）于1964年提出的，并在德国共同建立的。5.2.1进化策略的算法模型•寻求与函数极值关联的实n维矢量x。•随机选择父矢量的初始群体。•父矢量xi,i=1,…,p产生子代矢量xi。•对误差(i=1,…,p)排序以选择和决定保持哪些矢量。•继续产生新的试验数据以及选择最小误差矢量。5.2进化策略5.2.2进化策略和遗传算法的区别•进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原理的算法。•两者也存在着区别，其中最基本的区别是它们的研究领域不同。–进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法。–遗传算法从广义上说是一种自适应搜索技术。5.2进化策略5.3进化编程•进化编程(EvolutionaryProgramming，EP)，又称为进化规划（EvolutionaryPlanning），是由福格尔（Fogel）在1962年提出的一种模仿人类智能的方法。•进化编程根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。•它的提出是受自然生物进化机制的启发。5.3.1进化编程的机理与表示•进化编程的过程，可理解为从所有可能的计算机程序形成的空间中，搜索具有高的适应度的计算机程序个体。•进化编程设计强调群体行为的变化。进化编程系统的表示自然地面向任务级。一旦选定一种适应性表示，就可以定义依赖于该表示的变异操作，在具体的父辈行为上创建后代。5.3进化编程5.3.2进化编程的步骤进化编程分为三个步骤：•产生出初始群体。•迭代完成下述子步骤，直至满足选种标准为止：–执行群体中的每个程序。–应用变异等操作创造新程序群体。•在后代中适应值最高的计算机程序个体被指定为进化编程的结果。5.3进化编程变异和创造子代评估已存在的FSM用最好的状态机预测和添加符号选择父代初始化观测顺序是否是否预测初始化群体图5.6进化编程的基本过程5.3进化编程5.4人工生命•自然界是生命之源。自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无穷。•人工生命（ArtificialLife，AL）试图通过人工方法建造具有自然生命特征的人造系统。•人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。5.4.1人工生命研究的起源和发展•人类长期以来一直力图用科学技术方法模拟自然界，包括人脑本身。1943年麦卡络奇和皮茨提出了M－P神经学网络模型。•人工生命的许多早期研究工作也源于人工智能。•20世纪70年代以来，康拉德（Conrad）等提出不断完善的“人工世界”模型。•80年代人工神经网络再度兴起，出现了许多新模型和新算法。•90年代关于人工生命的系列性国际学术会议5.4人