遗传算法模式定理

• 模式 H( 0****** ) 的长度是0，记作 ( 0****** ) = 0 ；
复制对模式的影响
设在给定时间(代)t 有N个个体，种群A(t)包含有m个特定 模式H，记为
m=m(H, t)
• 在复制过程中，A(t)中的任何一个位串Ai以概率Pi＝f i /∑f i 被
选中并进行复制。
因此复制后在下一代群体 A(t+1)中，群体内属于模式H（或称与模式H匹配） 的个体数目 m(H,t+1) 可用平均适应度按下式近似计算：


k 1

• •
个体是由二值字符集 V={0, 1} 中的元素所组成的一个编码串; 而模式却是由三值字符集 V={0, 1,* } 中的元素所组成的一个编码串。
模式阶 (Schema Order) ——指模式中已有明确含意(二进制字符时指0或1)的字符个数，记做 o(s)，式中
s 代表模式。
• 模式的定义长度( Schema Defining Length) • ——指模式中第一个和最后一个具有明确含意的字符之间的距离，
记作 (s)。
• 例如，模式H( 011*l** ) 的第一个字符为0，最后一个字符为，
中间有3个字符，其定义长度为5-1=4，记作 ( 011*1** ) = 4 ；
例如，模式 ( 011*1** ) 含有4个明确含意的字符，其阶次是4， 记作 o( 011*1** ) =4; 模式 ( 0****** ) 的阶次是1，记作 o( 0****** ) =1。 • 阶次越低，模式的概括性越强，所代表的编码串个体数也越多，反之亦然； • 当模式阶次为零时，它没有明确含义的字符，其概括性最强。
模式的思路为我们提供了一种简单而有效的方法，
使能够在有限字母表的基础上讨论有限长位串的严谨 定义的相似性。
应强调的是，“*”只是一个元符号，既是代表其他
符号的一个符号。它不能被遗传算法直接处理，只不 过是允许来描述特定长度和特定字母表的位串的所有 可能相似性的符号件。
k 1 k 1
遗传算法的模式理论
• 从简单遗传算法的操作中，我们可以看到寻优问
•
题的性能是朝着不断改进的方向发展的。但是我 们怎么能知道对某一特定问题使用遗传算法会得 到优化或接近优化的解呢？ 分析遗传算法中的模式理论： 1. 模式； 2. 复制对模式的影响； 3. 交叉对模式的影响； 4. 变异对模式的影响； 5. 遗传算法有效处理的模式数量。
m( H , t 1) m( H , t ) N
f H
f ( j)
j 1
M
式中 度；
f H ——第t代属于模式 H 的所有个体之平均适应
N——群体中拥有的个体数目。
f
f ( j)
j 1
M
N
f H f
m( H , t 1) m( H , t )
这种所有模式的增减在复制中是并行进行的,遗传算法中隐含的并行 机制就在于此。
为了进一步分析高于平均适配值的模式数量的增长，假设 f ( H ) f c f (c是一个大于零的常数)，则式（2-1）可重写为
f cf f (1 c )m( H , t )
m( H , t 1) m( H , t )
模式
一个模式(Schemata)就是一个描述种群中在位串的某些确定位置上具有相似性的
位串子集的相似性模板(Similarity Template) 。
例如：求 max f(x)=x2
x {0,31}
遗传算法的第0代
位串 x=01101 11000 01000 10011 Xi 13 24 8 19 适配值 f(x)=x2＝132＝169 576 64 361
淘汰某些低适配值个体，而决不会产生新的模式结构，因而性能的改进是有 限的
模式
为了描述一个模式，在用以表示位串的两个字符的字母{0,1}中加入
一个通配符“*”，就构成了一个表示模式用的三个字符的字母表{0， 1，*}。
因此用三元素字母表{0，1，*}可以构造出任意一种模式。
一个Biblioteka Baidu式与一个特定位串相匹配是指：该模式中的1与位串中的1相
匹配，模式中的0与位串的0相匹配，模式中的“*”可以匹配位串中 的0或1。
(2 2)
从原始种群开始（t＝0），并假定是一个稳定的值，则有
t m( H , t 1) m( H ,0 （ )1 ＋c）
可见，对于高于平均适配值的模式的数量将呈指数形式增长（c>0）。
从对复制的分析可以看到，虽然复制过程成功地以并行方式控制着模式
数量以指数形式增减，但由于复制只是将某些高适配值个体全盘复制，或是
在上列种群里的各位串之间，我们能发现具有某种相似性和这种相似性与高适配 值之间具有某种因果关系。
这种因果关系例如：凡是以“1”开始的位串，其适
配值就高；以“0”开始的位串的适配值就低。
这种相似性正是遗传算法有效工作的因素。根据对
种群中高适配置位串之间的相似性的分析，Holland提 出了遗传算法的模式理论.
模式
• 模式00*00匹配了两个位{00100,00000} • 模式*111*可以和{01110, 01111, 11110, 11111}中的任何一
个位串匹配，即与长度为5中间三位为“1”的四个位串匹 配； • 模式0*1**则匹配了长度为5、第一位为0、第三位为1的8 个位串{00100, 00101, 00110, 00111, 01100, 01101, 01110, 01111}
式(2-1)
可见，经过复制操作后，下一代中特定模式的数量H正比于所在位串的平均 值与种群平均适配值的比值。 • 时，H的数量将增加； f H f
•
f H f 时，H的数量将减少。
种群A(t)中的任一模式H在复制中都将按照式(2-1)的规律变化，即
• 适配值高于种群平均值的模式在下一代中的数量增加； • 而适配值低于种群平均值的模式在下一代的数量将减少。