再上一篇: 第 6 章  遗 传 算 法
上一篇:6. 2  一个示例
主页
下一篇:6. 4  其它遗传操作
再下一篇:6. 5  习题
文章列表

6. 3  为什么遗传算法会奏效?

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

以二值符号串表达的遗传算法的理论基础可参见文献[64][83]。分析二值符号串的重要工具是相似性模板。它揭示出存在于二值符号串之间的相似性。

在前面的叙述中,二值符号串中每个基因的取值只能是0或1。模板是二值符号串的一种扩展,其中基因的取值可为0,1或“* ”。符号“* ”表示一种随意的情况,也就是说基因的取值既可为0亦可为1。例如,(* ,0,1,* ,0,0)、(* ,* ,* ,* ,* ,* )和(1,0,0,1,0,1)都是6位二值符号串的模板。如果一个基因的取值不是“* ”,我们称其为确定位; 否则称为不定位。

当一个模板和一个符号串的每个基因都匹配(“* ”与0和1都匹配)时,称这对模板和符号串匹配。因此,模板(* ,0,1,* ,0,0)与4个符号串(0,0,1,0,0,0)、(0,0,1,1,0,0)、(1,0,1,0,0,0)和(1,0,1,1,0,0)都匹配。同理,模板(* ,* ,* ,* ,* ,* )与所有64个6位二值符号串匹配,而模板(1,0,0,1,0,1)仅与符号串(1,0,0,1,0,1)匹配。

对于 位符号串,一共存在3n 个模板,且每个符号串可与2n 个模板相匹配。在一个拥

有m 个符号串的群体中,可与这m个符号串相匹配的模板数目在2n 到m2n之间。

模板可以两个值来刻画: 阶和定长。模板S 的阶是其中0和1的出现次数,以o(S)表示。例如,o((* ,0,1,* ,0,0))= 4,o((* ,* ,* ,* ,* ,* ))= 0,而o((1,0,0,1,0,1))= 6。模板S 的定长是其中第一个和最后一个确定位之间的距离,以 (S)表示。例如,((* ,0,1,* ,0,0))= 4,δ((* ,* ,* ,* ,* ,* ))= 0,而δ((1,0,0,1,0,1))= 5。

繁殖、交叉和突变等三个遗传操作对一个符号串群体的影响可以利用每一代中能与一个模板匹配的符号串个数的期望值来加以考察。在此,采用下列符号:

・n是一个二值符号串的位数。

・P(t)是在t 时刻的符号串群体。

・m 是P(t)中符号串的个数,亦即群体大小。

・f (s)是符号串s∈P(t)的适度值。

・F(t) = ∑if(si),si∈P(t) 是P(t) 中所有符号串的总适度值。

・F(t) = ∑if(si)/m 是P(t) 中所有符号串的平均适度值。

・F(S) = f (si)①,si与S 匹配,是P(t) 中所有与模板S 匹配的符号串的平均适

∑i

度值或模板S 的平均适度值。

・ ζ(S,t)是P(t)中与模板S 匹配的符号串个数的期望值。

・pc是交叉概率。

・pm是突变概率。

对于繁殖,一个P(t)中的符号串si存活到下一代的概率等于f(si)/F(t)。因此,对于一个拥有m 个符号串的群体,P(t+ 1)中与模板S 匹配的符号串个数的期望值为

① 译者注: 此表达式应除以P(t)中与S匹配的s 的数量。

#第54页-

ζ(S,t + 1)= mζ(S,t) F(S) (6.4)

F(t)

= ζ(S,t) F(S) (6.5)

F(t)

这就是说,与一个特定模板相匹配的符号串个数随着该模板的平均适度值与群体的平均适度值的比率而改变。若比率大于1,与“高于平均”模板匹配的符号串个数增长; 若比率小于1,与“低于平均”模板匹配的符号串个数减少。如果比率长期保持大于1,则与“高于平均”模板匹配的符号串个数呈指数增长(见习题6.5)。与此类似,如果比率长期保持小于1,则与“低于平均”模板匹配的符号串个数呈指数减少。

交叉和突变操作通过改变符号串中基因的取值来生成新符号串。对于一个能与交叉或突变操作前后的符号串都匹配的模板来说,它的确定位在该操作实施后应保持不变。

交叉将两个符号串同时截为两段并交换它们的尾部。当截点处于两个确定位之间时,这使得模板很有可能被破坏①。既然截点可被选在n- 1个可能位置中的任意一个,一个模板S 被破坏的概率是δS( )/(n- 1)。与交叉概率pc一并考虑,模板S 被破坏的概率是pcδS( )/(n- 1)。因此,模板S 存活的概率是

1- pc δ(S) (6.6)

n- 1

对于与一个模板S 相匹配的符号串个数的期望值,交叉的效果为

ζ(S,t - 1) ≥ζ(S,t) 1- pc δ(S) (6.7)

n- 1

突变只改换符号串的一位。如果被变更的是一个不定位,则模板可以存活。由此可见,模板S 在突变操作后仍存活的概率为

(1- pm)o(S) (6.8)对于pmn 1,(6.8)式可用1- o(S)pm 来近似。

将繁殖、交叉和突变的影响结合在一起,我们得到

ζ(S,t+ 1)≥ζ(S,t) F(S) 1- pc δ(S) [1- pmo(S)]

F(t) n- 1

F(S) δ(S) (6.9)

≥ζ(S,t) 1- pcn- 1- pmo(S)

F(t)

这就引出了下列定理。它指出: 与一个“高于平均”模板相匹配的字符串个数的期望值呈指数增长; 交叉和突变对短的和低阶的模板没有影响。

定理6.1  遗传算法的基本定理或模板定理  短的、低阶的、高于平均的模板在后代中获得呈指数增长的扩散。

短的、低阶的、高于平均的模板被称为结构单元并为遗传算法的寻求对象。结构单元之所以能在后代中获得呈指数增长的扩散从而得到最优解,其原因可参考统计决策理论中k个武装盗匪问题[83]。结合不同符号串中“好的”基因以获取更好基因的思想在直觉上是令人感兴趣的,并可作为假定。

① 如果新的尾部具有与旧的尾部完全相同的确定位,则此模板将存活。

#第55页-

假定6.1  结构单元假定  遗传算法通过结构单元的并列来寻求接近最优的性能。

虽然这一假定尚未被证明,大量应用的实验结果都支持这一假定的有效性。有兴趣的读者可以在文献[64]中找到有关资料。