再上一篇: 第 9 章  点模式匹配
上一篇:9. 2  模拟退火框架
主页
下一篇: 第 10 章  多处理器调度
再下一篇:10.2  均场退火
文章列表

9. 3  进化程序设计

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

把PPM任务置于进化程序设计框架中求解① 要有一个表示方法、一个适度函数、一组遗传算子以及控制遗传算子的规则。进化程序设计的核心有以下几部分:

(1) 起始群体的初始化  随机产生一个搜索结点数N= 30的起始群体。

(2) 对群体符号串的代价估值  适度函数决定了群体空间每一个染色体的适度值。

(3) 后代的繁衍  如后面将给出的,根据群体中符号串的适度值,产生新符号串的群体。

(4) 繁衍后代的重新组合  用交叉、突变和转位遗传算子使繁衍后代进行随后的重组。

(5) 收敛准则  重复步骤(2)~(4),直到收敛或者经历了预先给定的代数。

9.3.1  解空间的表示

用与模拟退火相同的一种指派的符号串表示进行进化程序设计。除了在9.2.1节中所描述的特性外,在用遗传算子对符号串表示进行运算时,也必须只产生有效的指派。这样就不再需要耗时的修复算法。用结点组成的符号串表示每一指派(即各个点坐标的标号) ,从而形成搜索/解空间。

9.3.2  群体空间:规模、初始化及其利用

理论上,为了达到运算的高度并行性,希望代的规模尽可能大,甚至是无限的。实际上这是不可能的,因此群体的大小取经验值为N= 30。初始群体是在唯一性约束下通过随机产生染色体形成的。

有效的利用可用的解空间要避免适度值高的个体集中在一起(占统治地位),并保持一个进化群体,这个群体开始是探索性的,最终引向解域的有效搜索。

9.3.3  适度函数

适度(目标或代价)函数应能反映不适当的指派所造成的误差(基于最优参数的),并对部分的匹配进行惩罚。同时,一个好的指派应产生一个高的适度值,反之亦然。(9.11)式所定义的匹配误差满足上述要求,可用作适度值估算子。适度值与匹配误差成反比。9.3.4  繁殖

在产生每一代以后,选择好的染色体以利用其基因遗传知识形成下一代的潜在染色

① 一个进化程序可以看成是一个经过加工修改的、能够引入和利用所讨论问题的结构的遗传算法。

#第91页-

体。通常采用的偏置轮盘选择过程有缺点。具有高适度值的染色体可能被多次挑选,使群

体空间很拥挤,且由于不选择其它可能的染色体而造成群体空间不断狭窄,从而丢掉了有

用的遗传信息。太多相同的染色体也造成计算资源的浪费(好的染色体信息利用因子不是

无限的)。

为了克服上述缺点,可用一个修正的选择机制来实现有效的繁殖。通过执行以下步

骤,不仅能修补前述机制的缺点[109],而且还有显著加快收敛的优点。

(1) 在偏置轮盘方法的基础上,从P(t)中选择r 个(不一定是各不相同的)高适度值

的染色体作为繁殖的父辈。

(2) 从P(t)中确定性地除掉r 个不同的适度值最小的染色体(不依赖于步骤(1)的选

择)。这样得到的(N- r)个染色体进入繁殖库。

(3) 从步骤(1)~(2)得到的N 个符号串组成的繁殖库中,通过一种遗传算子的运算

对步骤(1)所得到的r 个父辈进行重新组合以产生r 个后代。

(4) 从步骤(2)得到的(N- r)个染色体和从步骤(3)得到的 r 个后代形成新群体

P(t+ 1),从而完成新群体的选择过程,这是在重组之前的重要预处理步骤。此项技术使r

个后代是从高适度值的父辈产生的,每一个后代在某种方式上与其它后代又不相同。其结

果就是有可能形成比父辈的代价略高,而又能进入用于重新组合的下一个繁殖库的后代。

就像模拟退火方法那样,这类似于偶然接受有较高代价的染色体的概念[2]。

由于执行了步骤(2),最好的染色体总是与(N- r- 1)个适度值高的个体一起进入下

一次的产生过程。这样选择得到的群体有较丰富的遗传信息,有较大的潜力产生好的

后代。

9.3.5  遗传算子

遗传或重组算子控制着新的信息的形成手段,且现有的信息也在染色体之间进行交

换,以利于随后进化成有较高存活概率的染色体。在EP 算法中,用满足1对1映射的三

个这样的算子,从而避免了采用修补算法。

1. 突变

这里所用的突变算子是对染色体的单个基因进行操作的,这单个基因通常是在根据

适度值计算所提取知识的基础上确定性地选择出来的。因此不像通常的突变具有探索性

那样,这里的算子更具有实效性。这种基于知识的算子被用到的概率很大。在PPM 问题

中定义了三种突变算子,如下所述,每一种算子以不同的概率得到应用。

(1) 突变-1  这里,在染色体内部,把对用(9.6)式计算得到的平方误差和起最大作

用的基因与起次大作用的基因进行交换。这是一种确定性作法,而且总是在每次迭代时对

群体中最好的染色体进行。它也以某个概率在其它染色体上实现。假设有以下收敛前一

步的符号串:

1 2 10 4 5 6 7 8 9 3 11 12 `

#第92页-

显然在第3和第10位置上的基因需要进行交换以达到最优匹配。在这一步,用突变-1就

能有效地加以实现。与通常的突变方式不同,这种情况下,突变-1算子以概率为1地使下

一代收敛。

(2) 突变-2  第一个基因的选择与突变-1相同。把对误差作用第三大的基因选作第

二个基因,或从染色体符号串中随机拾取一个基因与第一个基因进行交换。在有必要把对

误差作用最大的基因与不是次大作用的基因进行交换时,需要这样的交换方法。事实上,

对于大的染色体,可以把这个原则扩展到对平方误差和作用大的多个基因组合。这样搜索

可以更快一些。

(3) 突变-3  把对误差作用最大的基因与任何其它基因进行交换可能造成不适当的

指派结果,从而显著增加总体的平方误差。这种情况使得上述两种突变都没有用处,而使

解总是停留在局部最小值。突变-3通过随机选择两个互换的基因来补救这种情况。它提

供了比可用解空间更大的搜索空间。因此执行这种突变方式的概率要保持在很小数值。无

论如何,由于它提供了从明显的局部最小值跳出的机制,所以可以起到重要的作用。

2. 均匀交叉

下面定义一种基于位置的均匀交叉,使在染色体间实现位置遗传信息(而不是阶保持

的遗传信息)的交换,它是多点交叉概念的一般化[150],[153]。具体做法如下:

(1) 在规定概率的基础上,选择两个用于交叉的符号串。

(2) 对于第一个符号串的每一个基因位置,如果该基因对误差作用大,而在第二个符

号串中相应基因的误差作用小,则把第二个符号串的该基因复制到第一个符号串的相应

位置上;同时把该位置原来的基因复制到第一个符号串中与用于置换的基因相同的位

置上。

(3) 对第二个染色体复重步骤(2) 。

通过这种交叉,从两个父辈中产生的两个后代能保持好的基因位置,并能对坏的基因

位置用从其它染色体的好基因位置的基因来改换。这种交叉非常有效,因为它能在不干扰

好基因位置的情况下取代多个坏基因位置,从而使误差值决定性地得以降低。

3. 反转

反转算子对它所操作的染色体进行(n+ 1)补运算,从而完全改变了正在进行的搜索

空间。例如,如果一个单元值的范围是从 0到n, 则一个单元值为 x 的(n+ 1)补就是

(n+ 1- x)。以下是当n= 15时,一个符号串及其(n+ 1)补的一个例子:

1 2 6 5 9 13 15 14 4 11 7 3 `

15 14 10 11 7 3 1 2 12 5 9 13 1w

注意,反转操作使符号串产生了巨大的变化,因此实施反转操作的概率要比实施互换

的概率小得多。最好随着代数的增长,使这种算子的概率为0。只有在解看来陷入到局部

最小值时,才进行这种操作。

#第93页-

9.3.6  模拟结果

试验结果表明进化编程技术在收敛速度和稳健性方面超过了其它通常算法。这是由于消除了其它算法所固有的无效计算环境。新的基于领域知识的互换和交叉算子是提高算法速度的起作用的因素。这里用三组点模式的结果对此加以说明。图9.1(a)示出了模型点模式。考虑以下三种示例:①

例1: 观察模式= T[模型模式]

例2: 观察模式= T[模型模式]+ 噪声

例3: 观察模式= T[模型模式]+ 噪声- n个点,点2,点10和点11丢失。

图 9.1  模型点模式和观察模式

例1: T[模型点模式],

例2: T[模型点模式]加噪声,

例3: T[模型点模式]加噪声并去掉3个点

① 第三种情况有三个丢失点,每一个符号串中赋有三个“0”。

#第94页-

T[・]表示由旋转π/4,尺度因子为3,在x 和y 轴平移量分别为 100和300所组成的相

似变换。噪声为零均值,方差为9的高斯随机变量。例1,2,3三种示例分别示于图9.1

(b),(c)和(d)。在几次迭代以后,算法就完成了匹配,图9.2给出了上述各种情况的收敛

速率。表9.1总结了模拟结果。它表示的只是每种情况下的典型运行结果。

表9.1  模拟结果(每例运行一次样本)

实  验 收敛所要的代数 收敛时误差

例1 8 0 u

例2 6 43.62 G

例3 12 90.67 G

图9.2  为得到正确匹配的进化程序设计的收敛率

例1: T[模型点模式],

例2: T[模型点模式]加噪声,

例3: T[模型点模式]加噪声并去掉3个点

#第95页-

9.4  总结

本章的主要目的是说明怎样把一个模式识别问题,例如PPM 问题,映射到能用计算智能方法进行求解的框架中。在建立框架和选择设计参数时有许多自由度。本章所概述的过程可以作为解决其它模式识别问题的示例。

#第96页-