遗传算法与机器学习.DOC

1、第六章 遗传算法与机器学习6.1 遗传机器学习系统的结构大多数学习系统来说，它们都具有一个共同的特性：即它们都能够产生结构上的变化来提高其内部知识结构的一致性和广泛性，发现和利用一些有意义的概念，增强其在环境下完成任务的能力。在这个观点下，精确地刻画允许产生的结构变化以及这些变化是通过什么方式产生的，是理解一个特定的学习系统最重要的方法之一。对于经典的方法来说，这就意味着完全、清晰地了解可能的结构空间和产生变化的操作。遗传学习系统的一般框架通常，可以将遗传学习系统分为两个子系统：一个基于 GA 的用于产生合适的结构变化的学习子系统和一个用于完成外部环境任务的任务子系统。系统通过任务探测器从外部

2、环境中获取环境信息，任务子系统则对这些信息进行处理，并产生一个对外部环境信息的响应，这个响应通过任务效应器作用到外部环境上。性能探测器对任务子系统对外部环境所产生的影响进行检测，并将所检测到的信息传送到学习子系统中，学习子系统利用这些信息对任务子系统的性能进行评估，并由此改变任务子系统的内部结构，以提高系统的性能。改变任务子系统结构的方式有三种：(1) 用 GA 改变一组预先定义的控制参数；(2) 改变控制任务子系统行为的更加复杂的数据结构，如“议程表” ；(3) 直接修改任务子系统的控制程序，6.2 匹兹堡方法与密西根方法将产生式系统引入遗传机器学习领域后产生了两种重要的实现方法：匹兹堡方法

3、和密西根方法。一种方式由匹兹堡（Pittsburgh）大学的 De Jong 和他的学生 Smith 所提出。这种方法将整个规则集合表示为一个个体，GA 维护一个包含一定数目的候选规则集的种群，这种方法被称为“匹兹堡方法” 。几乎与此同时，密西根（Michigan）大学的 Holland 和他的学生 Reitman 提出了另一种方法，这种方法认为每个个体就是一条规则，而整个种群就是规则集合。这种方法被称为“密西根方法” 。目前一般认为，密西根方法更加适合于在线的、实时的环境，在这种环境下，系统行为上的激进的变化是不能容忍的。而匹兹堡方法更适合于离线的环境，在这种环境下，更加从容不迫的搜索和更加

4、激进的变化是可以接受的。6.3 分类器系统（CS-1）分类器系统是一种学习系统，它通过学习句法规则，来指导系统在外部环境中的行为。分类器系统由三部分构成：(1) 规则和消息系统；(2) 信度分配系统；(3) 遗传算法。规则和消息系统是一种特殊的产生式系统。规则的一般形式为：If then 其含义是：若满足条件 C，则产生动作 A。也就是说，若满足条件，则规则被“激发” 。分类器所产生的动作，实际上也是一种消息，它可能会使得效应器产生一个动作，也有可能激发另一个分类器，还有可能不产生任何作用。分类器系统中采用长度一定的字符串表示一条规则(分类器)，这样，就可以保证句法上的合法性，同时，这种基于字

5、符串的表示方法还使得应用遗传算子变得比较方便。分类器系统结构图:= 0, 1 l:= : := 0, 1, # l消息和条件进行匹配时的匹配原则是：“1”与“1”匹配， “0”与“0”匹配， “#”是通配符，与“0”和“1”都可以匹配。假设有一条消息为 M(0 0 1 0 0)，则以下条件都与它相匹配：(0 0 # 0 0)、(0 0 1 0 0)、(# # 1 0 0)冲突解决机制：分类器系统中通过种“拍卖”的方式，让所有的候选分类器通过竞争来获得被“激活”的权利。信用分配机制桶队算法对于分类器系统来说，衡量每个分类器的“性能”非常困难。但是，为了应用 GA 对分类器进行改进，又必须要对每个

6、分类器在系统中的作用做出一个评价。从外部环境信息到效应器响应动作之间就形成了一条响应链，这条响应链建立了外部信息到效应器响应之间的映射关系。 : : 分类器之间以“交易”的形式传递消息，消息总是传递给“报价”最高的那个分类器。“报价”的计算：“匹配精度”的定义：匹配精度用于衡量消息与分类器的条件的“相似程度” 。匹配精度越高，两者之间的相似性越强。若分类器 C 的激发条件与消息 m 相匹配，则匹配精度可以定义为p(C, m) = 1/R(C)其中，R(C) 代表 C 的激发条件中通配符 “#”的数目。假定一个分类器 C 在 t 时刻的适应值为 Strength(C, t)，那么，当它成为候选分

7、类器时，它给出的“报价”为Bid(C, t) = cbid * R(C) * Strength(C, t)其中，c bid 为一常数，称报价系数。从上述定义中可以看出，候选分类器的报价与它的适应值成正比，与匹配精度成反比。也可以将“报价”简单定义为Bid(C, t) = cbid * Strength(C, t)若定义一个分类器在（t - 1）时刻“出售”过一条稍息，则在 t 时刻它将获得收入 I(t)。那么，一个候选分类器“消费”一条消息后，它的适应值为Strength(C, t+1) = Strength(C, t) - Bid(C, t) + I(t)若一个分类器一直没有被激活，它就可以

8、一直保持它的适应值不变。但是，若一条规则一直不被激发，那么这条规则也就没有存在的必要。所以，必须采用一定的方法来防止出现这种“不思进取”的现象。一种解决方法就是，在每一个时间步对所有的分类器征收“人头税”T(C ， t)：T(C， t) = ctax * Strength(C, t)那么，分类器 C 在 t + 1 时刻的适应值可以表示为:Strength(C, t+1) = Strength(C, t) - Bid(C, t) - T(C， t) + I(t)上式可以化简为Strength(C, t+1) = (1 - K) * Strength(C, t) + I(t)其中，K = cbi

9、d + ctax。分类器重组机制遗传算法分类器系统用 GA 来生成新的，可能具有更好性能的分类器，并且淘汰一部分适应值较低的分类器。需要确定一个时间步数 Tga，这个参数表示两次调用 GA 对分类器进行重组间的时间间隔。T ga 可以任意确定，但 Tga 对系统的性能会产生较大的影响。在实现时可以设置一些触发条件，当满足这些条件时，就调用 GA 对规则进行重组。由于分类器中使用了三元字符表0，l，所以需要对经典变异算子进行一定的修改。当发生变异时，从原来的字符变异到另外两个字符的概率相等。即P(0l)P(0 ) 、P(l0)P(1) 、P(0) P( 1)。分类器的运行6.4 匹兹堡方法：学习

10、系统在 Holland 提出分类器系统的同时，De Jong 和他的学生 Smith 也提出了一种基于遗传算法的机器学习系统LS-I。Smith 所提出的这种机器学习方法是匹兹堡方法的代表。LS-I 的个体不是表示一条规则，而是表示一个规则集合。 只对规则集合进行操作，可以避开信度分配问题。但是，缺乏信度分配机制也是 LS-I 的最大缺陷。由于反馈信息不够充分，LS系统的学习速度比较慢，需要进行大量的训练才能够得到较好的效果。但是，通过学习，LS 系统可以得到很好的性能。学习系统的结构6.4.1 学习系统概述LS 是分类器系统和一般的 产生式系统的结合，它包含了一个 推理引擎和一些规则。工作存

11、储区由一组无序的固定长度的单元构成，每个工作区单元又被细分为信号部分和数据部分。产生式规则存储区由一组无序的规则构成，其中，每条规则是一个固定长度的字符串。规则的前件(条件)由 k 个固定的模式组成，最初的 i 个模式与系统探测器所发出的环境消息所匹配，剩下的 k-i 个模式与工作存储区中的信号相匹配。在 LS 中，所有匹配的规则同时被激发。但是，若规则导致效应器产生了一个动作，则不能同时激发。此时，系统对这些规则进行标记，并让这些被标记的规则向它们将要激活的效应器“投票” 。然后，系统通过随机选择来决定产生哪一个效应器动作，进行选择时每个效应器动作被选中的概率等于它的“得票率” 。规则实例：

12、-1 # # 0 0 # # 0 # 1 # # X 0 # 0 # X 0 0 1 Y 0 1 1 REASSERT(Y)学习系统中的规则前件被分为了两个部分，一个是环境模式部分“-1 # # 0 0 # # 0 #”，另一个是工作存储区模式部分“1 # # X 0 # 0 # X 0 0 1 Y”。“-”代表逻辑“非”运算，表示对匹配结果取反。工作存储区状态每个工作存储区模式和工作存储区消息可以分为两个部分，一部分是信号区，另一部分是数据区。工作存储区模式中的字符“X” 、 “Y”是变量，其第一次出现时要对它赋值，赋值时取相应工作存储区消息的数据区的值。设立数据区变量使得学习系统具有了辨识

13、数据区信息是否相等的基本能力，更重要的是，设立数据区变量使得一条规则可以在它的前件和后件之间传递信息。对规则进行匹配时，要自左向右对规则进行扫描，首先对环境模式进行匹配，若可以匹配，再对工作存储区模式进行匹配。若一条规则的前件能够完全匹配，则这条规则被激发。此时，这条规则首先在工作存储区中搜索一个可用的空位，然后将后件中的消息粘贴到这个空位的信号区中。而后，这条规则将计算后件中数据区的值，再将这个值添加到空位的数据区中。6.4.2 规则集合的重组系统对规则集合的重组通过 GAs 进行，此处 GAs 使用了四种算子：复制、变异、交叉、倒序。复制和变异算子与一般的 GA 算子相同，交叉算子和倒序算

14、子则需要进行一些修改。交叉算子：因为规则集合的长度有可能不相同（包含不同数目的个体） ，所以必须保证交叉后生成的后代有合法个体。倒序算子：由于 LS 系统的规则具有一定的格式，所以在应用倒序操作时必须要保证生成的后代个体中的规则在语法上的合法性。在 LS-I 中，交叉通过三个步骤来进行：对齐、选择交叉点、交换。(1)对齐：进行对齐时首先要在两个规则集合中随机选择一个分隔符，然后将两个规则集合在选定的分隔符处对齐。(2)选择交叉点：在对齐后要选择一个交叉点，交叉点既可以选择在规则之间的边界上，也可以选择在规则内部，系统用一个参数 Pc-rb 来控制交叉发生在规则边界上的概率。若交叉点在规则边界上

15、，则可以保证规则本身不发生变化，而仅仅是规则集合发生了变化；若交叉点选择在规则内部，则规则本身会发生变化，而且规则集合也发生了变化。(3)交换：在确定了交叉点后，就将两个规则集合在交叉点以后的部分互换，这样就得到了两个新的规则集合。例如：A： R1：R 2：R 3：R 4：B： R5：R 6：R 7：R 8：R 9：R 10：A： R1：R 2：R 3：R 4：B： R5：R 6：R 7：R 8：R 9：R 10：A： R1：R 2：R 3：R 4：B： R5：R 6：R 7：R 8：R 9：R 10：A： R1：R 7：R 8：R 9：R 10：B： R5：R 6：R 2：R 3：R 4：在

16、 LS 系统中进行倒序操作时，倒序串的端点必须在规则边界上。R1：R 2：| R3：R 4：R 5： R6：R 7：R 8：| R 9：R 10：R1：R 2：| R8：R 7：R 6： R5：R 4：R 3：| R 9：R 10：6.4.3 LS-I 的性能Smith 用 LS-I 来玩扑克牌游戏以检测系统的学习能力。实验结果表明，LS-1 最后的规则集合中 82的规则与已知的著名的扑克牌游戏公理是相符合的，这表明了 LS-1 确实能够通过学习获取正确的游戏策略。6.5 组织学习方法经济领域中的交易代价理论是用于解释经济某个环境中组织机构如何形成的一种理论。由于分类器中的交互作用可以看做是进

17、行交易，那么，就有可能利用交易代价理论来帮助我们在分类器系统中自动地建立组织结构。在分类器选择交易对象的时候要付出代价，不论是出售方还是买入方。降低交易代价的努力导致了市场、组织和一些其他的经济结构的出现和发展，其中，记录交易者的声誉和生成交易组织是降低交易代价的两种最基本的方法。Wilcox 构造了一种简单的组织增长模型(Organizational Growth Model，OGM)来研究 OGM 如何调节组织增长。OGM 通过让群体组成多个组织，来对个体和集合同时进行演化，各个不同的组织为获得适应值而进行竞争，这样，组织的行为就既具有个体行为的特征，也具有集合行为的特征。这个简化的 OGM 主要包含以下几个组成部分：(1)个体和组织；(2)适值函数；(3)组织算子；(4)选择算子。其中，个体是单独的分类器，而组织则可以包含个或多个个体。组织的适值函数是关于它所包含的个体数目的函数。组织算子是用于控制组织结构的算子。此处使用的选择算子是联赛选择算子。