智能控制_03遗传算法2.ppt

智能控制系统,天津大学电气与自动化工程学院,三,天津大学自动化学院,3.遗传算法的理论基础,指导遗传算法的基本理论，是J.H.Holland教授创立的模式理论。该理论揭示了遗传算法的基本机理。3.1基本概念问题的引出例：求maxf(x)=x2x0,31,天津大学自动化学院,3.遗传算法的理论基础,分析当编码的最左边字符为“1”时，其个体适配值较大，如2号个体和4号个体，我们将其记为“1*”；其中2号个体适配值最大，其编码的左边两位都是1，我们记为“11*”；当编码的最左边字符为“0”时，其个体适配值较小，如1号和3号个体，我们记为“0*”。,天津大学自动化学院,3.遗传算法的理论基础,结论从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，而对其他字符不关心。换句话讲我们只关心字符的某些特定形式，如1*，11*，0*这种特定的组合形式就叫模式。,天津大学自动化学院,3.遗传算法的理论基础,模式、模式位数及模式定义长度模式(Schemata)指编码的字符串在某些确定位置上具有相似性的位串子集的相似性模板。使用三元素字母表0，1，*可以构造出任意模式。其中“*”称为通配符，表示这一位可以是0，1中任意一种。使用大写字母H代表模式，例如H=1100*,天津大学自动化学院,3.遗传算法的理论基础,匹配的定义模式中的“0”和位串中的“0”匹配，模式中的“1”和位串中的“1”匹配，模式中的“*”和位串中的“0”或“1”匹配.以五位二进制字符串为例。模式*111*可匹配4个个体：01110，01111，11110，11111模式*0000则匹配2个个体：10000，00000,天津大学自动化学院,3.遗传算法的理论基础,模式位数(Order)指模式中有定义的非“*”位个数，记为O(H)例如，若H=00*1*0，则O(H)=4模式的定义长度（DefiningLength）指模式中最两端的有定义位置之间的距离，记为(H)例如，若H=00*1*0，则(H)=6-1=5若H=*11*，则(H)=4-3=1若H=*，则(H)=0,天津大学自动化学院,3.遗传算法的理论基础,模式长度越短，被破坏的可能性越小，长度为0的模式最难被破坏。编码位串的模式数目模式总数二进制位串假设字符串的长度为l，字符串中每一个字符可取(0,1,*)三个符号中任意一个，可能组成的模式数目最多为：333333=3l,天津大学自动化学院,3.遗传算法的理论基础,一般情况假设字符的长度为l，字符串中有k种具体字符可取，可能组成的模式数目最多为：(k+1)(k+1)(k+1)(k+1)(k+1)=(k+1)l某一特定编码串包含的模式数二进制位串对于长度为l的某二进制字符串，它含有的模式总数最多为：2222=2l,天津大学自动化学院,3.遗传算法的理论基础,注这个数目是指字符串已确定为0或1，每个字符只能在已定值(0/1)或*中选取。某一特定群体所含模式数在长度为l，规模为n的二进制编码字符串群体中，一般包含有2ln2l个模式。,天津大学自动化学院,3.遗传算法的理论基础,3.2模式定理引入模式的概念之后，遗传算法的实质可看作是对模式的一种运算。对基本遗传算法(GA)而言，也就是某一模式H的各个样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式。复制时的模式数目公式推导假设在第t次迭代时,群体A(t)中有n个个体,其中有m个符合特定模式,记作m(,t)。,天津大学自动化学院,3.遗传算法的理论基础,个体i按其适配值fi的大小进行复制。从统计意义讲，个体i被复制的概率pi是：因此复制后在下一代群体(t+1)中，群体内属于模式（或称与模式匹配）的个体数目m(,t+1)可用平均适配值按下式近似计算()是属于模式H的个体的平均适配值）：,天津大学自动化学院,3.遗传算法的理论基础,设第t代所有个体(不论它属于何种模式)的平均适配值是,有等式:综合上述两式，复制后模式H所拥有的个体数目可按下式近似计算：,天津大学自动化学院,3.遗传算法的理论基础,结论上式说明复制后下一代群体中属于模式H的个体数目，取决于该模式的平均适配值与群体的平均适配值之比;只有当模式H的平均值大于群钵的平均值时，H模式的个体数目才能增长。否则，H模式的数目要减小。模式的这种增减规律，正好符合复制操作的“优胜劣汰”原则，这也说明模式的确能描述编码字符串的内部特征。,天津大学自动化学院,3.遗传算法的理论基础,进一步推导假设某一模式H在复制过程中其平均适应度f(H)比群体的平均适配值高出一个定值，其中c为常数，则上式改写为：从第一代开始，若模式H以常数c繁殖到第t+1代，其个体数目为：结论说明模式H所拥有的个体数目在复制过程中以指数形式增加或减小。,天津大学自动化学院,3.遗传算法的理论基础,交叉时的模式数目这里以单点交叉算子为例研究。举例有两个模式H1:“*1*0”H2:“*10*”它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表示）A:“0111000”选择个体A进行交叉,随机选择交叉点。,天津大学自动化学院,3.遗传算法的理论基础,H1:“*1*0”交叉点选在第26之间都可能破坏模式H1;H2:“*10*”交叉点在第45之间才破坏H2。公式推导交换发生在模式H的定义长度(H)范围内，即模式被破坏的概率是：例：H1被破坏的概率为：5/6H2被破坏的概率为：1/6,天津大学自动化学院,3.遗传算法的理论基础,模式不被破坏，存活下来的概率为：若交叉概率为pc，则模式存活下来的概率为：经复制、交叉操作后，模式H在下一代群体中所拥有的个体数目为：,天津大学自动化学院,3.遗传算法的理论基础,结论模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏。变异时的模式数目这里以基本位变异算子为例研究。公式推导变异时个体的每一位发生变化的概率是变异概率pm，也就是说，每一位存活的概率是(1-pm)。根据模式位数o(H)，可知模式中有明确含意的字符有o(H)个，于是模式H存活的概率是：,天津大学自动化学院,3.遗传算法的理论基础,通常pm1，上式用泰勒级数展开取一次项，可近似表达为：结论上式说明，模式的阶次o(H)越低，模式H存活的可能性越大，反之亦然。模式定理综合上述分析可以得出遗传算法经复制、交叉、变异操作后，模式H在下一代群体中所拥有的个体数目：,天津大学自动化学院,3.遗传算法的理论基础,模式定理适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算法的迭代过程中将按指数规律增长。模式定理深刻地阐明了遗传算法中发生“优胜劣汰”的原