第三章 模式理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 模式理论,指导遗传算法的基本理论，是,J.H.Holland,教授创立的,模式理论,。该理论揭示,了遗传算法的基本机理。,3.1,基本概念,3.1.1,问题的引出,例：求,max f(x)=x,2,x,0,31,分析,当编码的最左边字符为“,1”,时，其个体适应度较大，如,2,号个体和,4,号个体，,我们将其记为“,1*”,；,其中,2,号个体适应度最大，其编码的左边两位都是,1,，我们记为“,11*”,；,当编码的最左边字符为“,0”,时，其个体适应度较小，如,1,号和,3,号个体，,我们记为“,0*”,。,结论,从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，而对其他字符不关心。换句话讲我们只关心字符的某些特定形式，如,1*,，,11*,，,0*,。这种特定的形式就叫,模式,。,3.1.2,模式、模式阶及模式定义长度,模式,(Schema),指,编码的字,符串中具,有,类似特征的子集。,以五,位,二进制字符,串,为例，,模式,*,111*,可代表,4,个个体：,01110,，,01111,，,11110,，,11111,；,模式,*,0000,则代表,2,个个体：,10000,，,00000,。,个体,是由二值字符集,V=0,1,中的元素所组成的一个编码串,;,而,模式,却是由三值字符集,V=0,1,*,中的元素所组成的一个编码串，其中,“,*,”表示通配符，它既可被当作“,1”,也可被当作“,0”,。,模式阶,(Schema,Order),指模式中已有明确含意,(,二进制字符时指,0,或,1),的字符个数，,记做,o(s),，式中,s,代表模式。,例如，模式,(011*1*),含有,4,个明确含意的字符，其阶次是,4,，,记作,o(011*1*)=4;,模式,(0*),的阶次是,1,，记作,o(0*)=1,。,阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；,当模式阶次为零时，它没有明确含义的字符，其概括性最强。,模式的定义长度,(,Schema,Defining Length),指模式中第一个和最后一个具有明确含意的字符之间的距离，记作,(s),。,例如，模式,(011*l*),的第一个字符为,0,，最后一个字符为,l,，中间有,3,个字,符，其定义长度为,4,，记作,(011*l*)=4,；,模式,(0*),的长度是,0,，记作,(0*)=0,；,一般地，有式子,(s),b,a,式中,b,模式,s,中最后一个明确字符的位置,;,a,模式,s,中最前一个明确字符的位置。,模式的长度代表该模式在今后遗传操作,(,交叉、变异,),中被破坏的可能性：,模式长度越短，被破坏的可能性越小，长度为,0,的模式最难被破坏。,3.1.3,编码字符串的模式数目,(1),模式总数,二进制字符串,假设字符的长度为,l,，字符串中每一个字符可取,(0,1,*),三个符号中任意,一个，可能组成的模式数目最多为：,3,3,3,3=,(2+1),l,一般情况下，,假设字符串长度为,l,，字符的取值为,k,种，字符串组成的模式数目,n,1,最多,为：,n,1,=(k+1),l,(2),编码字符串（一个个体编码串）所含模式总数,二进制字符串,对于长度为,l,的某二进制字符串，它含有的模式总数最多为：,2,2,2,2=,2,l,注意,这个数目是指字符串已确定为,0,或,1,，每个字符只能在已定值,(0/1),或,*中选取；,前面所述的,n,1,指字符串未确定，每个字符可在,0,1,*,三者中选取。,一般情况下,长度为,l,、取值有,k,种的某一字符串，它可能含有的模式数目最多为：,n,2,=k,l,(3),群体所含模式数,在长度为,l,，,规模为,M,的二进制编码字符串群体中，一般包含有,2,l,M 2,l,个,模式。,3.2,模式定理,由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看,作是对模式的一种运算。对基本遗传算法,(GA),而言，也就是某一模式,s,的各个,样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式。,3.2.1,复制时的模式数目,这里以比例选择算子为例研究。,公式推导,(1),假设在第,t,次迭代时,群体,P(t),中有,M,个个体,其中,m,个个体属于模式,s,记作,m(s,t),。,(2),个体,a,i,按其适应度,f,i,的大小进行复制。,从统计意义讲，个体,a,i,被复制的概率,p,i,是：,(3),因此复制后在下一代群体,P(t+1),中，群体内属于模式,s,（或称与模式,s,匹配）,的个体数目,m(s,t+1),可用平均适应度按下式近似计算：,f(s),式中,第,t,代属于模式,s,的所有,个体之平均适应度；,M,群体中拥有的个体数目。,f(s),(4),设第,t,代所有个体,(,不论它属于何种模式,),的平均适应度是,有等式,:,f,(5),综合上述两式，复制后模式,s,所拥有的个体数目可按下式近似计算：,f,f,f(s),结论,上式说明复制后下一代群体中属于模式,s,的个体数目，取决于该模式的平均,适应度 与群体的平均适应度 之比,;,只有当模式,s,的平均值 大于群钵的平均值 时，,s,模式的个体数目才,能增长。否则，,s,模式的数目要减小。,模式,s,的这种增减规律，正好符合复制操作的“优胜劣汰”原则，这也说明模式的确能描述编码字符串的内部特征。,f(s),f,f(s),f,进一步推导,(1),假设某一模式,s,在复制过程中其平均适应度 比群体的平均适应度 高,出一个定值 ，其中,c,为常数，则上式改写为：,f,f(s),c f,结论,从数学上讲，上式是一个指数方程，它说明模式,s,所拥有的个体数目,在复制过程中以指数形式增加或减小。,f,c f,f,+,=m(s,t),(,1+c),(2),从第一代开始，若模式,s,以常数,c,繁殖到第,t+1,代，其个体数目为：,m(s,t+1)=m(s,1),(,1+c),t,3.2.2,交叉时的模式数目,这里以单点交叉算子为例研究。,举例,(1),有两个模式,s,1,:“*1*0”,s,2,:“*1 0*”,它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表示）,a:“0 1 1 1 0 0 0”,(2),选择个体,a,进行交叉,(3),随机选择交叉点,s,1,:“*1 *0 ”,交叉点选在第,2 6,之间都可能破坏模式,s,1,;,s,2,:“*1 0 *”,交叉点在 第,4 5,之间才破坏,s,2,。,公式推导,(1),交换发生在模式,s,的定义长度,(s),范围内，即模式被破坏的概率是：,例：,s,1,被破坏的概率为：,5/6,s,2,被破坏的概率为：,1/6,l,(2),模式不被破坏，存活下来的概率为：,(3),若交叉概率为,p,c,，则模式存活下来的概率为：,结论,模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏。,(4),经复制、交叉操作后，模式,s,在下一 代群体中所拥有的个体数目为：,l-,1,l-,1,f,f(s),l-,1,3.2.3,变异时的模式数目,这里以基本位变异算子为例研究。,公式推导,(1),变异时个体的每一位发生变化的概率是变异概率,p,m,，也就是说，每一位存,活的概率是,(1-p,m,),。根据模式的阶,o(s),，可知模式中有明确含意的字符有,o(s),个，于是模式,s,存活的概率是：,(2),通常,p,m,1,，上式用泰勒级数展开取一次项，可近似表达为：,p,s,1 p,m,o(s),结论,上式说明，模式的阶次,o(s),越低，模式,s,存活的可能性越大，反之亦然。,3.2.4,模式定理,综合式,、,、,可以得出遗传算法经复制、交叉、变异操作后，模式,s,在,下一代群体中所拥有的个体数目，如下式所示：,模式定理,适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算,法的迭代过程中将按指数规律增长。,模式定理深刻地阐明了遗传算法中发生“优胜劣汰”的原因。在遗传过程,中能存活,的模式都是定义长度短、阶次低、平均适应度高于群体平均适应度的,优良模式。遗传算法正是利用这些优良模式逐步进化到最优解。,f,f(s),l-,1,3.2.5,模式定理示例,例：求,max f(x)=x,2,x,0,31,个 体 变 化,叉,叉,S,1,S,2,S,3,叉,3.3,建筑块假说,3.3.1,模式对搜索空间的划分,举例,以,max f(x)=x,2,x,0,31,为例，,图中：横坐标表示,x,，,纵坐标代表适应度,f(x)=x,2,，用千分数表示，,弧线表示适应度曲线，,网点区代表所有符合此模式的个体集合。,模式,1,：,1*,模式,2,：,10*,模式,3,：*,1*1,结论,模式能够划分搜索空间，而且模式的阶越高，对搜索空间的划分越细致。,3.3.2,分配搜索次数,模式定理告诉我们：,GA,根据模式的适应度、长度和阶次为模式分配搜索次数。,为那些适应度较高，长度较短，阶次较低的模式分配的搜索次数按指数率增长；,为那些适应度较低，长度较长，阶次较高的模式分配的搜索次数按指数率衰减。,3.3.3,建筑块假说,前面我们已经介绍了,GA,如何划分搜索空间和在各个子空间中分配搜索次数，,那么,GA,如何利用搜索过程中的积累信息加快搜索速度呢？,Holland,和,Goldberg,在模式定理的基础上提出了“建筑块假说”。,建筑块（或称积木块）,(Buliding Block),短定义长度、低阶、高适应度的模式。,之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜,索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像,搭积木一样、将它们拼接在一起，从而逐渐地构造出适应度越来越高的个,体编码串。,建筑块假说,GA,在搜索过程中将不同的“建筑块”通过遗传算子（如交叉算子）的作用结合在一起，形成适应度更高的新模式。这样将大大缩小,GA,的搜索范围。,建筑块混合,建筑块通过遗传算子的作用集合在一起的过程称为“建筑块混合”。,当那些构成最优点（或近似最优点）的“建筑块”结合在一起时，就得到了最优点。,建筑块混合的例子,问题的最优用三个建筑块,BB,1,BB,2,BB,3,表示；,群体中有,8,个个体。,初始群体中个体,1,，个体,2,包含建筑块,BB,1,，个体,3,包含,BB,3,个体,5,包含,BB,2,。,P,1,P,2,P,3,P,4,P,5,P,6,P,7,P,8,BB,1,BB,2,BB,1,BB,3,P,1,P,2,P,3,P,4,P,5,P,6,P,7,P,8,BB,2,BB,3,BB,1,BB,3,BB,1,BB,2,BB,1,BB,1,BB,2,BB,3,P,1,P,2,P,3,P,4,P,5,P,6,P,7,P,8,BB,2,BB,3,BB,1,BB,3,BB,1,BB,2,BB,1,BB,1,BB,2,BB,3,BB,2,BB,3,初始群体,第二代群体,第三代群体,说明：,第三代群体中,出现了一个包,含三个“建筑块”,的个体,3,。,个体,3,就代表这,个问题的最优解。,3.4,隐含并行性（内在并行性）,隐含并行性（,Implicit Parallelism,）是模式理论的另一个重要内容。,这一机理说明，在遗传算法中尽管每一代只处理,M,个个体，但实际上却是处理,了,M,3,以上的模式。,隐含并行性定理,设,(0,1),是一个很小的数，,模式存活的最小长度,群体规模为,则,GA,在一次迭代中所处理的“存活率”大于,(1-,),的模式数约为,O(M,3,),。其中 表示上取值。,公式推导,以二进制编码为例。在长度为,l,，规模为,M,的群体中，包含了,2,l,M,2,l,个不,同的模式，随着进化过程的进行，这些模式中一些定义长度较长的模式被破,坏掉，而另一些定义长度较短的模式却能够生存下来。,(1),模式存活