人工智能及其应用蔡自兴第四版

人工智能第5章计算智能(2)ComputationalIntelligence进化计算人工生命3进化计算包括：–遗传算法(geneticalgorithms，GA)–进化策略(evolutionarystrategies)–进化编程(evolutionaryprogramming)–遗传编程(geneticprogramming)人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。人工生命是人工智能和计算智能的一个新的研究热点。45.1遗传算法遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。55.1.1遗传算法的基本机理霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。编码与解码适应度函数遗传操作5.1遗传算法61.编码与解码将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。7二进制编码最常用的编码方法假设某一参数的取值范围是[A，B]，AB。用长度为l的二进制编码串来表示该参数，将[A，B]等分成2l-1个子部分，记每一个等分的长度为δ。参数编码的对应关系:11212iliilbABBx解码假设某一个体的编码是：X：xlxl-1xl-2…x2x1，则上述二进制编码所对应的解码公式为：00000000……00000000=0——→A00000000……00000001=1——→A+δ……………11111111……11111111=-1——→Bl28二进制编码的最大缺点之一是长度较大，对很多问题用其他主编码方法可能更有利符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。例如，对于TSP问题，采用符号编码方法，按一条回路中城市的次序进行编码，一般情况是从城市w1开始，依次经过城市w2，……，wn，最后回到城市w1，我们就有如下编码表示：由于是回路，记wn+1=w1。它其实是1，……，n的一个循环排列。要注意w1，w2，……，wn是互不相同的。n适应度函数体现染色体的适应能力，对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitnessfunction）对优化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数：njjjnwwd),(1)...(103.遗传操作简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大（优良）个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。11交叉操作交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换假设有八位长的二个体，产生一个在1到8之间的随机数c，假如现在产生的是3，将P1和P2的低三位交换1000111011011001P1P211000112变异操作返回变异操作的简单方式是改变数码串的某个位置上的数码二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0TSP的变异操作：随机产生一个1至n之间的数k，对回路中的第k个城市的代码wk作变异操作，又产生一个1至n之间的数w，替代wk，并将wk加到尾部，得到：knkk135.1.2遗传算法的求解步骤1.遗传算法的特点(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。5.1遗传算法142.遗传算法的框图(图5.2)(1)初始化种群;(2)计算种群上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4)按概率Pc进行交叉操作;(5)按概率Pm进行变异操作;(6)若没有满足某种停止条件，则转第(2)步，否则进入下一步。(7)输出种群中适应度值最优的染色体作为问题的满意解或最优解。5.1遗传算法15初始化种群变异操作计算适应度值选择操作交叉操作最优解输出终止条件？图5.2算法框图返回5.1遗传算法否是开始结束(1)(2)(3)(4)(5)(6)(7)16遗传算法的一般结构表示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遗传算法173.遗传算法求解举例5.1遗传算法设用SGA求遗传算法归纳为五个基本组成部份方案表示种群初始化适应度函数遗传操作算法参数0.1)10sin()(xxxf]2,1[),(maxxxf185.1.3SGA及其模式定理回顾：–（1）GA的基本原理与算法框架；–（2）GA的基本遗传算子；问题：–（1）基本遗传算法（SGA）的算法步骤；–（2）GA的计算实例；–（3）GA有效性的理论证明；5.1遗传算法19SGA的算法步骤5.1遗传算法(1)编码：随机产生一个由确定长度的特征字符串组成的初始种群。(2)进化：对该字符串种群迭代的执行下面的步①和步②，直到满足停止标准：①计算种群中每个个体字符串的适应值；②应用复制、交叉和变异等遗传算子产生下一代种群。(3)解码：把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。20产生初始种群计算每个个体的适应值GEN:=GEN+1依概率选择遗传操作执行复制选择一个个体i:=i+1选择两个个体选择一个个体执行变异i:=0复制到新种群i:=i+1将两个后代插入新种群插入到新种群执行杂交指定结果是否是否变异复制交叉结束GEN:=0是否满足停止准则i=M?5.1遗传算法21SGA的伪代码描述Procedure:SimpleGeneticAlgorithmsbegint←0;initializeP(t);evaluateP(t);while(notterminationcondition)dobeginrecombineP(t)toyieldC(t);P(t)←C(t);evaluateP(t);t←t+1;endend5.1遗传算法22一个简单的计算实例例：极大值问题maxf(x)=x2,x[0,31]1.编码：5位二进制数；2.初始群体：群体规模为4个个体，随机产生；假设为：01101，11000，01000，100113.适应度计算：（适应值直接取f(x)）4.选择复制产生下一代群体；（选择概率按适应值大小采用轮盘赌的随机策略）5.1遗传算法310f=x2个体编号初始群体基因译码适应度计算f(xi)/f(xi)f(xi)/f下一代群体复制数101101131690.140.581211000245760.491.9723010008640.060.220410011193610.311.231235.个体基因交叉；（一般交叉概率较大0.7～0.9）6.个体基因变异（一般变异概率较小0.001～0.01）7.转3直至算法终止。个体编号复制后的群体基因译码适应度计算交叉对象交叉位置交叉后的群体适应度计算1011011316924011001442110002457614110016253110002457643110117294100111936133100002565.1遗传算法01110011000011001011交叉0011000010变异24模式的定义思考：–（1）SGA优化搜索中遗传算子的作用？–（2）怎样从理论上证明SGA能依概率搜索到优良解答的有效性？模式：我们将群体中的个体即基因串中的相似样板称为“模式”。–模式表示基因串某些特征位相同的结构。–它描述的是一个串中的子集，在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号*代表任意字符，即0或1。例如模式*1*描述了一个四个元的子集{010,011,110,111}。–一般一个模式代表了多个个体，一个个体符合多个模式；5.1遗传算法25模式的阶与定义距模式阶：模式H中确定位置的个数成为模式H的模式阶，记作O（H）。–例如O（011*1*）＝4。–模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本个数就越少。定义距（长度）：模式H中的第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作δ(H)。–例如，δ(011*1**)＝4。–在遗传查找中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。5.1遗传算法26模式定理模式定理（SchemaTheorem）：如果在给定的时间步t，一个特定的模式H有m个代表串包含在种群A(t)中，记为m(H,t)，f(H)表示在时间步t模式H的串平均适应度，整个种群的平均适应度为f，l为二进制染色体基因串长，pc为交叉概率，pm为变异概率，则在基本遗传算法（SGA）的机制下有：–结论2.3.1.1若遗传算法只采用选择复制操作，有下式成立，–结论2.3.1.2若遗传算法同时考虑选择复制与交叉操作，有下式成立，–结论2.3.1.3若遗传算法同时考虑选择复制、交叉与变异操作，有下式成立，fHftHmtHm)(),()1,(]1)(1[)(),()1,(lHpfHftHmtHmc])(1)(1[)(),()1,(mcpHOlHpfHftHmtHm5.1遗传算法27模式定理的意义模式定理的意义：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。积木块假说；SGA最新的理论研究：–（1）浓度模型；–（2）概率模型；5.1遗传算法28GA与进化计算的发展进化计算（Evolutionarycomputing）灵感计算（inspiredcomputing）自然计算（Naturecomputing）–进化计算–蚁群系统–量子遗传算法–人工免疫系统–人工内分泌系统–复杂自适应系统295.2进化策略进化策略(EvolutionStrategies，ES)是一类模仿自然进化原理以求解参数优化问题的算法。它是由雷切伯格（Rechenberg）、施韦费尔（Schwefel）和彼得·比纳特（PeterBienert）于1964年提出的，并在德国共同建立的。305.2.1进化策略的算法模型寻求与函数极值关联的实n维矢量x。随机选择父矢量的初始种群。父矢量xi,i=1,…,p产生子代矢量xi。对误差(i=1,…,p)排序以选择和决定保持哪些矢量。继续产生新的试验数据以及选择最小误差矢量。5.2进化策略315.2.2进化策略和遗传算法