遗传算法模式定理推导

《遗传算法模式定理推导》由会员分享，可在线阅读，更多相关《遗传算法模式定理推导（4页珍藏版）》请在金锄头文库上搜索。

1、8.3 遗传算法基本定理1、模式的概念 所谓模式就是一个相同的构形， 它描述的是一个数字串的子集合，在这个集 合中的所有数字串之间、在某些确定位置上是相同的。模式一般用大写字母H 表示。用 3 个字符的字母表0,1, V组成的三元组来描述模式， 其中，符号代表不确定数字，即在特定位置上可以与数字0 或 1 相匹配。例如，字符串长为5 的模式110H，并称数字串A=01110是模式 H 的一个代表串，这是因为数 字串 A 与模式 H 在确定位置 2、3 和 5 上相匹配。 遗传算法的操作过程非常简单，从一个含有N 个染色体的初始群体出发， 不断循环地执行选择、 交叉和变异运算。 看起来遗传算法是

2、按这种简单的模式直 接作用在一个个数字串组成的群体上，实际上，在每一代的计算过程中， 这种数 字串的显式操作过程蕴含了大量模式的隐含操作。这里，首先讨论选择、 交叉和 变异算子对模式作用的影响。对于由 N 个二进制数字串组成的群体中，至多包含有2LN个模式（所有符 号都为确定数字时），式中 L 为数字串长。 在遗传算法的执行过程中， 所有的模式并不是以同等的机会发生的。有些模 式比起其他的模式更明确， 例如，模式011 1和模式0相比，在相似性方面， 模式011 1就比较明确。有些模式的跨度要比另一些模式的长，例如，模式11 和模式1 1相比，在长度方面，模式11要跨越整个串长。 为了定量地描

3、述模式，下面介绍两个基本概念： 模式的定义长度和模式的阶。 模式 H 的定义长度是指模式H 中第 1 个常数位置与最后1 个常数位置之间 的距离，用()H表示。例如，模式1011 1H的定义长度为1()4H，这是因为模式1H 中第 1 个常数的位置为 1，最后回个常数的位置为5，它们之间的距离为 5-1=4；另一个模式20H中仅有 1 个常数位置， 即第 1 个和最后 1个常数位置是同一个位置，因此其定义长度2()0H。模式 H 的阶是指出现在模式H 中常数的个数， 用()O H表示。在二进制数字串中，一个模式 H 的阶就是模式中所有1 和 0的个数。例如，模式1011 1H的阶为4，可记为1

4、()4O H，同样地，模式20H阶为1，可记为2()1O H。模式、 模式的定义长度以及模式的阶对于讨论和区分数字串的相似性是有用 的标志，并且它们提供了一个基本的方法来分析遗传算子对包含在群体中的基因 的作用效果。 下面分别考虑选择、 交叉和变异操作对包含在群体中的模式作用的 单独效果和联合效果，并最终导出模式定理。 2、选择操作的效果 假设在给定时间 t 代， 一个特定的模式 H 有 m 个代表数字串包含在群体( )A t 中，记为(, )mm H t，在不同的时间 t 代，不同的模式 H 可能有不同数量的代表 数字串。 在选择操作阶段， 每个数字串根据它的适应度函数值进行选择，一个数字串

5、 ( )iA t 的选择率siP 为式中，if 为数字串( )A t的适应度函数值。当采用没有重叠的N 个数字串的群体替代群体( )A t后，人们期望在时间(1)t代，模式H 在群体(1)A t中有(,1)mm H t个代表数字串，则模式H 的 数量为式中，()f H表示在时间 t 代模式 H 包含的所有代表数字串的平均适应度函数值。由于群体的平均适应度函数值可记为：故模式 H 的选择生长方程可表示为（8.1） 由此式看出，一个特定的模式H 按照其适应度函数值与群体的平均适应度 函数值之间的比例生长，换句话说，当()f Hf 时，模式 H 的代表数字串在下一代中将会增多；当()f Hf 时，模

6、式 H 的代表数字串在下一代中将会减少。 群体( )A t中的任一模式H 在选择操作下都将按上述规律变化，这种对所有模式数量的增减在选择操作中是并行发生的，遗传算法中隐含的并行机制就在于此。 上面定量分析了选择对不同模式的影响，可以看出，在平均适应度函数值以 上的模式数量将逐渐增加， 平均适应度函数值以下的模式数量将逐渐消失。在此 基础上，下面导出一个定量表达式。 假设某一特定模式H 的适应度函数值保持在高出群体平均适应度函数值以 上一个 Cf ，即()f HfCf ，C 为一常数，则模式H 的选择生长方程可变为：从时间0t代开始，模式 H 的选择生长方程为：至此选择的作用已清楚了。当常数C0

7、 时，在群体平均适应度函数值以上的模 式数量将会按指数规律增长，而当常数C0 时，在群体平均适应度函数值以下 的模式数量将会按指数规律减少。 在一定程度上，选择可以把按指数规律增长或减少的模式并行地遗传到下一 代。一方面，许许多多不同的模式根据相同的规则，通过利用简单的选择算子被 并行地处理； 另一方面， 仅仅只有选择操作并无助于搜索空间中新的区域，这是 因为选择操作并没有搜索新的点。 3、交叉操作的效果 虽然选择对模式H 的数量的影响令人惊奇，但若无交叉操作，它就失去了 意义，因为选择不会在数字串空间中产生新的点，它只是一种选择而已。因而， 为了检测模式空间中新的区域，需要执行交叉操作。 这

8、里，仅考虑简单的一点交叉的作用效果。 一点交叉过程首先是随机选择一对交配数字串，然后随机选择一个交叉位 置， 将其中一个数字串从交叉位置到右端的子串与另一个交配数字串对应的子串 相交换。为了讨论方便，不妨考虑一个长度为6 的串以及隐含其中的两个模式。假定 A 被选中进行交叉，而交叉点以等概率产生，即交叉点落在1、2、3、 4、 5 的概率相同。这里不妨假设交叉点为3， 即交叉发生在位置3 和位置 4 之间， 并以分隔符“|”表示交叉泣置，即有在这种情况下， 除了与A进行交叉的串 （称作配偶） 在确定位（比如位置 2、 6）相同（这种可能性我们暂且不考虑）外，模式1H 将遭到破坏，因为位置2 的

9、“1”和位置 6 的“0”在交叉产生的子代个体中将被替代为不同的值。比如A 的配偶为101001A，则产生的后代为1010001A，2101001A，都不是1H 的样本，即发生交叉后，模式1H 丢失了。而相同情况下，2H 却依然存在，因为不论 A 的配偶为任何串，2H 中确定位 4 的“1”和确定位 5 的“1”都将一块传入子代。可能有的读者会问，假若交叉点在位置4，2H 不也会遭到破坏吗？不错！但有一点可以看出，由于交叉点等概率产生，模式1H 遭破坏的概率（在位置2、3、 4、5 交叉都遭破坏） 大大超过模式2H （只在位置 4 交叉遭破坏）， 即2H 的 “生命力”要强于1H 。现在定量地

10、讨论一下。我们注意到模式1H 的定义长度为4，那么交叉点在6-1=5 个位置随机产生时，1H 遭破坏的概率为1() /(1)4/ 5dPHl， 换句话说， 其 生 存 概率 为1/ 5； 而 模 式2H 的定 义 长 度 为 1， 则2H 遭 破 坏 的概 率为2()/(1)1/5dPHl，即生存概率为4/5。更一般地讲，模式H 只有当交叉点落在定义长度之外才能生存。在简单交 叉（单点交叉）下的H 的生存概率1()/(1)sPHl。而交叉本身也是以一定的概率cP 发生的，所以模式H 的生存概率为：（8.2） 现在我们考虑先前暂且忽略的可能性，即交叉发生在定义长度内，模式H 不被破坏的可能性。在

11、前面的例子中，若A 的配偶在位置 2、6 上有一位与 A 相 同，则1H 将被保留。考虑到这一点，式（8.2）给出的生存概率只是一个下界，即有：（8.3） 式（8.3）描述了模式在交叉算子作用下的生存概率。现在考虑模式H 在选 择和交叉算子的共同作用下的变化。参照式（8.1）和式（ 8.3） ，则有：(8.4) 由(8.4)式可以看出，在选择和交叉算子的共同作用下，模式的增长（减少） 取决于两个因素：（1）模式的平均适应度是否高于群体平均适应度； （2）模式是 否具有较短的定义长度。 显然，那些平均适应度高于群体平均适应度、具有短定 义长度的模式将呈指数级增长。 现在考虑选择和交叉结合在一起时

12、对模式的作用效果。当仅考虑选择时， 人 们感兴趣的是计算一个特定的模式在下一代中期望出现的数目。假设选择和交叉 操作是不相关的，可用下式来估算：（8.5） 比较式（8.1）和式（8.3）可以看出，选择和交叉一起对模式的作用效果是， 通过把仅有选择作用的模式数量与在交叉作用下的生存概率相乘得到的。 模式 H 的数量增多或减少与一个乘积因子有关。在选择和交叉作用下，这 个乘积因子与两个因素有关：模式的适应度函数值()f H是在群体平均适应度函数值f 之上还是之下； 模式具有相对短的定义长度还是长的定义长度()H。 当()f H越大，()H 越短，则在下一代中，模式H 的数量就越多，且按指数增长率进

13、化发展。 4、变异算子的作用效果 最后讨论变异算子的作用效果。由变异引起模式H 被破坏的概率表示为 ()mP O H，其中mP 为变异概率。变异算子是以概率mP 随机地改变数字串中一个位置上的值，为了使模式H 可以生存下来，所有特定的位置上的值必须存活。 因为单个等位基因存活的概率为1mP ，并且由于每次变异都是统计独立的，因此，当模式 H 中个()O H确定位都存活时，这个模式才存活，因而在变异算子作用下，则模式H 的存活概率为()(1)O H mP。一般情况下1mP，模式 H 的存活概率可以近似地等于 1()mP O H 。5、模式定理 因此，在考虑选择、交叉和变异作用下，一个特定模式H 在下一代中期望 产生的数目可近似表示为（8.6） 1()mP O H 乘以（ 8.5）式：()()()11()1()()111cmcmmcHHHPPO HPPO HPO HPLLL 最后一项是极小项，忽略了。从式（8.6）可以看出，增加变异作用后几乎不改 变先前的结论。人们称式（8.6）为模式定理，又称作遗传算法的基本定理，即 定义长度短、低阶且模式平均适应度函数值在群体平均适应度函数值以上的模 式，在遗传算法执行过程中其数量将按指数规律增多。实际上， 模式定理给出了 模式在选择、交叉和变异作用下子代中产生个体数目的下限值。