遗传算法第三章模式理论课件.ppt

第三章￿￿模式理论￿￿￿￿￿￿￿￿指导遗传算法的基本理论，是J.H.Holland教授创立的模式理论该理论揭示￿￿￿￿了遗传算法的基本机理￿3.1￿￿3.1￿￿基本概念基本概念￿3.1.1￿￿3.1.1￿￿问题的引出问题的引出￿￿￿￿￿￿￿￿￿￿￿例：￿求￿￿￿max￿￿f(x)=x2￿￿￿￿￿￿x￿ {0,31}1遗传算法第三章模式理论￿￿[分析]￿￿￿￿￿•￿￿当编码的最左边字符为“1”时，其个体适应度较大，如2号个体和4号个体，￿￿￿￿￿￿￿￿￿我们将其记为￿“￿1****￿”；￿￿￿￿￿￿￿￿￿其中2号个体适应度最大，其编码的左边两位都是1，我们记为￿“￿11***￿”；￿￿￿￿￿•￿￿当编码的最左边字符为“0”时，其个体适应度较小，如1号和3号个体，￿￿￿￿￿￿￿￿￿我们记为￿“￿0****￿”￿￿￿[结论]￿￿￿￿￿￿￿￿￿从这个例子可以看比，我们在分析编码字符串时，常常只关心某一位或某几位字符，而对其他字符不关心换句话讲．我们只关心字符的某些特定形式，如￿￿￿￿￿￿￿1****，11***，0****这种特定的形式就叫模式￿3.1.2￿￿3.1.2￿￿模式、模式阶及模式定义长度模式、模式阶及模式定义长度￿￿￿￿￿￿￿￿￿￿模式模式模式模式(Schema)(Schema)——指指编码的字符串中具符串中具有类似特征的子集。

似特征的子集￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿以五以五位二二进制字符制字符串为例，例，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿模式模式￿￿* *111*111*￿￿￿可代表可代表4个个体：个个体：￿01110，，01111，，11110，，11111；；￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿模式模式￿￿* *00000000￿￿则代表代表2个个体：个个体：10000，，00000￿￿2遗传算法第三章模式理论￿￿￿￿￿￿￿•￿￿个体是由二值字符集￿V={0,￿1}￿中的元素所组成的一个编码串;￿￿￿￿￿￿￿•￿￿而模式却是由三值字符集￿￿V={0,￿1,*￿}￿中的元素所组成的一个编码串，其中￿￿￿￿￿￿￿￿￿￿￿“￿* ￿*￿”￿表示通配符，它既可被当作￿“1”￿也可被当作￿“0”模式阶模式阶￿ ￿(Schema(Schema￿Order)￿Order)￿￿￿￿￿￿￿￿——指模式中已有明确含意(二进制字符时指0或1)的字符个数，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿记做￿o(s)，式中￿s￿代表模式。

￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿例如，模式￿(￿011*1**￿)￿含有4个明确含意的字符，其阶次是4，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿记作￿o(￿011*1**￿)￿=4;￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿模式￿(￿0******￿)￿的阶次是1，记作￿o(￿0******￿)￿=1￿￿￿￿￿￿￿￿￿•￿￿•￿￿阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然；￿￿￿￿￿￿￿￿￿•￿￿当模式阶次为零时，它没有明确含义的字符，其概括性最强模式的定义长度模式的定义长度(￿ (￿SchemaSchema￿Defining￿￿Length)￿Defining￿￿Length)￿￿￿￿￿￿￿￿——指模式中第一个和最后一个具有明确含意的字符之间的距离，记作￿(s)￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿例如，模式(￿011*l**￿)￿的第一个字符为0，最后一个字符为l，中间有3个字￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿符，其定义长度为4，记作￿￿(￿011*l**￿)￿=￿4￿；￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿模式￿(￿0******￿)￿的长度是0，记作￿￿(￿0******￿)￿=￿0￿；3遗传算法第三章模式理论￿￿￿￿￿•￿￿一般地，有式子￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿(s)＝b￿–￿a￿￿￿￿￿￿￿￿￿￿￿￿式中￿￿￿￿￿b—模式s￿中最后一个明确字符的位置;￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿a—模式s￿中最前一个明确字符的位置。

￿￿￿￿￿￿•￿￿模式的长度代表该模式在今后遗传操作模式的长度代表该模式在今后遗传操作( (交叉、变异交叉、变异) )中被破坏的可能性：中被破坏的可能性：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿模式长度越短，被破坏的可能性越小，长度为模式长度越短，被破坏的可能性越小，长度为0 0的模式最难被破坏的模式最难被破坏3.1.3￿￿3.1.3￿￿编码字符串的模式数目编码字符串的模式数目￿￿￿￿￿(1)￿￿(1)￿￿模式总数模式总数￿ ￿￿￿￿￿￿￿￿•￿￿￿二进制字符串￿￿￿￿￿￿￿￿￿￿￿￿￿假设字符的长度为l，字符串中每一个字符可取(￿0,￿1,￿*￿)￿三个符号中任意￿￿￿￿￿￿￿￿￿一个，可能组成的模式数目最多为：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿3￿￿3￿￿3￿￿…￿￿3￿=￿(2+1)(2+1)l l￿ ￿￿￿￿￿￿￿￿•￿一般情况下，￿￿￿￿￿￿￿￿￿￿￿￿￿假设字符串长度为l，字符的取值为￿k￿种，字符串组成的模式数目￿n1￿最多￿￿￿￿￿￿￿￿￿￿￿￿￿￿为：￿￿￿￿￿￿￿￿￿n1=(k+1)l4遗传算法第三章模式理论(2)￿￿(2)￿￿编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数￿￿￿￿￿•￿￿二进制字符串￿￿￿￿￿￿￿￿￿￿￿对于长度为l的某二进制字符串，它含有的模式总数最多为：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿2￿￿2￿￿2￿￿…￿￿2￿=￿2 2l l￿ ￿￿￿￿￿￿￿￿￿￿￿￿[注意]￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿这个数目是指字符串已确定为0或1，每个字符只能在已定值￿(0/1)或￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿*￿中选取；￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿前面所述的￿n1￿指字符串未确定，每个字符可在{0,￿1,￿*￿}三者中选取。

￿￿￿￿￿￿￿￿￿•￿￿一般情况下￿￿￿￿￿￿￿￿￿￿￿长度为l、取值有￿k￿种的某一字符串，它可能含有的模式数目最多为：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿n2￿=￿kl￿(3)￿￿(3)￿￿群体所含模式数群体所含模式数￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿在长度为l，规模为M的二进制编码字符串群体中，一般包含有2l￿~￿M￿·￿2l个￿￿￿￿￿￿￿￿￿模式5遗传算法第三章模式理论3.2￿￿3.2￿￿模式定理模式定理￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看￿￿￿￿￿作是对模式的一种运算对基本遗传算法(GA)而言，也就是某一模式s￿的各个￿￿￿￿￿样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式3.2.1￿￿3.2.1￿￿复制时的模式数目复制时的模式数目￿￿￿￿￿￿￿￿￿￿￿这里以比例选择算子为例研究￿￿￿￿￿￿￿￿[ [公式推导公式推导] ]￿￿￿￿￿￿￿(1)￿假设在第t次迭代时,￿群体P(t)中有M个个体,￿其中m个个体属于模式s,￿记作m(s,t)￿￿￿￿￿￿￿(2)￿个体￿ai￿按其适应度￿fi￿的大小进行复制。

￿￿￿￿￿￿￿￿￿￿￿￿从统计意义讲，个体ai被复制的概率pi是：(3) 因此复制后在下一代群体因此复制后在下一代群体 P(t+1)中，群体内属于模式中，群体内属于模式s（或称与模式（或称与模式s匹配）匹配） 的个体数目的个体数目 m(s,t+1) 可用平均适应度按下式近似计算：可用平均适应度按下式近似计算：f(s)式中式中 ——第第t代属于模式代属于模式 s 的所有的所有 个体之平均适应度；个体之平均适应度； M——群体中拥有的个体数目群体中拥有的个体数目f(s)6遗传算法第三章模式理论 (4) 设第设第t代所有个体代所有个体(不论它属于何种模式不论它属于何种模式)的平均适应度是的平均适应度是 , 有等式有等式:f(5) 综合上述两式，复制后模式综合上述两式，复制后模式s所拥有的个体数目可按下式近似计算：所拥有的个体数目可按下式近似计算：fff(s)[ [结论结论] ]￿￿￿￿￿￿•￿ •￿上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式s￿ s￿的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿适应度适应度￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿与群体的平均适应度与群体的平均适应度￿￿￿￿￿￿￿￿￿￿￿￿之比之比; ;￿￿￿￿￿￿￿￿￿￿￿￿•￿ •￿只有当模式只有当模式s￿ s￿的平均值的平均值￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿大于群钵的平均值大于群钵的平均值￿￿￿￿￿￿￿￿￿￿￿￿时，时，s s模式的个体数目才模式的个体数目才￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿能增长。

否则，能增长否则，s s模式的数目要减小模式的数目要减小￿￿￿￿￿￿￿￿￿￿￿￿•￿模式s￿的这种增减规律，正好符合复制操作的“优胜劣汰”原则，这也说明模￿￿￿￿￿￿￿￿￿式的确能描述编码字符串的内部特征f(s)ff(s)f①①7遗传算法第三章模式理论[ [进一步推导进一步推导] ]￿￿￿￿(1)￿￿假设某一模式s￿在复制过程中其平均适应度￿￿￿￿￿￿￿￿￿比群体的平均适应度￿￿￿￿￿高￿￿￿￿￿￿￿￿￿￿出一个定值￿￿￿￿￿￿￿￿￿￿￿，其中c￿为常数，则上式改写为：ff(s) c f[ [结论结论] ] 从数学上讲，上式是一个指数方程，它说明模式从数学上讲，上式是一个指数方程，它说明模式s￿ s￿所拥有的个体数目所拥有的个体数目 在复制过程中以指数形式增加或减小在复制过程中以指数形式增加或减小 f c ff += m( s, t ) · (1+c ) (2) 从第一代开始，若模式从第一代开始，若模式s 以常数以常数c 繁殖到第繁殖到第 t+1代，其个体数目为：代，其个体数目为： m( s, t+1 ) = m( s, 1 ) · (1+c )t8遗传算法第三章模式理论3.2.2￿￿3.2.2￿￿交叉时的模式数目交叉时的模式数目￿￿￿￿￿￿￿￿￿￿￿这里以单点交叉算子为例研究。

￿￿￿￿[ [举例举例]￿￿]￿￿￿￿￿￿￿￿(1)￿￿有两个模式￿￿￿s1:￿￿“￿*￿1￿*￿*￿*￿*￿0￿”￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿s2:￿￿“￿*￿*￿*￿1￿0￿*￿*￿”￿￿￿￿￿￿￿￿￿￿￿￿￿它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表示）￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿a:￿￿“￿0￿1￿1￿1￿0￿0￿0￿”￿￿￿￿￿￿(2)￿￿选择个体a￿进行交叉￿￿￿￿￿￿(3)￿￿随机选择交叉点￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿s1:￿￿“￿￿*￿￿1￿￿*￿￿*￿￿*￿￿*￿￿0￿￿”￿￿￿￿￿￿￿￿交叉点选在第￿2￿~￿6￿之间都可能破坏模式s1;￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿s2:￿￿“￿￿*￿￿*￿￿*￿￿1￿￿0￿￿*￿￿*￿￿”￿￿￿￿￿￿￿￿交叉点在￿第￿4￿~￿5之间才破坏s2￿￿[ [公式推导公式推导] ]￿￿￿￿￿￿￿(1)￿￿交换发生在模式s￿的定义长度￿(s)范围内，即模式被破坏的概率是：例：例： s1 被破坏的概率为：被破坏的概率为：5/6 s2 被破坏的概率为：被破坏的概率为：1/6 l9遗传算法第三章模式理论 (2) 模式不被破坏，存活下来的概率为：模式不被破坏，存活下来的概率为： (3) 若交叉概率为若交叉概率为pc，则模式存活下来的概率为：，则模式存活下来的概率为：[ [结论结论] ]￿￿￿￿￿模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏。

模式的定义长度对模式的存亡影响很大，模式的长度越大，越容易被破坏②② (4) 经复制、交叉操作后，模式经复制、交叉操作后，模式s在下一在下一 代群体中所拥有的个体数目为：代群体中所拥有的个体数目为： l-1 1l-1 1ff(s)l-1 110遗传算法第三章模式理论3.2.3￿￿3.2.3￿￿变异时的模式数目变异时的模式数目￿￿￿￿￿￿￿￿￿这里以基本位变异算子为例研究￿￿￿￿￿￿￿[ [公式推导公式推导] ]￿￿￿￿￿￿￿￿￿￿￿￿￿￿(1)￿￿变异时个体的每一位发生变化的概率是变异概率pm，也就是说，每一位存￿￿￿￿￿￿￿￿￿￿￿￿￿￿活的概率是(1-￿pm)根据模式的阶o(s)，可知模式中有明确含意的字符有o(s)￿￿￿￿￿￿￿￿￿￿￿￿￿个，于是模式s￿存活的概率是：￿￿￿￿ (2) 通常通常 pm<<1，上式用泰勒级数展开取一次项，可近似表达为：，上式用泰勒级数展开取一次项，可近似表达为： ps   1 – pm · o(s) [ [结论结论]￿ ]￿￿￿￿￿￿￿￿￿上式说明，模式的阶次上式说明，模式的阶次o(s)o(s)越低，模式越低，模式s￿ s￿存活的可能性越大，反之亦然。

存活的可能性越大，反之亦然￿￿￿￿￿③③11遗传算法第三章模式理论3.2.4￿3.2.4￿模式定理模式定理￿￿￿￿￿￿￿￿￿综合式①、②、③￿可以得出遗传算法经复制、交叉、变异操作后，模式s在￿￿￿￿￿下一代群体中所拥有的个体数目，如下式所示：④④￿[ [模式定理模式定理] ]￿￿￿适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿法的迭代过程中将按指数规律增长法的迭代过程中将按指数规律增长￿￿￿￿￿￿￿￿￿￿模式定理深刻地阐明了遗传算法中发生“优胜劣汰”的原因在遗传过程中￿￿￿￿￿￿￿￿能存活的模式都是定义长度短、阶次低、平均适应度高于群体平均适应度的￿￿￿￿￿￿￿￿优良模式遗传算法正是利用这些优良模式逐步进化到最优解ff(s)l-1 112遗传算法第三章模式理论3.2.5￿￿3.2.5￿￿模式定理示例模式定理示例￿￿￿￿￿￿￿￿￿￿￿例：￿求￿￿￿max￿￿f(x)=x2￿￿￿￿￿￿x￿{0,31}个个 体体 变变 化化叉叉叉叉13遗传算法第三章模式理论S1S2S3叉叉14遗传算法第三章模式理论3.3￿3.3￿建筑块假说建筑块假说3.3.1￿￿3.3.1￿￿模式对搜索空间的划分模式对搜索空间的划分￿￿￿[ [举例举例] ]￿￿￿￿￿￿￿￿￿￿￿￿￿以￿￿￿max￿￿f(x)=x2￿￿￿￿￿￿x￿{0,31}￿￿为例，￿￿￿￿￿￿￿￿￿图中：横坐标表示x，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿纵坐标代表适应度f(x)=x2，用千分数表示，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿弧线表示适应度曲线，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿网点区代表所有符合此模式的个体集合。

￿￿￿￿￿￿￿￿￿￿￿￿模式1：1****15遗传算法第三章模式理论模式模式2：：10***模式模式3：：**1*116遗传算法第三章模式理论[ [结论结论] ]￿￿￿￿￿￿￿￿￿模式能够划分搜索空间，而且模式的阶越高，对搜索空间的划分越细致模式能够划分搜索空间，而且模式的阶越高，对搜索空间的划分越细致3.3.2￿￿3.3.2￿￿分配搜索次数分配搜索次数￿￿￿￿￿￿模式定理告诉我们：￿￿￿￿￿￿￿￿GAGA根据模式的适应度、长度和阶次为模式分配搜索次数根据模式的适应度、长度和阶次为模式分配搜索次数￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿为那些适应度较高，长度较短，阶次较低的模式分配的搜索次数按指数率增长；为那些适应度较高，长度较短，阶次较低的模式分配的搜索次数按指数率增长；￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿为那些适应度较低，长度较长，阶次较高的模式分配的搜索次数按指数率衰减为那些适应度较低，长度较长，阶次较高的模式分配的搜索次数按指数率衰减3.3.3￿3.3.3￿建筑块假说建筑块假说￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿前面我们已经介绍了GA如何划分搜索空间和在各个子空间中分配搜索次数，￿￿￿￿￿那么GA如何利用搜索过程中的积累信息加快搜索速度呢？￿￿￿￿￿￿￿￿￿Holland￿和￿Goldberg在模式定理的基础上提出了“建筑块假说”。

￿￿￿￿￿￿￿￿￿17遗传算法第三章模式理论[￿ [￿建筑块（或称积木块）建筑块（或称积木块）(Buliding￿Block)](Buliding￿Block)]￿￿￿￿￿￿￿￿￿￿￿￿——短定义长度、低阶、高适应度的模式￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜￿￿￿￿￿￿￿索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像￿￿￿￿￿￿搭积木一样、将它们拼接在一起，从而逐渐地构造出适应度越来越高的个￿￿￿￿￿￿体编码串￿[￿ [￿建筑块假说建筑块假说] ]￿￿￿￿￿￿￿￿￿￿￿￿￿GA在搜索过程中将不同的“建筑块”通过遗传算子（如交叉算子）的作￿￿￿￿￿￿￿￿￿￿用结合在一起，形成适应度更高的新模式这样将大大缩小GA的搜索范￿￿￿￿￿￿￿￿￿￿围18遗传算法第三章模式理论[ [建筑块混合建筑块混合] ]￿￿￿￿——建筑块通过遗传算子的作用集合在一起的过程称为“建筑块混合”￿￿￿￿￿￿当那些构成最优点（或近似最优点）的“建筑块”结合在一起时，就得到了最优点[ [建筑块混合的例子建筑块混合的例子] ]￿￿￿￿￿￿￿•￿问题的最优用三个建筑块￿BB1,￿BB2,￿BB3￿表示；￿￿￿￿￿￿￿•￿￿群体中有8个个体。

￿￿￿￿￿￿￿•￿￿初始群体中个体1，个体2包含建筑块BB1￿，个体3包含BB3￿,个体5包含BB2￿P1P2P3P4P5P6P7P8BB1BB2BB1BB3P1P2P3P4P5P6P7P8BB2BB3BB1BB3BB1BB2BB1BB1BB2BB3P1P2P3P4P5P6P7P8BB2BB3BB1BB3BB1BB2BB1BB1BB2BB3BB2BB3初始群体初始群体第二代群体第二代群体第三代群体第三代群体说明：说明：第三代群体中第三代群体中出现了一个包出现了一个包含三个含三个“建筑块建筑块”的个体的个体3个体个体3就代表这就代表这个问题的最优解个问题的最优解19遗传算法第三章模式理论3.4￿￿3.4￿￿隐含并行性（内在并行性）隐含并行性（内在并行性）￿￿￿￿￿￿隐含并行性（Implicit￿Parallelism）是模式理论的另一个重要内容￿￿￿￿￿￿￿￿￿￿￿￿这一机理说明，在遗传算法中尽管每一代只处理M个个体，但实际上却是处理￿￿￿￿￿￿￿了M3以上的模式￿￿￿￿[ [隐含并行性定理隐含并行性定理] ]￿￿￿￿￿￿￿￿￿￿￿￿￿设￿￿(￿0,￿1￿)￿是一个很小的数，模式存活的最小长度￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿,￿￿￿￿￿￿￿￿￿群体规模为￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿,￿￿则GA在一次迭代中所处理的“存活率”大于￿(1-￿ )￿的模式￿￿￿￿￿￿￿￿￿数约为O(M3)￿。

其中￿￿￿￿￿￿￿表示上取值￿[ [公式推导公式推导] ]￿￿￿￿￿￿￿以二进制编码为例在长度为l，规模为M的群体中，包含了￿2l￿~￿M·2l￿个不￿￿￿￿￿同的模式，随着进化过程的进行，这些模式中一些定义长度较长的模式被破￿￿￿￿坏掉，而另一些定义长度较短的模式却能够生存下来20遗传算法第三章模式理论￿(1)￿￿(1)￿￿模式存活的最小长度模式存活的最小长度￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿从模式定理中可以看出，模式在交叉和变异时可能遭破坏￿￿￿￿￿￿￿￿•￿由于变异概率很小，在此只考虑交叉的破坏（此式也可兼顾变异的破坏因素)￿￿￿￿￿￿￿￿￿￿￿￿￿模式被破坏的概率为：l• 为保证模式的存活率为保证模式的存活率 , 令令pd<  ，即：，即：• 根据模式定义长度的定义，模式不被破坏的最小长度根据模式定义长度的定义，模式不被破坏的最小长度 是：是：• 带入上式得：带入上式得：21遗传算法第三章模式理论(2)￿￿(2)￿￿个体编码串中拥有长度为个体编码串中拥有长度为￿￿￿￿￿￿￿￿￿￿的模式数目的模式数目￿￿￿￿￿￿￿￿[示例]￿￿￿假设下述个体编码字符串的长度￿l＝10，￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿1￿0￿1￿1￿1￿0￿0￿0￿1￿0￿￿￿￿￿￿￿￿￿￿￿￿￿设模式s￿的存活长度￿￿￿￿＝5。

￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿Ⅰ.￿将它放置在个体字符串的最左侧，则有：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿1￿0￿1￿1￿1￿0￿0￿0￿1￿0￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿写成模式的形式，上述字符串变为：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿% % % % 1 * * * * *￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿•￿方框中%可在{￿0,￿1,￿*￿}三者中任取一个也就是说，％可为固定值￿(￿0/1￿)￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿或不固定值(*)两种情况￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿•￿方框内的1表示有一个确定的模式，也可以选方框内的其他固定值表示￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿这时，可以组成的模式个数是：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿2￿￿2￿￿…￿￿2￿=￿￿￿￿￿￿￿￿￿￿￿￿￿￿Ⅱ.￿将上述方框右移一位￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿其模式表达为：￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿1￿0￿1￿1￿1￿0￿0￿0￿1￿0￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿*￿￿% % % % 0 * * * *￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿又可以组成￿￿￿￿￿￿￿￿￿￿￿￿￿￿￿个模式。

22遗传算法第三章模式理论 Ⅲ. 上述方框可发生在上述方框可发生在6个不同的位置，即发生次数为：个不同的位置，即发生次数为： ，， 于是，长度为于是，长度为 的个体可组成存活长度为的个体可组成存活长度为 的模式数目是：的模式数目是：(3)￿￿(3)￿￿群体中的模式数目群体中的模式数目￿￿￿￿￿￿￿￿当群体由M个个体组成时，可能组成的长度为￿￿￿￿￿￿的模式数目为： • 若若M较大，则对一些低阶的模式肯定会有一些重复为排除这些重复部分，可较大，则对一些低阶的模式肯定会有一些重复为排除这些重复部分，可 取群体的规模数为取群体的规模数为M = 这时，模式阶高于或等于这时，模式阶高于或等于 的模式最多只的模式最多只 重复计数一次重复计数一次 • 另另—方面，由于遗传操作都是利用均匀随机数，模式数目服从二项分布，即模方面，由于遗传操作都是利用均匀随机数，模式数目服从二项分布，即模 式中有一半的阶次高于式中有一半的阶次高于 ，另一半小于，另一半小于 。

于是，计算时模式数目应于是，计算时模式数目应 取上式的取上式的 1/2 /2/2/223遗传算法第三章模式理论综合上述各方面，可能存活的模式数目综合上述各方面，可能存活的模式数目ns为：为：即有：即有： ns = cM3 = O(M3)[ [结论结论] ]￿￿￿￿￿￿￿￿￿￿￿￿￿遗传算法所处理的有效模式总数约与群体规模遗传算法所处理的有效模式总数约与群体规模MM的立方成正比也就是说，的立方成正比也就是说，￿￿￿￿￿￿￿￿￿￿虽然在进化过程的每一代中只处理了虽然在进化过程的每一代中只处理了MM个个体，但实际上我们并行处理了与个个体，但实际上我们并行处理了与MM￿￿￿￿￿￿￿￿￿￿的立方成正比例的模式数的立方成正比例的模式数￿￿￿￿￿￿￿￿￿￿￿因此，遗传算法实际上是一种并行算法，隐藏在个体的背后，故称隐含并行￿￿￿￿￿￿算法正是由于这种隐含并行性，遗传算法的搜索效率很高24遗传算法第三章模式理论此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！25遗传算法第三章模式理论。