清华大学出版社 TSINGHUA UNIVERSITY PRESS 为了描述一个模式，在用以表示位串的两个字符{0,1中 加入一个通配符“*”，就构成了一个表示模式用的三个 字符的符号表{0,1，*}。因此用三个元素符号表{0,1，*}可 以构造出任意一种模式。当一个模式与一个特定位串相匹 配时，意味着该模式中的1与位串中的1相匹配，模式中的 0与位串中的0相匹配，模式中的“*”与位串中的0或1相 匹配。例如，模式00*00匹配了两个位串，即00100， 00000;模式*111*可以和{01110,01111,11110,11111 中的任何一个位串相匹配；模式0*1*则匹配了长度位5， 第一位位0、第三位为1的8个位串，即00100,00101， 00110,00111,01100,01101,01110,01111}。 模式的思路提供了一种简单而有效的方法，使能够在有限 符号表的基础上讨论有限长位串的严谨定义的相似性。应 强调的是，“*”只是一个代表其它符号的一个元符号， 它不能被遗传算法直接处理，但可以据此计算出所有可能 的模式
为了描述一个模式，在用以表示位串的两个字符{0，1}中 加入一个通配符“*”，就构成了一个表示模式用的三个 字符的符号表{0,1, *}。因此用三个元素符号表{0,1, *}可 以构造出任意一种模式。当一个模式与一个特定位串相匹 配时，意味着该模式中的1与位串中的1相匹配，模式中的 0与位串中的0相匹配，模式中的“*”与位串中的0或1相 匹配。例如，模式00*00匹配了两个位串，即{00100， 00000}；模式*111*可以和{01110，01111，11110，11111} 中的任何一个位串相匹配；模式0*1**则匹配了长度位5， 第一位位0、第三位为1的8个位串，即{00100，00101， 00110，00111，01100，01101，01110，01111}。 模式的思路提供了一种简单而有效的方法，使能够在有限 符号表的基础上讨论有限长位串的严谨定义的相似性。应 强调的是，“*”只是一个代表其它符号的一个元符号， 它不能被遗传算法直接处理，但可以据此计算出所有可能 的模式
清华大学出版社 TSINGHUA UNIVERSITY PRESS 一 般地，假定符号表的基数是k,例如0,1的基数是2， 则定义在该符号表上的长度为的位串中，所有可能包含 的最大模式数为(k十1)'，原因是在个位置中的任何一个位 置上即可以取个字符中的任何一个又可以取通配符“*” 即共有k十1个不同的表示，则个位置的全排列数为(k+1)'。 例如，对长度=5，k=2（对应0,1)，则会有 3×3×3×3×3=35=243=(k+1)种不同的符号串，而位串 的数量仅为=25=32。可见，模式的数量要大于位串的数 量。 对于由0、1和*定义且长度为的符号串所能组成的最大模 式数为(2十1)'。对于任一长度为的给定位串，当任一位置 上只有两种不同表示时，所含模式数为2个，因此对于含 有个位串个体的种群可能包含的模式数在2~nX2'之间。 不难看出，遗传算法正是利用种群中位串之间的众多的相 似性以及适值之间的相关性，来引导遗传算法进行有效地 搜索
一般地，假定符号表的基数是k，例如{0，1}的基数是2， 则定义在该符号表上的长度为l的位串中，所有可能包含 的最大模式数为(k＋1)l ，原因是在个位置中的任何一个位 置上即可以取k个字符中的任何一个又可以取通配符“*” ， 即共有k＋1个不同的表示，则l个位置的全排列数为(k＋1)l 。 例如，对长度l=5,k=2（对应0，1），则会有 3×3×3×3×3=35=243=(k＋1)l种不同的符号串，而位串 的数量仅为k l=25=32。可见，模式的数量要大于位串的数 量。 对于由0、1和*定义且长度为l的符号串所能组成的最大模 式数为(2＋1)l 。对于任一长度为的给定位串，当任一位置 上只有两种不同表示时，所含模式数为2 l个，因此对于含 有n个位串个体的种群可能包含的模式数在2 l～n×2 l之间。 不难看出，遗传算法正是利用种群中位串之间的众多的相 似性以及适值之间的相关性，来引导遗传算法进行有效地 搜索
清华大学出版社 TSINGHUA UNIVERSITY PRESS 为论述方便，首先定义一些名词术语。为不失一般性，考虑在二进制 符号表={和，1}上构造位串的表示。用大写字母表示一个位串，如 A=1010011。一个长度为的位串表达式为： A=01023.-101 0,∈ 其中：4(i=1,2,,)具有二值特性，又可称为基因。相应地， 若一个模式是定义在V+={0,1,)之上的，则用大写字母H表示，如 H=10**11*。 在第代的种群用A(t)表示，种群中的位串个体分别用A,(=1,2, n)表示。 为了区分不同类型的模式，对模式H定义两个量：模式位数(order) 和模式的定义长度(defining length)分别表示为OH)和6()。O) 是H中有定义的非“*”位的个数，如H=00*10,则O(D=4。模式的 定义长度6(0是指H中左右两端有定义位置之间的距离。例如 H=011*1**,则6(0=5一1=4；若H=**11***,则6(H0=4一3=1；又 若H=******,则6（价=0。这两个量为分析位串的相似性及分析遗 传操作对重要模式（称为建筑块(building blocks)模式）的影响提供了基 本手段
为论述方便，首先定义一些名词术语。为不失一般性，考虑在二进制 符号表V={0，1}上构造位串的表示。用大写字母表示一个位串，如 A=1010011。一个长度为的位串表达式为： A=a1 a2 a3…al-1 al ai∈V 其中：ai（i=1，2，…，l）具有二值特性，ai又可称为基因。相应地， 若一个模式是定义在V＋={0，1，*}之上的，则用大写字母H表示，如 H=10**11*。 在第t代的种群用A(t)表示，种群中的位串个体分别用Aj（j=1，2，…， n）表示。 为了区分不同类型的模式，对模式H定义两个量：模式位数（order） 和模式的定义长度（defining length）分别表示为O(H)和δ(H)。O(H) 是H中有定义的非“*”位的个数，如H=00*1*0，则O(H)=4。模式的 定义长度δ(H)是指H中左右两端有定义位置之间的距离。例如 H=011*1**，则δ(H)=5－1=4；若H=**11***，则δ(H)=4－3=1；又 若H=*******，则δ(H)=0。这两个量为分析位串的相似性及分析遗 传操作对重要模式(称为建筑块(building blocks)模式)的影响提供了基 本手段
清华大学出版社 TSINGHUA UNIVERSITY PRESS 6.2.2复制对模式的影响 设在给定时间（代）t,种群A(t)包含个特定模式H, 记为 m-m(H,t) 在复制过程中，A()中的任何一个位串A,以概率 P=∫②被选中并进行复制。假如选择是有放回地抽样 且两代种群之间没有交叠（即若A(①的规模为n,则在产生 A(t十1)时，必须从A()中选个位串进匹配集)，可以期 望在复制完成后，在t千1时刻，特定模式的数量为： m(H,t+1)=m(H,t)nf(H)f 其中：0是在时刻对应于模式的位串的平均适值，因 为整个种群的平均适殖"=f加，则上式又可写为 mH,t+1)=(H,t) (6-1)
6.2.2 复制对模式的影响 设在给定时间(代)t，种群A(t)包含m个特定模式H， 记为 m=m(H,t) 在复制过程中，A(t)中的任何一个位串 Ai以概率 Pi =f i /Σf i被选中并进行复制。假如选择是有放回地抽样， 且两代种群之间没有交叠（即若A(t)的规模为n，则在产生 A(t＋1)时，必须从A(t)中选n个位串进匹配集），可以期 望在复制完成后，在t＋1时刻，特定模式H的数量为： m(H,t+1)= m(H,t)nf(H)/Σf i 其中：f(H)是在t时刻对应于模式H的位串的平均适值，因 为整个种群的平均适值 =Σf i /n，则上式又可写为 m(H,t+1)= m(H,t) （6-1） f
清华大学出版社 TSINGHUA UNIVERSITY PRESS 可见，经过复制操作后，下一代中特定模式的数 量H正比于所在位串的平均适值与种群平均适值 的比值。若H)>f,则H的数量将增加，若f0 <f，则H的数量将减少。种群A()中的任一模 式H在复制中都按式(6-1)的规律变化。即若包含H 的个体位串的平均适值高于当前种群中所有个体 位串的平均适值，则种群包含的特定模式在下一 代中的数量将增加；反之，将减少。操作中模式 的增减在复制中是并行的，这恰恰表现了遗传算 法隐含的并行性。方程式(6-1)即是复制操作对模 式H数量影响的定量描述
可见，经过复制操作后，下一代中特定模式的数 量H正比于所在位串的平均适值与种群平均适值 的比值。若f(H)＞ ，则H的数量将增加，若f(H) ＜ ，则H的数量将减少。种群A(t)中的任一模 式H在复制中都按式(6-1)的规律变化。即若包含H 的个体位串的平均适值高于当前种群中所有个体 位串的平均适值，则种群包含的特定模式在下一 代中的数量将增加；反之，将减少。操作中模式 的增减在复制中是并行的，这恰恰表现了遗传算 法隐含的并行性。方程式(6-1)即是复制操作对模 式H数量影响的定量描述。 f f