《遗传算法模式定理》由会员分享，可在线阅读，更多相关《遗传算法模式定理（18页珍藏版）》请在金锄头文库上搜索。
1、遗传算法的模式理论,从简单遗传算法的操作中，我们可以看到寻优问题的性能是朝着不断改进的方向发展的。但是我们怎么能知道对某一特定问题使用遗传算法会得到优化或接近优化的解呢？ 分析遗传算法中的模式理论： 模式； 复制对模式的影响； 交叉对模式的影响； 变异对模式的影响； 遗传算法有效处理的模式数量。,模式,一个模式(Schemata)就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板(Similarity Template) 。 例如：求 max f(x)=x2 x 0,31 遗传算法的第0代 在上列种群里的各位串之间，我们能发现具有某种相似性和这种相似性与高适配值之间具有某
2、种因果关系。,这种因果关系例如：凡是以“1”开始的位串，其适配值就高；以“0”开始的位串的适配值就低。 这种相似性正是遗传算法有效工作的因素。根据对种群中高适配置位串之间的相似性的分析，Holland提出了遗传算法的模式理论.,模式,为了描述一个模式，在用以表示位串的两个字符的字母0,1中加入一个通配符“*”，就构成了一个表示模式用的三个字符的字母表0，1，*。 因此用三元素字母表0，1，*可以构造出任意一种模式。 一个模式与一个特定位串相匹配是指：该模式中的1与位串中的1相匹配，模式中的0与位串的0相匹配，模式中的“*”可以匹配位串中的0或1。,模式,模式00*00匹配了两个位00100,0
3、0000 模式*111*可以和01110, 01111, 11110, 11111中的任何一个位串匹配，即与长度为5中间三位为“1”的四个位串匹配； 模式0*1*则匹配了长度为5、第一位为0、第三位为1的8个位串00100, 00101, 00110, 00111, 01100, 01101, 01110, 01111,模式的思路为我们提供了一种简单而有效的方法，使能够在有限字母表的基础上讨论有限长位串的严谨定义的相似性。 应强调的是，“*”只是一个元符号，既是代表其他符号的一个符号。它不能被遗传算法直接处理，只不过是允许来描述特定长度和特定字母表的位串的所有可能相似性的符号件。,一般地，假定
4、字母表的基数是k，例如0,1的基数是2，则定义在该字母表上的长度为的位串中所有可能包含的最大模式数为 ，原因是在L个位置中的任何一个位置上都可以取k个字符中的任何一个及通配符“*” ，即共有k+1个位置中的任何一个位置的全排列数为 例如，对长度5，k=2则会有3333335243 中不同的相似模板，而位串的数量仅为25=32。可见，模式的数量要大于位串的数量。,编码字符串的模式数目 (1) 模式总数 n 1,(2) 编码字符串（一个个体编码串）所含模式总数 n 2 二进制字符串 对于长度为的某二进制字符串，它含有的模式总数最多为： 2 2 2 2 = 2 注意 这个数目是指字符串已确定为0或1
5、，每个字符只能在已定值 (0/1)或 * 中选取； 前面所述的 n1 指字符串未确定，每个字符可在0, 1, * 三者中选取。 一般情况下 长度为、取值有 k 种的某一字符串，它可能含有的模式数目最多为： n2 = (3) 群体所含模式数 在长度为，规模为M的二进制编码字符串群体中，一般包含有 2 Mx 2 个模式。,种群中位串之间的众多的相似性，可引导遗传算法有效地搜索。因为即使是一个规模不大的种群，也包含了丰富的 2 m 2 个有关这种相似性的信息。 这些相似性和适配值之间的相关性正是是遗传算法能够进行有效搜索的根本所在。, 个体是由二值字符集 V=0, 1 中的元素所组成的一个编码串;
6、而模式却是由三值字符集 V=0, 1,* 中的元素所组成的一个编码串。 模式阶 (Schema Order) 指模式中已有明确含意(二进制字符时指0或1)的字符个数，记做 o(s)，式中 s 代表模式。 例如，模式 ( 011*1* ) 含有4个明确含意的字符，其阶次是4，记作 o( 011*1* ) =4; 模式 ( 0* ) 的阶次是1，记作 o( 0* ) =1。 阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然； 当模式阶次为零时，它没有明确含义的字符，其概括性最强。,模式的定义长度( Schema Defining Length) 指模式中第一个和最后一个具有明确含意
7、的字符之间的距离，记作 (s)。 例如，模式H( 011*l* ) 的第一个字符为0，最后一个字符为，中间有3个字符，其定义长度为5-1=4，记作 ( 011*1* ) = 4 ； 模式 H( 0* ) 的长度是0，记作 ( 0* ) = 0 ；,复制对模式的影响,设在给定时间(代)t 有N个个体，种群A(t)包含有m个特定模式H，记为 m=m(H, t) 在复制过程中，A(t)中的任何一个位串Ai以概率Pif i /f i 被选中并进行复制。,因此复制后在下一代群体 A(t+1)中，群体内属于模式H（或称与模式H匹配） 的个体数目 m(H,t+1) 可用平均适应度按下式近似计算：,式中 第t
8、代属于模式 H 的所有个体之平均适应度； N群体中拥有的个体数目。,式(2-1),可见，经过复制操作后，下一代中特定模式的数量H正比于所在位串的平均值与种群平均适配值的比值。 时，H的数量将增加； 时，H的数量将减少。 种群A(t)中的任一模式H在复制中都将按照式(2-1)的规律变化，即 适配值高于种群平均值的模式在下一代中的数量增加； 而适配值低于种群平均值的模式在下一代的数量将减少。 这种所有模式的增减在复制中是并行进行的,遗传算法中隐含的并行机制就在于此。,为了进一步分析高于平均适配值的模式数量的增长，假设 (c是一个大于零的常数)，则式（2-1）可重写为,从原始种群开始（t0），并假定是一个稳定的值，则有 可见，对于高于平均适配值的模式的数量将呈指数形式增长（c0）。 从对复制的分析可以看到，虽然复制过程成功地以并行方式控制着模式数量以指数形式增减，但由于复制只是将某些高适配值个体全盘复制，或是淘汰某些低适配值个体，而决不会产生新的模式结构，因而性能的改进是有限的,
