智能优化算法理论与应用中的模式理论

在仅仅利用适应度来进行搜索的过程中，遗传算法是如何会得到最优化或接近最优化的解呢？带着这一问题，本节中将进一步分析遗传算法的工作原理。

1.模式

在遗传算法中，模式（schemata）就是描述种群在染色体的某些确定位置上具有相似性的一组符号串。模式中所体现的这种相似性正是遗传算法有效工作的原因，根据对种群中高适应度染色体之间相似性的分析，Holland提出了遗传算法的模式理论。

在用以表示位串的两个字符｛0，l｝中加入一个通配符“*”，就构成了用来表示模式的字符集｛0，l，*｝，用这三个字符就可以构造出任意一个模式H。为了区分不同的模式，对模式H定义两个量：模式位数（order）O（H）和模式的定义长度（defining length）δ（H）。O（H）是指H中有定义的非“*”位的个数；δ（H）是指H中左右两端有定义位置之间的距离。这两个量为分析位串的相似性及遗传操作对重要模式的影响提供了基本的手段。

2.模式定理

在选择、交叉、变异的连续作用下，模式的数量会不断地变化，下面就遗传操作对模式的影响进行分析。

设在第t代迭代中，种群A（t）包含m个特定的模式H，记为：m=m（H，t）。在选择操作中，A（t）中的任意一个个体A，被选中的概率为pi=fi/∑fi，则在t+1代特定模式的数量为

其中f（H）为第t代包含模式H的个体的平均适应度，将种群平均适应度¯f=∑fi/n带入上式，得

可见，经过选择操作之后，下一代中特定模式H的数量正比于其所在个体的平均适应度与种群平均适应度的比值，即当f（H）＞¯f时，H的数量将增加；当f（H¯f时，H的数量将减少。种群中的任意模式都是按照式（2.5）所示的规模变化的，而操作中模式的增减是在选择中并行进行的，这恰恰体现了遗传算法的隐含并行性。

交叉的过程是个体之间有组织的随机交换信息的过程。交叉操作对模式的影响与模式的定义长度δ（H）有关，δ（H）越大，H的跨度就越大，随机交叉点落入其中的可能性就越大，H被分裂的可能性就越大，即H存活率就越低。设交叉概率为pc，则模式H的存活率ps的下限为：(www.xing528.com)

式中，l为个体染色体的长度，结合式（2.5），在选择、交叉操作之后模式H的数量为

变异是对个体的单个位置以概率pm进行替换，因此单个位置基因值的存活概率为（1-pm）（保持率），由于每一位的变异都是统计独立的，因此，一个特定的模式仅当它的O（H）个确定位都存活时才能存活，故经变异操作后，特定模式H的存活率为

（1-pm）O（H）

由于一般情况下pm≪1，所以H的存活率可以表示为

综合考虑选择、交叉、变异操作的共同作用，则模式H在经历这些操作之后，在下一代中的数量为

综上所述，我们可以得到遗传算法中的一个非常重要的结论——模式定理。

定理2.1　遗传算法中，在选择、交叉、变异的作用下，具有定义长度短、确定位数少、平均适应度高于群体平均适应度的模式将随着代数的增加呈指数式增长。

模式定理是遗传算法的基本理论，保证了较优的模式的数目呈指数增长，为解释遗传法机理提供了一种数学工具。