第六章遗传算法和机器学习.doc

第六章 遗传算法与机器学习 6.1 遗传机器学习系统的结构 大多数学习系统来说，它们都具有一个共同的特性：即它们都能够产生结构上的变化来提高其内部知识结构的一致性和广泛性，发现和利用一些有意义的概念，增强其在环境下完成任务的能力。 在这个观点下，精确地刻画允许产生的结构变化以及这些变化是通过什么方式产生的，是理解一个特定的学习系统最重要的方法之一。对于经典的方法来说，这就意味着完全、清晰地了解可能的结构空间和产生变化的操作。 遗传学习系统的一般框架 通常，可以将遗传学习系统分为两个子系统：一个基于GA的用于产生合适的结构变化的学习子系统和一个用于完成外部环境任务的任务子系统。 系统通过任务探测器从外部环境中获取环境信息，任务子系统则对这些信息进行处理，并产生一个对外部环境信息的响应，这个响应通过任务效应器作用到外部环境上。性能探测器对任务子系统对外部环境所产生的影响进行检测，并将所检测到的信息传送到学习子系统中，学习子系统利用这些信息对任务子系统的性能进行评估，并由此改变任务子系统的内部结构，以提高系统的性能。 改变任务子系统结构的方式有三种： 用GA改变一组预先定义的控制参数； 改变控制任务子系统行为的更加复杂的数据结构，如“议程表”； 直接修改任务子系统的控制程序， 6.2 匹兹堡方法与密西根方法 将产生式系统引入遗传机器学习领域后产生了两种重要的实现方法：匹兹堡方法和密西根方法。一种方式由匹兹堡（Pittsburgh）大学的De Jong和他的学生Smith所提出。这种方法将整个规则集合表示为一个个体，GA维护一个包含一定数目的候选规则集的种群，这种方法被称为“匹兹堡方法”。几乎与此同时，密西根（Michigan）大学的Holland和他的学生Reitman提出了另一种方法，这种方法认为每个个体就是一条规则，而整个种群就是规则集合。这种方法被称为“密西根方法”。 目前一般认为，密西根方法更加适合于在线的、实时的环境，在这种环境下，系统行为上的激进的变化是不能容忍的。而匹兹堡方法更适合于离线的环境，在这种环境下，更加从容不迫的搜索和更加激进的变化是可以接受的。 6.3 分类器系统（CS-1） 分类器系统是一种学习系统，它通过学习句法规则，来指导系统在外部环境中的行为。 分类器系统由三部分构成： 规则和消息系统； 信度分配系统； 遗传算法。 规则和消息系统是一种特殊的产生式系统。规则的一般形式为： If 条件C then 动作A 其含义是：若满足条件C，则产生动作A。也就是说，若满足条件，则规则被“激发”。 分类器所产生的动作，实际上也是一种消息，它可能会使得效应器产生一个动作，也有可能激发另一个分类器，还有可能不产生任何作用。 分类器系统中采用长度一定的字符串表示一条规则(分类器)，这样，就可以保证句法上的合法性，同时，这种基于字符串的表示方法还使得应用遗传算子变得比较方便。 分类器系统结构图 消息 ::= {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对分类器进行改进，又必须要对每个分类器在系统中的作用做出一个评价。 从外部环境信息到效应器响应动作之间就形成了一条响应链，这条响应链建立了外部信息到效应器响应之间的映射关系。 外部环境信息 — 分类器1 : 消息1 — … 分类器n : 消息n — 效应器动作 分类器之间以“交易”的形式传递消息，消息总是传递给“报价”最高的那个分类器。 “报价”的计算： “匹配精度”的定义：匹配精度用于衡量消息与分类器的条件的“相似程度”。匹配精度越高，两者之间的相似性越强。若分类器C的激发条件与消息m相匹配，则匹配精度可以定义为 p(C, m) = 1/R(C) 其中，R(C)代表C的激发条件中通配符“#”的数目。 假定一个分类器C在t时刻的适应值为Strength(C, t)，那么，当它成为候选分类器时，它给出的“报价”为 Bid(C, t) = cbid * R(C) * Strength(C, t) 其中，cbid为一常数，称报价系数。从上述定义中可以看出，候选分类器的报价与它的适应值成正比，与匹配精度成反比。 也可以将“报价”简单定义为 Bid(C, t) = c