遗传算法第三章模式理论优秀PPT.ppt

第三章第三章 模式理论模式理论 指导遗传算法的基本理论，是指导遗传算法的基本理论，是J.H.Holland教授创立的教授创立的模式理论模式理论。该理论揭示。该理论揭示 了遗传算法的基本机理。了遗传算法的基本机理。3.1 3.1 基本概念基本概念基本概念基本概念 3.1.1 3.1.1 问题的引出问题的引出问题的引出问题的引出 例：例：求求 max f(x)=x2 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 种，字符串组成的模式数目种，字符串组成的模式数目 n1 最多最多 为：为：n1=(k+1)l(2)(2)编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数编码字符串（一个个体编码串）所含模式总数 二进制字符串二进制字符串二进制字符串二进制字符串 对于长度为对于长度为对于长度为对于长度为l l的某二进制字符串，它含有的模式总数最多为：的某二进制字符串，它含有的模式总数最多为：的某二进制字符串，它含有的模式总数最多为：的某二进制字符串，它含有的模式总数最多为：2 2 2 2 2 2 2=2l 2=2l 留意留意留意留意 这个数目是指字符串已确定为这个数目是指字符串已确定为这个数目是指字符串已确定为这个数目是指字符串已确定为0 0或或或或1 1，每个字符只能在已定值，每个字符只能在已定值，每个字符只能在已定值，每个字符只能在已定值(0/1)(0/1)或或或或 *中选取；中选取；中选取；中选取；前面所述的前面所述的前面所述的前面所述的 n1 n1 指字符串未确定，每个字符可在指字符串未确定，每个字符可在指字符串未确定，每个字符可在指字符串未确定，每个字符可在0,1,*0,1,*三者中选取。三者中选取。三者中选取。三者中选取。一般状况下一般状况下一般状况下一般状况下 长度为长度为长度为长度为l l、取值有、取值有、取值有、取值有 k k 种的某一字符串，它可能含有的模式数目最多为：种的某一字符串，它可能含有的模式数目最多为：种的某一字符串，它可能含有的模式数目最多为：种的某一字符串，它可能含有的模式数目最多为：n2=kl n2=kl(3)(3)群体所含模式数群体所含模式数群体所含模式数群体所含模式数 在长度为在长度为在长度为在长度为l l，规模为，规模为，规模为，规模为MM的二进制编码字符串群体中，一般包含有的二进制编码字符串群体中，一般包含有的二进制编码字符串群体中，一般包含有的二进制编码字符串群体中，一般包含有2l M 2l2l M 2l个个个个 模式。模式。模式。模式。3.2 3.2 模式定理模式定理模式定理模式定理 由前面的叙述我们可以知道，在引入模式的概念之后，遗由前面的叙述我们可以知道，在引入模式的概念之后，遗由前面的叙述我们可以知道，在引入模式的概念之后，遗由前面的叙述我们可以知道，在引入模式的概念之后，遗传算法的实质可看传算法的实质可看传算法的实质可看传算法的实质可看 作是对模式的一种运算。对基本遗传算法作是对模式的一种运算。对基本遗传算法作是对模式的一种运算。对基本遗传算法作是对模式的一种运算。对基本遗传算法(GA)(GA)而言，也就是而言，也就是而言，也就是而言，也就是某一模式某一模式某一模式某一模式s s 的各个的各个的各个的各个 样本经过选择运算、交义运算、变异运算之后，得到一些新样本经过选择运算、交义运算、变异运算之后，得到一些新样本经过选择运算、交义运算、变异运算之后，得到一些新样本经过选择运算、交义运算、变异运算之后，得到一些新的样本和新的模式。的样本和新的模式。的样本和新的模式。的样本和新的模式。3.2.1 3.2.1 复制时的模式数目复制时的模式数目复制时的模式数目复制时的模式数目 这里以比例选择算子为例探讨。这里以比例选择算子为例探讨。这里以比例选择算子为例探讨。这里以比例选择算子为例探讨。公式推导公式推导公式推导公式推导 (1)(1)假设在第假设在第假设在第假设在第t t次迭代时次迭代时次迭代时次迭代时,群体群体群体群体P(t)P(t)中有中有中有中有MM个个体个个体个个体个个体,其中其中其中其中mm个个个个个个个个体属于模式体属于模式体属于模式体属于模式s,s,记作记作记作记作m(s,t)m(s,t)。(2)(2)个体个体个体个体 ai ai 按其适应度按其适应度按其适应度按其适应度 fi fi 的大小进行复制。的大小进行复制。的大小进行复制。的大小进行复制。从统计意义讲，个体从统计意义讲，个体从统计意义讲，个体从统计意义讲，个体aiai被复制的概率被复制的概率被复制的概率被复制的概率pipi是：是：是：是：(3)因此复制后在下一代群体因此复制后在下一代群体 P(t+1)中，群体内属于模式中，群体内属于模式s（或称与模式（或称与模式s匹配）匹配）的个体数目的个体数目 m(s,t+1)可用平均适应度按下式近似计算：可用平均适应度按下式近似计算：f(s)式中式中 第第t代属于模式代属于模式 s 的所有的所有 个体之平均适应度；个体之平均适应度；M群体中拥有的个体数目。群体中拥有的个体数目。f(s)(4)设第设第t代全部个体代全部个体(不论它属于何种模式不论它属于何种模式)的平均适应度是的平均适应度是 ,有等式有等式:f(5)综合上述两式，复制后模式综合上述两式，复制后模式s所拥有的个体数目可按下式近似计算：所拥有的个体数目可按下式近似计算：fff(s)结论结论结论结论 上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式上式说明复制后下一代群体中属于模式s s 的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均的个体数目，取决于该模式的平均 适应度适应度适应度适应度 与群体的平均适应度与群体的平均适应度与群体的平均适应度与群体的平均适应度 之比之比之比之比;只有当模式只有当模式只有当模式只有当模式s s 的平均值的平均值的平均值的平均值 大于群钵的平均值大于群钵的平均值大于群钵的平均值大于群钵的平均值 时，时，时，时，s s模式的个体数目才模式的个体数目才模式的个体数目才模式的个体数目才 能增长。否则，能增长。否则，能增长。否则，能增长。否则，s s模式的数目要减小。模式的数目要减小。模式的数目要减小。模式的数目要减小。模式模式s 的这种增减规律，正好符合复制操作的的这种增减规律，正好符合复制操作的“优胜劣汰优胜劣汰”原则，这也说明原则，这也说明模模 式的确能描述编码字符串的内部特征。式的确能描述编码字符串的内部特征。f(s)ff(s)f 进一步推导进一步推导进一步推导进一步推导 (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)t3.2.2 3.2.2 交叉时的模式数目交叉时的模式数目交叉时的模式数目交叉时的模式数目 这里以单点交叉算子为例探讨。这里以单点交叉算子为例探讨。这里以单点交叉算子为例探讨。这里以单点交叉算子为例探讨。举例举例举例举例 (1)(1)有两个模式有两个模式有两个模式有两个模式 s1:“*1*0”s1:“*1*0”s2:“*1 0*”s2:“*1 0*”它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表它们有一个共同的可匹配的个体（可与模式匹配的个体称为模式的表示）示）示）示）a:“0 1 1 1 0 0 0”a:“0 1 1 1 0 0 0”(2)(2)选择个体选择个体选择个体选择个体a a 进行交叉进行交叉进行交叉进行交叉 (3)(3)随机选择交叉点随机选择交叉点随机选择交叉点随机选择交叉点 s1:“*1 *0 ”s1:“*1 *0 ”交叉点选在第交叉点选在第交叉点选在第交叉点选在第 2 6 2 6 之间都可能破坏模式之间都可能破坏模式之间都可能破坏模式之间都可能破坏模式s1;s1;s2:“*1 0 *”s2:“*1 0 *”交叉点在交叉点在交叉点在交叉点在 第第第第 4 5 4 5之间才破坏之间才破坏之间才破坏之间才破坏s2s2。公式推导公式推导公式推导公式推导 (1)(1)交换发生在模式交换发生在模式交换发生在模式交换发生在模式s s 的定义长度的定义长度的定义长度的定义长度 (s)(s)范围内，即模式被破坏的概率是：范围内，即模式被破坏的概率是：范围内，即模式被破坏的概率是：范围内，即模式被破坏的概率是：例：例：s1 被破坏的概率为：被破坏的概率为：5/6 s2 被破坏的概率为：被破坏的概率为：1/6 l(2)模式不被破坏，存活下来的概率为：模式不被破坏，存活下来的概率为：(3)若交叉概率为若交叉概率为pc，则模式存活下来的概率为：，则模式存活下来的概率为：结论结论结论结论 模式的定义长度对模式的存亡影响很大，模式的长度越大，越简洁被破坏。模式的定义长度对模式的存亡影响很大，模式的长度越大，越简洁被破坏。模式的定义长度对模式的存亡影响很大，模式的长度越大，越简洁被破坏。模式的定义长度对模式的存亡影响很大，模式的长度越大，越简洁被破坏。(4)经复制、交叉操作后，模式经复制、交叉操作后，模式s在下一在下一 代群体中所拥有的个体数目为：代群体中所拥有的个体数目为：l-1 1l-1 1ff(s)l-1 13.2.3 3.2.3 变异时的模式数目变异时的模式数目变异时的模式数目变异时的模式数目 这里以基本位变异算子为例探讨。这里以基本位变异算子为例探讨。这里以基本位变异算子为例探讨。这里以基本位变异算子为例探讨。公式推导公式推导公式推导公式推导 (1)(1)变异时个体的每一位发生变更的概率是变异概率变异时个体的每一位发生变更的概率是变异概率变异时个体的每一位发生变更的概率是变异概率变异时个体的每一位发生变更的概率是变异概率pmpm，也就是说，每，也就是说，每，也就是说，每，也就是说，每一位存一位存一位存一位存 活的概率是活的概率是活的概率是活的概率是(1-pm)(1-pm)。依据模式的阶。依据模式的阶。依据模式的阶。依据模式的阶o(s)o(s)，可知模式中有明确含意的，可知模式中有明确含意的，可知模式中有明确含意的，可知模式中有明确含意的字符有字符有字符有字符有o(s)o(s)个，于是模式个，于是模式个，于是模式个，于是模式s s 存活的概率是：存活的概率是：存活的概率是：存活的概率是：(2)通常通常 pm1，上式用泰勒级数绽开取一次项，可近似表达为：，上式用泰勒级数绽开取一次项，可近似表达为：ps 1 pm o(s)结论结论结论结论 上式说明，模式的阶次上式说明，模式的阶次上式说明，模式的阶次上式说明，模式的阶次o(s)o(s)越低，模式越低，模式越低，模式越低，模式s s 存活的可能性越大，反之亦然。存活的可能性越大，反之亦然。存活的可能性越大，反之亦然。存活的可能性越大，反之亦然。3.2.4 3.2.4 模式定理模式定理模式定理模式定理 综合式综合式、可以得出遗传算法经复制、交叉、变异操作后，模式可以得出遗传算法经复制、交叉、变异操作后，模式s在在 下一代群体中所拥有的个体数目，如下式所示：下一代群体中所拥有的个体数目，如下式所示：模式定理模式定理 适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算适应度高于群体平均适应度的，长度较短，低阶的模式在遗传算 法的迭代过程中将按指数规律增长。法的迭代过程中将按指数规律增长。模式定理深刻地阐明白遗传算法中发生模式定理深刻地阐明白遗传算法中发生“优胜劣汰优胜劣汰”的缘由。在遗传过程中的缘由。在遗传过程中 能存活的模式都是定义长度短、阶次低、平均适应度高于群体平均适应度的能存活的模式都是定义长度短、阶次低、平均适应度高于群体平均适应度的 优良模式。遗传算法正是利用这些优良模式逐步进化到最优解。优良模式。遗传算法正是利用这些优良模式逐步进化到最优解。ff(s)l-1 13.2.5 3.2.5 模式定理示例模式定理示例模式定理示例模式定理示例 例：例：求求 max f(x)=x2 x 0,31个个 体体 变变 化化叉叉叉叉S1S2S3叉叉3.3 3.3 建筑块假说建筑块假说建筑块假说建筑块假说3.3.1 3.3.1 模式对搜寻空间的划分模式对搜寻空间的划分模式对搜寻空间的划分模式对搜寻空间的划分 举例举例举例举例 以以以以 max f(x)=x2 x max f(x)=x2 x 0,31 0,31 为例，为例，为例，为例，图中：横坐标表示图中：横坐标表示图中：横坐标表示图中：横坐标表示x x，纵坐标代表适应度纵坐标代表适应度纵坐标代表适应度纵坐标代表适应度f(x)=x2f(x)=x2，用千分数表示，用千分数表示，用千分数表示，用千分数表示，弧线表示适应度曲线，弧线表示适应度曲线，弧线表示适应度曲线，弧线表示适应度曲线，网点区代表全部符合此模式的个体集合。网点区代表全部符合此模式的个体集合。网点区代表全部符合此模式的个体集合。网点区代表全部符合此模式的个体集合。模式模式模式模式1 1：1*1*模式模式2：10*模式模式3：*1*1 结论结论结论结论 模式能够划分搜寻空间，而且模式的阶越高，对搜寻空间的划分越细致。模式能够划分搜寻空间，而且模式的阶越高，对搜寻空间的划分越细致。模式能够划分搜寻空间，而且模式的阶越高，对搜寻空间的划分越细致。模式能够划分搜寻空间，而且模式的阶越高，对搜寻空间的划分越细致。3.3.2 3.3.2 安排搜寻次数安排搜寻次数安排搜寻次数安排搜寻次数 模式定理告知我们：模式定理告知我们：模式定理告知我们：模式定理告知我们：GA GA依据模式的适应度、长度和阶次为模式安排搜寻次数。依据模式的适应度、长度和阶次为模式安排搜寻次数。依据模式的适应度、长度和阶次为模式安排搜寻次数。依据模式的适应度、长度和阶次为模式安排搜寻次数。为那些适应度较高，长度较短，阶次较低的模式安排的搜寻次数按指数率增长；为那些适应度较高，长度较短，阶次较低的模式安排的搜寻次数按指数率增长；为那些适应度较高，长度较短，阶次较低的模式安排的搜寻次数按指数率增长；为那些适应度较高，长度较短，阶次较低的模式安排的搜寻次数按指数率增长；为那些适应度较低，长度较长，阶次较高的模式安排的搜寻次数按指数率衰减。为那些适应度较低，长度较长，阶次较高的模式安排的搜寻次数按指数率衰减。为那些适应度较低，长度较长，阶次较高的模式安排的搜寻次数按指数率衰减。为那些适应度较低，长度较长，阶次较高的模式安排的搜寻次数按指数率衰减。3.3.3 3.3.3 建筑块假说建筑块假说建筑块假说建筑块假说 前面我们已经介绍了前面我们已经介绍了前面我们已经介绍了前面我们已经介绍了GAGA如何划分搜寻空间和在各个子空间中安排搜寻次数，如何划分搜寻空间和在各个子空间中安排搜寻次数，如何划分搜寻空间和在各个子空间中安排搜寻次数，如何划分搜寻空间和在各个子空间中安排搜寻次数，那么那么那么那么GAGA如何利用搜寻过程中的积累信息加快搜寻速度呢？如何利用搜寻过程中的积累信息加快搜寻速度呢？如何利用搜寻过程中的积累信息加快搜寻速度呢？如何利用搜寻过程中的积累信息加快搜寻速度呢？Holland Holland 和和和和 Goldberg Goldberg在模式定理的基础上提出了在模式定理的基础上提出了在模式定理的基础上提出了在模式定理的基础上提出了“建筑块假说建筑块假说建筑块假说建筑块假说”。建筑块（或称积木块）建筑块（或称积木块）建筑块（或称积木块）建筑块（或称积木块）(Buliding Block)(Buliding Block)短定义长度、低阶、高适应度的模式。短定义长度、低阶、高适应度的模式。短定义长度、低阶、高适应度的模式。短定义长度、低阶、高适应度的模式。之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜之所以称之为建筑块（积木块），是由于遗传算法的求解过程并不是在搜 索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像 搭积木一样、将它们拼接在一起，从而渐渐地构造出适应度越来越高的个搭积木一样、将它们拼接在一起，从而渐渐地构造出适应度越来越高的个搭积木一样、将它们拼接在一起，从而渐渐地构造出适应度越来越高的个搭积木一样、将它们拼接在一起，从而渐渐地构造出适应度越来越高的个 体编码串。体编码串。体编码串。体编码串。建筑块假说建筑块假说建筑块假说建筑块假说 GA GA在搜寻过程中将不同的在搜寻过程中将不同的在搜寻过程中将不同的在搜寻过程中将不同的“建筑块建筑块建筑块建筑块”通过遗传算子（如交叉算子）的通过遗传算子（如交叉算子）的通过遗传算子（如交叉算子）的通过遗传算子（如交叉算子）的作作作作 用结合在一起，形成适应度更高的新模式。这样将大大缩小用结合在一起，形成适应度更高的新模式。这样将大大缩小用结合在一起，形成适应度更高的新模式。这样将大大缩小用结合在一起，形成适应度更高的新模式。这样将大大缩小GAGA的搜寻范的搜寻范的搜寻范的搜寻范 围。围。围。围。建筑块混合建筑块混合建筑块混合建筑块混合 建筑块通过遗传算子的作用集合在一起的过程称为建筑块通过遗传算子的作用集合在一起的过程称为“建筑块混合建筑块混合”。当那些构成最优点（或近似最优点）的当那些构成最优点（或近似最优点）的“建筑块建筑块”结合在一起时，就得到了最优结合在一起时，就得到了最优点。点。建筑块混合的例子建筑块混合的例子建筑块混合的例子建筑块混合的例子 问题的最优用三个建筑块问题的最优用三个建筑块 BB1,BB2,BB3 表示；表示；群体中有群体中有8个个体。个个体。初始群体中个体初始群体中个体1，个体，个体2包含建筑块包含建筑块BB1，个体，个体3包含包含BB3,个体个体5包含包含BB2。P1P2P3P4P5P6P7P8BB1BB2BB1BB3P1P2P3P4P5P6P7P8BB2BB3BB1BB3BB1BB2BB1BB1BB2BB3P1P2P3P4P5P6P7P8BB2BB3BB1BB3BB1BB2BB1BB1BB2BB3BB2BB3初始群体初始群体其次代群体其次代群体第三代群体第三代群体说明：说明：第三代群体中第三代群体中出现了一个包出现了一个包含三个含三个“建筑块建筑块”的个体的个体3。个体个体3就代表这就代表这个问题的最优解。个问题的最优解。3.4 3.4 隐含并行性（内在并行性）隐含并行性（内在并行性）隐含并行性（内在并行性）隐含并行性（内在并行性）隐含并行性（隐含并行性（隐含并行性（隐含并行性（Implicit ParallelismImplicit Parallelism）是模式理论的另一个重要）是模式理论的另一个重要）是模式理论的另一个重要）是模式理论的另一个重要内容。内容。内容。内容。这一机理说明，在遗传算法中尽管每一代只处理这一机理说明，在遗传算法中尽管每一代只处理这一机理说明，在遗传算法中尽管每一代只处理这一机理说明，在遗传算法中尽管每一代只处理MM个个体，个个体，个个体，个个体，但事实上却是处理但事实上却是处理但事实上却是处理但事实上却是处理 了了了了M3M3以上的模式。以上的模式。以上的模式。以上的模式。隐含并行性定理隐含并行性定理隐含并行性定理隐含并行性定理 设设设设 (0,1)(0,1)是一个很小的数，模式存活的最小长度是一个很小的数，模式存活的最小长度是一个很小的数，模式存活的最小长度是一个很小的数，模式存活的最小长度 ,群体规模为群体规模为群体规模为群体规模为 ,则则则则GAGA在一次迭代中所处理的在一次迭代中所处理的在一次迭代中所处理的在一次迭代中所处理的“存存存存活率活率活率活率”大于大于大于大于(1-(1-)的模式的模式的模式的模式 数约为数约为数约为数约为O(M3)O(M3)。其中。其中。其中。其中 表示上取值。表示上取值。表示上取值。表示上取值。公式推导公式推导公式推导公式推导 以二进制编码为例。在长度为以二进制编码为例。在长度为l，规模为，规模为M的群体中，包含了的群体中，包含了 2l M2l 个不个不 同的模式，随着进化过程的进行，这些模式中一些定义长度较长的模式被破同的模式，随着进化过程的进行，这些模式中一些定义长度较长的模式被破 坏掉，而另一些定义长度较短的模式却能够生存下来。坏掉，而另一些定义长度较短的模式却能够生存下来。(1)(1)模式存活的最小长度模式存活的最小长度模式存活的最小长度模式存活的最小长度 从模式定理中可以看出，模式在交叉和变异时可能遭破坏。从模式定理中可以看出，模式在交叉和变异时可能遭破坏。由于变异概率很小，在此只考虑交叉的破坏（此式也可兼顾变异的破坏因素由于变异概率很小，在此只考虑交叉的破坏（此式也可兼顾变异的破坏因素)。模式被破坏的概率为：模式被破坏的概率为：l 为保证模式的存活率为保证模式的存活率,令令pd ，即：，即：依据模式定依据模式定义长义长度的定度的定义义，模式不被破坏的最小，模式不被破坏的最小长长度度 是：是：带入上式得：带入上式得：(2)(2)个体编码串中拥有长度为个体编码串中拥有长度为个体编码串中拥有长度为个体编码串中拥有长度为 的模式数目的模式数目的模式数目的模式数目 示例示例示例示例 假设下述个体编码字符串的长度假设下述个体编码字符串的长度假设下述个体编码字符串的长度假设下述个体编码字符串的长度 l l1010，1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 设模式设模式设模式设模式s s 的存活长度的存活长度的存活长度的存活长度 5 5。.将它放置在个体字符串的最左侧，则有：将它放置在个体字符串的最左侧，则有：将它放置在个体字符串的最左侧，则有：将它放置在个体字符串的最左侧，则有：1 0 1 1 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 写成模式的形式，上述字符串变为：写成模式的形式，上述字符串变为：写成模式的形式，上述字符串变为：写成模式的形式，上述字符串变为：%1*%1*方框中方框中方框中方框中%可在可在可在可在 0,1,*0,1,*三者中任取一个。也就是说，可为固定值三者中任取一个。也就是说，可为固定值三者中任取一个。也就是说，可为固定值三者中任取一个。也就是说，可为固定值(0/1)(0/1)或不固定值或不固定值或不固定值或不固定值(*)(*)两种状况。两种状况。两种状况。两种状况。方框内的方框内的方框内的方框内的1 1表示有一个确定的模式，也可以选方框内的其他固定值表示。表示有一个确定的模式，也可以选方框内的其他固定值表示。表示有一个确定的模式，也可以选方框内的其他固定值表示。表示有一个确定的模式，也可以选方框内的其他固定值表示。这时，可以组成的模式个数是：这时，可以组成的模式个数是：这时，可以组成的模式个数是：这时，可以组成的模式个数是：2 2 2 2 2=2=.将上述方框右移一位将上述方框右移一位将上述方框右移一位将上述方框右移一位 其模式表达为：其模式表达为：其模式表达为：其模式表达为：1 0 1 1 1 0 0 0 1 0 *%0*1 0 1 1 1 0 0 0 1 0 *%0*又可以组成又可以组成又可以组成又可以组成 个模式。个模式。个模式。个模式。.上述方框可发生在上述方框可发生在6个不同的位置，即发生次数为：个不同的位置，即发生次数为：，于是，长度为于是，长度为 的个体可组成存活长度为的个体可组成存活长度为 的模式数目是：的模式数目是：(3)(3)群体中的模式数目群体中的模式数目群体中的模式数目群体中的模式数目 当群体由当群体由M个个体组成时，可能组成的长度为个个体组成时，可能组成的长度为 的模式数目为：的模式数目为：若若M较大，则对一些低阶的模式肯定会有一些重复。为排除这些重复部分，可较大，则对一些低阶的模式肯定会有一些重复。为排除这些重复部分，可 取群体的规模数为取群体的规模数为M=。这时，模式阶高于或等于。这时，模式阶高于或等于 的模式最多只的模式最多只 重复计数一次。重复计数一次。另另方面，由于遗传操作都是利用均匀随机数，模式数目服从二项分布，即模方面，由于遗传操作都是利用均匀随机数，模式数目服从二项分布，即模 式中有一半的阶次高于式中有一半的阶次高于 ，另一半小于，另一半小于 。于是，计算时模式数目应。于是，计算时模式数目应 取上式的取上式的 1/2。/2/2/2综合上述各方面，可能存活的模式数目综合上述各方面，可能存活的模式数目ns为：为：即有：即有：ns=cM3=O(M3)结论结论结论结论 遗传算法所处理的有效模式总数约与群体规模遗传算法所处理的有效模式总数约与群体规模遗传算法所处理的有效模式总数约与群体规模遗传算法所处理的有效模式总数约与群体规模MM的立方成正比。也就是说，的立方成正比。也就是说，的立方成正比。也就是说，的立方成正比。也就是说，虽然在进化过程的每一代中只处理了虽然在进化过程的每一代中只处理了虽然在进化过程的每一代中只处理了虽然在进化过程的每一代中只处理了MM个个体，但事实上我们并行处理了与个个体，但事实上我们并行处理了与个个体，但事实上我们并行处理了与个个体，但事实上我们并行处理了与MM 的立方成正比例的模式数。的立方成正比例的模式数。的立方成正比例的模式数。的立方成正比例的模式数。因此，遗传算法事实上是一种并行算法，隐藏在个体的背后，故称隐含并行因此，遗传算法事实上是一种并行算法，隐藏在个体的背后，故称隐含并行因此，遗传算法事实上是一种并行算法，隐藏在个体的背后，故称隐含并行因此，遗传算法事实上是一种并行算法，隐藏在个体的背后，故称隐含并行 算法。正是由于这种隐含并行性，遗传算法的搜寻效率很高。算法。正是由于这种隐含并行性，遗传算法的搜寻效率很高。算法。正是由于这种隐含并行性，遗传算法的搜寻效率很高。算法。正是由于这种隐含并行性，遗传算法的搜寻效率很高。