遗传算法与机器学习

1、第六章第六章 遗传算法与机器学习遗传算法与机器学习 概述概述 分类器系统分类器系统cs-1（holland） 学习系统学习系统ls-1（smith） 组织学习方法（组织学习方法（wilcox） 6.1 概概 述述 “学习学习”是一个由是一个由“未知未知”到到“知知”的过程。的过程。 “学习学习”的目的是获得的目的是获得尽可能接近真实尽可能接近真实的的“知识知识”。 “学习学习”过程包含了对已有知识的过程包含了对已有知识的“继承继承”和对未知知和对未知知 识的识的“探索探索”。 “学习学习”本身是一个本身是一个进化进化的过程。的过程。 将将“进化计算进化计算”应用于应用于“学习学习”是是自然的自

2、然的、合理的合理的。 6.1 概概 述述 概念学习可以看作是对概念描述空间的一种启发式搜概念学习可以看作是对概念描述空间的一种启发式搜 索。索。 概念描述空间是对原始数据（即由教师或环境向学习概念描述空间是对原始数据（即由教师或环境向学习 系统提供的某些概念的实例）使用一定推理规则得到系统提供的某些概念的实例）使用一定推理规则得到 的。的。 概念学习中所隐含的这种搜索机制以及它所采用的符概念学习中所隐含的这种搜索机制以及它所采用的符 号表示方法，使得遗传算法在概念学习领域有其用武号表示方法，使得遗传算法在概念学习领域有其用武 之地。之地。 遗传算法本身固有的鲁棒性，使得基于遗传算法的概遗传算法

3、本身固有的鲁棒性，使得基于遗传算法的概 念学习系统具有更少的限制性。念学习系统具有更少的限制性。 6.1 概概 述述 1978年年holland等实现了第一个基于遗传算法的机器学等实现了第一个基于遗传算法的机器学 习系统：一级认知系统习系统：一级认知系统cs-1（cognitive system level one）。）。 1986年，年，holland提出桶队算法（提出桶队算法（bucket brigade），）， 整个系统被称为分类器系统。整个系统被称为分类器系统。 1980年，年，smith提出提出ls-1系统。在某些重要方面，如染系统。在某些重要方面，如染 色体的表示、反馈方式等，色体

4、的表示、反馈方式等，ls-1和和cs-1有明显差异。有明显差异。 1993年，年，de jong和和spears提出提出gabil系统，实现基于系统，实现基于 ga的概念学习。的概念学习。 6.1 概概 述述 从应用角度来说，这些系统对从应用角度来说，这些系统对顺序决策顺序决策这类学习问题这类学习问题 较为合适。该类问题可以描述如下：一决策主体以回较为合适。该类问题可以描述如下：一决策主体以回 复方式与一具有离散时间状态的动态系统交互，在每复方式与一具有离散时间状态的动态系统交互，在每 个时间步的开始，系统处于某确定状态。该主体依当个时间步的开始，系统处于某确定状态。该主体依当 前状态，根据决

5、策规则，从有限的动作集中选择一个前状态，根据决策规则，从有限的动作集中选择一个 动作供动态系统执行，并进入到一个新的状态。同时动作供动态系统执行，并进入到一个新的状态。同时 向主体反馈一个补偿（向主体反馈一个补偿（payoff），其目的是发现一决），其目的是发现一决 策规则集以使补偿最大化。策规则集以使补偿最大化。 6.2 遗传机器学习系统的结构遗传机器学习系统的结构 大多数学习系统都具有一个共同的特性：即它们都能够产大多数学习系统都具有一个共同的特性：即它们都能够产 生结构上的变化来提高其内部知识结构的生结构上的变化来提高其内部知识结构的一致性一致性和和广泛性广泛性， 发现和利用一些有意义的

6、概念，增强其在环境下完成任务发现和利用一些有意义的概念，增强其在环境下完成任务 的能力。的能力。 6.2 遗传机器学习系统的结构遗传机器学习系统的结构 通常，可以将遗传学习系统分为两个子系统：一个基于通常，可以将遗传学习系统分为两个子系统：一个基于ga 的用于产生合适的结构变化的的用于产生合适的结构变化的学习子系统学习子系统和一个用于完成和一个用于完成 外部环境任务的外部环境任务的任务子系统任务子系统。 系统通过系统通过任务探测器任务探测器从外部环境中获取环境信息，从外部环境中获取环境信息，任务子任务子 系统系统则对这些信息进行处理，并产生一个对外部环境信息则对这些信息进行处理，并产生一个对外

7、部环境信息 的响应，这个响应通过的响应，这个响应通过任务效应器任务效应器作用到外部环境上。作用到外部环境上。性性 能探测器能探测器对任务子系统对外部环境所产生的影响进行检测，对任务子系统对外部环境所产生的影响进行检测， 并将所检测到的信息传送到并将所检测到的信息传送到学习子系统学习子系统中，学习子系统利中，学习子系统利 用这些信息对任务子系统的性能进行评估，并由此改变任用这些信息对任务子系统的性能进行评估，并由此改变任 务子系统的内部结构，以提高系统的性能。务子系统的内部结构，以提高系统的性能。 6.2 遗传机器学习系统的结构遗传机器学习系统的结构 改变任务子系统结构的方式有三种：改变任务子系

8、统结构的方式有三种： (1) 用用ga改变一组预先定义的控制参数；改变一组预先定义的控制参数； (2) 改变控制任务子系统行为的更加复杂的数据结构，如改变控制任务子系统行为的更加复杂的数据结构，如 “议程表议程表”； (2) 直接修改任务子系统的控制程序，直接修改任务子系统的控制程序， 6.3 匹兹堡方法与密西根方法匹兹堡方法与密西根方法 将产生式系统引入遗传机器学习领域后产生了两种重要的将产生式系统引入遗传机器学习领域后产生了两种重要的 实现方法：实现方法：匹兹堡方法匹兹堡方法和和密西根方法密西根方法。 匹兹堡方法：匹兹堡方法：将整个规则集合表示为一个个体，将整个规则集合表示为一个个体，ga

9、维护一维护一 个包含一定数目的候选规则集的种群。由匹兹堡个包含一定数目的候选规则集的种群。由匹兹堡 （pittsburgh）大学的）大学的de jong和他的学生和他的学生smith所提出。所提出。 密西根方法：密西根方法：认为每个个体就是一条规则，而整个种群就认为每个个体就是一条规则，而整个种群就 是规则集合。由密西根（是规则集合。由密西根（michigan）大学的）大学的holland和他的和他的 学生学生reitman提出。提出。 一般认为，密西根方法更加适合于在线、实时的环境，在一般认为，密西根方法更加适合于在线、实时的环境，在 这种环境下，系统行为上的激进的变化是不能容忍的。而这种环

10、境下，系统行为上的激进的变化是不能容忍的。而 匹兹堡方法更适合于离线的环境，在这种环境下，更加从匹兹堡方法更适合于离线的环境，在这种环境下，更加从 容不迫的搜索和更加激进的变化是可以接受的。容不迫的搜索和更加激进的变化是可以接受的。 匹兹堡方法匹兹堡方法 首先要选择适当的表示方法。首先要选择适当的表示方法。 一种表示方法将单个规则作为一个基因，而将整个分类器一种表示方法将单个规则作为一个基因，而将整个分类器 系统作为一个基因串（个体）。系统作为一个基因串（个体）。 交叉算子提供规则的新的组合方式，而变异算子则提供新交叉算子提供规则的新的组合方式，而变异算子则提供新 的规则。的规则。 为了使得交

11、叉算子和变异算子能够产生合法的个体，一种为了使得交叉算子和变异算子能够产生合法的个体，一种 最简单的方法就是将所有的规则用固定长度、固定字段格最简单的方法就是将所有的规则用固定长度、固定字段格 式的二进制串来表示。这样，这些式的二进制串来表示。这样，这些“ifthen”规则就很规则就很 自然地表示为一组固定数目的待匹配的传感器模式和一个自然地表示为一组固定数目的待匹配的传感器模式和一个 在此模式下的动作。在此模式下的动作。 匹兹堡方法匹兹堡方法 也可以采用更加灵活的表示方法：用不定长的串来表示规也可以采用更加灵活的表示方法：用不定长的串来表示规 则。这种情况下，需要对遗传算子进行修改才能保证得

12、到则。这种情况下，需要对遗传算子进行修改才能保证得到 合法的个体。一种方式就是在串中加入合法的个体。一种方式就是在串中加入“标点符号标点符号”，并，并 通过这些通过这些“标点符号标点符号”来区分各条规则和标注规则的内部来区分各条规则和标注规则的内部 结构。结构。 和表示方法相关的另外一个问题就是每个个体所包含的规和表示方法相关的另外一个问题就是每个个体所包含的规 则数目。若将规则集合看做是一个程序或者是一个知识库，则数目。若将规则集合看做是一个程序或者是一个知识库， 那么，规定每个个体包含相同数目的规则是极不自然的。那么，规定每个个体包含相同数目的规则是极不自然的。 smith成功地设计了一种

13、成功地设计了一种ga，这种算法中的个体长度是变，这种算法中的个体长度是变 化的。化的。 密西根方法密西根方法 holland认为，对于一个特定的人（认知实体）的知识（经认为，对于一个特定的人（认知实体）的知识（经 验）的更自然的观点是将知识看做是一组规则，这组规则验）的更自然的观点是将知识看做是一组规则，这组规则 在与环境的交互作用下不断改变。这一组知识并不是通过在与环境的交互作用下不断改变。这一组知识并不是通过 每一代中进行的选择和交叉来进行演变，相反，这一组知每一代中进行的选择和交叉来进行演变，相反，这一组知 识是在个体尽力使自己适应环境的过程中实时积累的。识是在个体尽力使自己适应环境的过

14、程中实时积累的。 “分类器系统分类器系统”认知模型认知模型 在分类器系统中，在分类器系统中，gas所操作的个体不是规则集合而是单所操作的个体不是规则集合而是单 独的规则。独的规则。 分类器系统中最重要也是最困难的问题是信度分配问题，分类器系统中最重要也是最困难的问题是信度分配问题， 也就是如何将适应度值分配到各条规则上去的问题。也就是如何将适应度值分配到各条规则上去的问题。 桶队算法桶队算法 6.4 分类器系统（分类器系统（cs-1） 分类器系统是一种学习系统，它通过学习句法规则，分类器系统是一种学习系统，它通过学习句法规则， 来指导系统在外部环境中的行为。来指导系统在外部环境中的行为。 分类

15、器系统由三部分构成：分类器系统由三部分构成： (1) 规则和消息系统；规则和消息系统； (2) 信度分配系统；信度分配系统； (3) 遗传算法。遗传算法。 分类器系统结构图分类器系统结构图 6.4 分类器系统（分类器系统（cs-1） 规则和消息系统是一种特殊的产生式系统。规则的一规则和消息系统是一种特殊的产生式系统。规则的一 般形式为：般形式为： if then 其含义是：若满足条件其含义是：若满足条件c，则产生动作，则产生动作a。也就是说，。也就是说， 若满足条件，则规则被若满足条件，则规则被“激发激发”。 分类器所产生的动作，实际上也是一种消息，它可能分类器所产生的动作，实际上也是一种消息

16、，它可能 会使得效应器产生一个动作，也有可能激发另一个分会使得效应器产生一个动作，也有可能激发另一个分 类器，还有可能不产生任何作用。类器，还有可能不产生任何作用。 6.4 分类器系统（分类器系统（cs-1） 分类器系统中采用长度一定的字符串表示一条规则分类器系统中采用长度一定的字符串表示一条规则（分类分类 器），这样，就可以保证句法上的合法性，同时，这种基器），这样，就可以保证句法上的合法性，同时，这种基 于字符串的表示方法还使得应用遗传算子变得比较方便。于字符串的表示方法还使得应用遗传算子变得比较方便。 := 0, 1l := 0, 1, #l := : 消息和条件进行匹配时的匹配原则是：

17、消息和条件进行匹配时的匹配原则是：“1”与与“1”匹配，匹配， “0”与与“0”匹配，匹配，“#”是通配符，与是通配符，与“0”和和“1”都可以匹都可以匹 配。配。 6.4 分类器系统（分类器系统（cs-1） 假设有一条消息为假设有一条消息为m(0 0 1 0 0)，则以下条件都与它相匹，则以下条件都与它相匹 配：配： (0 0 # 0 0)、(0 0 1 0 0)、(# # 1 0 0) 冲突解决机制：分类器系统中通过一种冲突解决机制：分类器系统中通过一种“拍卖拍卖”的方式，的方式， 让所有的候选分类器通过竞争（花钱购买）来获得被让所有的候选分类器通过竞争（花钱购买）来获得被“激激 活活”的

18、权利。的权利。 6.4 分类器系统（分类器系统（cs-1） 信用分配机制信用分配机制桶队算法桶队算法 对于分类器系统来说，衡量每个分类器的对于分类器系统来说，衡量每个分类器的“性能性能”非常困非常困 难。但是，为了应用难。但是，为了应用ga对分类器进行改进，又必须要对每对分类器进行改进，又必须要对每 个分类器在系统中的作用做出一个评价。个分类器在系统中的作用做出一个评价。 从外部环境信息到效应器响应动作之间就形成了一条响应从外部环境信息到效应器响应动作之间就形成了一条响应 链，这条响应链建立了外部信息到效应器响应之间的映射链，这条响应链建立了外部信息到效应器响应之间的映射 关系。关系。 分类器

19、之间以分类器之间以“交易交易”的形式传递消息，消息总是传递给的形式传递消息，消息总是传递给 “报价报价”最高的那个分类器。最高的那个分类器。 6.4 分类器系统分类器系统（cs-1） “报价报价”的计算的计算： “匹配精度匹配精度”的定义：匹配精度用于衡量消息与分类器的条件的的定义：匹配精度用于衡量消息与分类器的条件的 “相似程度相似程度”。匹配精度越高，两者之间的相似性越强。若分类。匹配精度越高，两者之间的相似性越强。若分类 器器c c的激发条件与消息的激发条件与消息m m相匹配，则匹配精度可以定义为相匹配，则匹配精度可以定义为 p p( (c,mc,m) ) = = 1/1/r r( (c

20、 c) ) 其中，其中，r(c)r(c)代表代表c c的激发条件中通配符的激发条件中通配符“#”#”的数目。的数目。 假定一个分类器假定一个分类器c在在t时刻的适应值为时刻的适应值为strength(c, t)，那么，当它，那么，当它 成为候选分类器时，它给出的成为候选分类器时，它给出的“报价报价”为为 bid(c, t) = cbid * r(c) * strength(c, t) 其中，其中，cbid为一常数，称为一常数，称报价系数报价系数。从上述定义中可以看出，候选。从上述定义中可以看出，候选 分类器的报价与它的适应值成正比，与匹配精度成反比。分类器的报价与它的适应值成正比，与匹配精度成

21、反比。 6.4 分类器系统（分类器系统（cs-1） 也可以将也可以将“报价报价”简单定义为简单定义为 bid(c, t) = cbid * strength(c, t) 若定义一个分类器在（若定义一个分类器在（t - 1）时刻）时刻“出售出售”过一条稍息，则过一条稍息，则 在在t时刻它将获得时刻它将获得收入收入i(t)。那么，一个候选分类器。那么，一个候选分类器“消费消费” 一条消息后，它的适应值为一条消息后，它的适应值为 strength(c, t+1) = strength(c, t) - bid(c, t) + i(t) 6.4 分类器系统（分类器系统（cs-1） 若一个分类器一直没有被

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

23、刻的适应值可以表示为: 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 = cbid + ctax。 6.4 分类器系统（分类器系统（cs-1） 分类器重组机制分类器重组机制遗传算法遗传算法 分类器系统用分类器系统用ga来生成新的，可能具有更好性能的分类器，并来生成新的，可能具有更好性能的分类器，并 且淘汰一部分适应值较低的分类器，以使分类器系统的整体性能且淘汰一部分适应值

24、较低的分类器，以使分类器系统的整体性能 不断提高。不断提高。 一般来说，为保证学习系统性能的稳定性，不采用完全取代的方一般来说，为保证学习系统性能的稳定性，不采用完全取代的方 法，而是选取一定比例的染色体来取代。法，而是选取一定比例的染色体来取代。 需要确定一个时间步数需要确定一个时间步数tga，这个参数表示两次调用，这个参数表示两次调用ga对分类器对分类器 进行重组间的时间间隔。进行重组间的时间间隔。tga可以任意确定。在实现时可以设置一可以任意确定。在实现时可以设置一 些触发条件，当满足这些条件时，就调用些触发条件，当满足这些条件时，就调用ga对规则进行重组。对规则进行重组。 由于分类器中

25、使用了三元字符表由于分类器中使用了三元字符表0，l，所以需要对经典变，所以需要对经典变 异算子进行一定的修改。当发生变异时，从原来的字符变异到另异算子进行一定的修改。当发生变异时，从原来的字符变异到另 外两个字符的概率相等。即外两个字符的概率相等。即 p(0l)p(0)、p(l0)p(1)、p(0)p( 1)。 6.4 分类器系统（分类器系统（cs-1） holland给出的在分类器中采用遗传算法的核心步骤：给出的在分类器中采用遗传算法的核心步骤： (1) 根据分类器的强度从分类器集合中成对挑选分类器，根据分类器的强度从分类器集合中成对挑选分类器， 强度越大，被选出的可能性越大；强度越大，被选

26、出的可能性越大； (2) 对选中的分类器对应用交叉、变异算子，生成新的分对选中的分类器对应用交叉、变异算子，生成新的分 类器；类器； (3) 用生成的后代替换强度最弱的那些分类器。用生成的后代替换强度最弱的那些分类器。 6.4 分类器系统（分类器系统（cs-1） 分类器系统中的遗传算法：分类器系统中的遗传算法： begin (1) t = 0，随机生成集合，随机生成集合bt，它由，它由m个分类器组成；个分类器组成； (2) 计算计算bt中全体分类器的中全体分类器的平均强度平均强度vt。对每个分类器赋予一个。对每个分类器赋予一个标准标准 化强度值化强度值st(cj)/vt。 (3) 给给bt中的

27、每个分类器中的每个分类器cj赋一个与其标准强度值成正比的概率，并赋一个与其标准强度值成正比的概率，并 根据根据bt中的概率分布，从中的概率分布，从bt中选取中选取n对对分类器，其中分类器，其中n m； (4) 对每对分类器应用交叉算子，生成对每对分类器应用交叉算子，生成2n个新的分类器；个新的分类器； (5) 将将bt中的中的2n个强度值最低的分类器用新生成的个强度值最低的分类器用新生成的2n个取代；个取代； (6) t = t + 1，返回步骤，返回步骤2。 (7) end 6.4 分类器系统（分类器系统（cs-1） 生物进化的目的并不是要产生出单一的超级物种，生物进化的目的并不是要产生出单

28、一的超级物种， 而是要产生出彼此相互适应的物种群组成的生物而是要产生出彼此相互适应的物种群组成的生物 圈。同理利用遗传算法的目的也不是为了控制个圈。同理利用遗传算法的目的也不是为了控制个 别规则和策略的演变，而是为了控制由许多规则别规则和策略的演变，而是为了控制由许多规则 构成的分类系统的演化。竞争的压力并不能孤立构成的分类系统的演化。竞争的压力并不能孤立 地筛选出最优规则，但是可以引起大系统的进化。地筛选出最优规则，但是可以引起大系统的进化。 6.4 分类器系统（分类器系统（cs-1） 如果按每条规则产生的正确行动的数目对其评分，如果按每条规则产生的正确行动的数目对其评分， 只会有利于演化出

29、个别超级规则，而不利于寻找只会有利于演化出个别超级规则，而不利于寻找 到一组相互之间发生有效作用的规则（系统）。到一组相互之间发生有效作用的规则（系统）。 所以必须改变策略，强迫这些规则去争夺对行动所以必须改变策略，强迫这些规则去争夺对行动 的控制权。每条满足条件的规则都要与其他满足的控制权。每条满足条件的规则都要与其他满足 条件的规则进行竞争，并且由其中最有力的规则条件的规则进行竞争，并且由其中最有力的规则 来决定系统在某种情况下的行动。如果系统的行来决定系统在某种情况下的行动。如果系统的行 动成功了，获胜的规则将被加强，反之，它们将动成功了，获胜的规则将被加强，反之，它们将 被削弱。被削弱

30、。 6.4 分类器系统（分类器系统（cs-1） 可以把每条规则看成是关于分类系统的一种可以把每条规则看成是关于分类系统的一种假设假设 （hypothesis）。只有当某条规则自称与当前情况有关。只有当某条规则自称与当前情况有关 时，它才参加角逐。它的竞争力取决于它对解决同类时，它才参加角逐。它的竞争力取决于它对解决同类 问题所做的贡献大小。随着遗传算法的运作，强有力问题所做的贡献大小。随着遗传算法的运作，强有力 的规则发生组配，形成融合上一代基因块为一体的后的规则发生组配，形成融合上一代基因块为一体的后 代规则，这些后代取代了最弱小的规则，它们相当于代规则，这些后代取代了最弱小的规则，它们相当

31、于 一些似乎可能但还未经证实的假设。一些似乎可能但还未经证实的假设。 6.4 分类器系统（分类器系统（cs-1） 规则之间的竞争为分类系统应付层出不穷的新情况提供了规则之间的竞争为分类系统应付层出不穷的新情况提供了 巧妙的手段。如果分类系统具有响应某种情况的有力规则，巧妙的手段。如果分类系统具有响应某种情况的有力规则， 就等于分类系统的某些假没已经被证实。只有在满足某些就等于分类系统的某些假没已经被证实。只有在满足某些 条件的有力规则不存在的情况下，也就是只有当分类系统条件的有力规则不存在的情况下，也就是只有当分类系统 不知所措的时候，那些生来就比上一代弱小的后代规则才不知所措的时候，那些生来

32、就比上一代弱小的后代规则才 有出头之日，可能赢得竞争，并影响分类系统的行为。如有出头之日，可能赢得竞争，并影响分类系统的行为。如 果它们的行为对于分类系统有所帮助，它们便生存下去，果它们的行为对于分类系统有所帮助，它们便生存下去， 否则，它们很快就被取代。所以，在分类系统很有经验的否则，它们很快就被取代。所以，在分类系统很有经验的 情况中，后代并不会干涉分类系统的行为，它只是作为关情况中，后代并不会干涉分类系统的行为，它只是作为关 于在新情况下应该如何行动的假设，在一旁静静地等候着。于在新情况下应该如何行动的假设，在一旁静静地等候着。 6.4 分类器系统（分类器系统（cs-1） 增加这样的竞争

33、对于分类系统的演化有很大的帮助。增加这样的竞争对于分类系统的演化有很大的帮助。 分类系统在开始运行的初期，先发展出条件简单的规分类系统在开始运行的初期，先发展出条件简单的规 则，即那些把很多情况当作相同情况对待的规则。分则，即那些把很多情况当作相同情况对待的规则。分 类系统把这些规则作为缺省规则。在缺乏更详细信息类系统把这些规则作为缺省规则。在缺乏更详细信息 的情况下，用它们来说明分类系统应采取的某种行动。的情况下，用它们来说明分类系统应采取的某种行动。 不过，缺省规则只能作为肤浅的判断，因为它们经常不过，缺省规则只能作为肤浅的判断，因为它们经常 出错，因而强度得不到加强。随着分类系统获得经验

34、，出错，因而强度得不到加强。随着分类系统获得经验， 繁殖和交叉使得更复杂和更专用的规则得到发展，这繁殖和交叉使得更复杂和更专用的规则得到发展，这 些规则迅速得到增强，很快成为各种特殊情况下分类些规则迅速得到增强，很快成为各种特殊情况下分类 系统行为的主宰。系统行为的主宰。 6.4 分类器系统（分类器系统（cs-1） 最终分类系统发展成为一种层次结构：处于下层的例最终分类系统发展成为一种层次结构：处于下层的例 外规则层处理大多数情况；当详细规则无法满足情况外规则层处理大多数情况；当详细规则无法满足情况 的条件时，处于层次结构上层的缺省规则就发挥作用。的条件时，处于层次结构上层的缺省规则就发挥作用

35、。 这种缺省层一方面带来了针对新情况的有关经验，同这种缺省层一方面带来了针对新情况的有关经验，同 时也使分类系统不至于陷入过于详细的选项之中而不时也使分类系统不至于陷入过于详细的选项之中而不 能自拔。能自拔。 促使进化中的分类系统成为处理新情况的专家的那些促使进化中的分类系统成为处理新情况的专家的那些 特征，同样善于应付某次行动的效果要等到该行动很特征，同样善于应付某次行动的效果要等到该行动很 久之后才能显示出来的情况。久之后才能显示出来的情况。 6.5 6.5 学习系统（学习系统（ls-1ls-1） 在在holland提出分类器系统之后，提出分类器系统之后，de jong和他的学生和他的学生

36、smith 也提出了一种基于遗传算法的机器学习系统也提出了一种基于遗传算法的机器学习系统ls-1。 smith所提出的这种机器学习方法是匹兹堡方法的代表。所提出的这种机器学习方法是匹兹堡方法的代表。 ls-1的个体不是表示一条规则，而是表示一个规则集合。的个体不是表示一条规则，而是表示一个规则集合。 只对规则集合进行操作，可以避开信度分配问题。只对规则集合进行操作，可以避开信度分配问题。 但是，缺乏信度分配机制也是但是，缺乏信度分配机制也是ls-1的最大缺陷。由于反馈的最大缺陷。由于反馈 信息不够充分，信息不够充分，ls-1系统的学习速度比较慢，需要进行大系统的学习速度比较慢，需要进行大 量的

37、训练才能够得到较好的效果。但是，通过学习，量的训练才能够得到较好的效果。但是，通过学习，ls-1 系统可以得到很好的性能。系统可以得到很好的性能。 ls-1学习系统的结构学习系统的结构 6.5 6.5 学习系统（学习系统（ls-1ls-1） ls是是分类器系统分类器系统和一般的和一般的产生式系统产生式系统的结合，它包含了一个的结合，它包含了一个推理引推理引 擎擎和一些和一些规则规则。 工作存储区工作存储区由一组无序的固定长度的单元构成，每个工作区单元由一组无序的固定长度的单元构成，每个工作区单元 又被细分为又被细分为信号部分信号部分和和数据部分数据部分。 产生式规则存储区产生式规则存储区由一组

38、无序的规则构成，其中，每条规则是一由一组无序的规则构成，其中，每条规则是一 个固定长度的字符串。个固定长度的字符串。规则的前件规则的前件(条件条件)由由k个固定的模式组成，个固定的模式组成， 最初的最初的i个模式与系统探测器所发出的环境消息所匹配，剩下的个模式与系统探测器所发出的环境消息所匹配，剩下的k- i个模式与工作存储区中的信号相匹配。个模式与工作存储区中的信号相匹配。 在在ls中，所有匹配的规则同时被激发。但是，若规则导致效应器中，所有匹配的规则同时被激发。但是，若规则导致效应器 产生了一个动作，则不能同时激发。产生了一个动作，则不能同时激发。 此时，系统对这些规则进行标记，并让这些被

39、标记的规则向它们此时，系统对这些规则进行标记，并让这些被标记的规则向它们 将要激活的效应器将要激活的效应器“投票投票”。然后，系统通过随机选择来决定产。然后，系统通过随机选择来决定产 生哪一个效应器动作，进行选择时每个效应器动作被选中的概率生哪一个效应器动作，进行选择时每个效应器动作被选中的概率 等于它的等于它的“得票率得票率”。 6.5 6.5 学习系统（学习系统（ls-1ls-1） 规则实例：规则实例： -1 # # 0 0 # # 0 # 1 # # x 0 # 0 # x 0 0 1 y 0 1 1 reassert(y) 学习系统中的规则前件被分为了两个部分，一个是学习系统中的规则前

40、件被分为了两个部分，一个是环环 境模式部分境模式部分“-1 # # 0 0 # # 0 #”，另一个是，另一个是工作存储区工作存储区 模式部分模式部分“1 # # x 0 # 0 # x 0 0 1 y”。 “-”代表逻辑代表逻辑“非非”运算，表示对匹配结果取反。运算，表示对匹配结果取反。 工作存储区状态工作存储区状态 6.5 6.5 学习系统（学习系统（ls-1ls-1） 工作存储区模式中的字符工作存储区模式中的字符“x”、“y”是变量，其第一是变量，其第一 次出现时要对它赋值，赋值时取相应工作存储区消息次出现时要对它赋值，赋值时取相应工作存储区消息 的数据区的值。的数据区的值。 设立数据区

41、变量使得学习系统具有了辨识数据区信息设立数据区变量使得学习系统具有了辨识数据区信息 是否相等的基本能力，更重要的是，设立数据区变量是否相等的基本能力，更重要的是，设立数据区变量 使得一条规则可以在它的前件和后件之间传递信息。使得一条规则可以在它的前件和后件之间传递信息。 对规则进行匹配时，要自左向右对规则进行扫描，首对规则进行匹配时，要自左向右对规则进行扫描，首 先对环境模式进行匹配，若可以匹配，再对工作存储先对环境模式进行匹配，若可以匹配，再对工作存储 区模式进行匹配。区模式进行匹配。 6.5 6.5 学习系统（学习系统（ls-1ls-1） 若一条规则的前件能够完全匹配，则这条规则被激发。若

42、一条规则的前件能够完全匹配，则这条规则被激发。 此时，这条规则首先在工作存储区中搜索一个可用的此时，这条规则首先在工作存储区中搜索一个可用的 空位，然后将后件中的消息粘贴到这个空位的信号区空位，然后将后件中的消息粘贴到这个空位的信号区 中。而后，这条规则将计算后件中数据区的值，再将中。而后，这条规则将计算后件中数据区的值，再将 这个值添加到空位的数据区中。这个值添加到空位的数据区中。 6.5 6.5 学习系统（学习系统（ls-1ls-1） 规则集合的重组规则集合的重组 系统对规则集合的重组通过系统对规则集合的重组通过gas进行，此处进行，此处gas使用了四种使用了四种 算子：复制、变异、交叉、

43、倒序。复制和变异算子与一般算子：复制、变异、交叉、倒序。复制和变异算子与一般 的的ga算子相同，交叉算子和倒序算子则需要进行一些修改。算子相同，交叉算子和倒序算子则需要进行一些修改。 交叉算子：因为规则集合的长度有可能不相同（包含不同交叉算子：因为规则集合的长度有可能不相同（包含不同 数目的个体），所以必须保证交叉后生成的后代有合法个数目的个体），所以必须保证交叉后生成的后代有合法个 体。体。 倒序算子：由于倒序算子：由于ls系统的规则具有一定的格式，所以在应系统的规则具有一定的格式，所以在应 用倒序操作时必须要保证生成的后代个体中的规则在语法用倒序操作时必须要保证生成的后代个体中的规则在语法

44、 上的合法性。上的合法性。 6.5 6.5 学习系统（学习系统（ls-1ls-1） 在在ls-i中，交叉通过三个步骤来进行：中，交叉通过三个步骤来进行：对齐、选择交叉点、交换对齐、选择交叉点、交换。 (1) 对齐对齐：进行对齐时首先要在两个规则集合中随机选择一个分隔符，：进行对齐时首先要在两个规则集合中随机选择一个分隔符， 然后将两个规则集合在选定的分隔符处对齐。然后将两个规则集合在选定的分隔符处对齐。 (2) 选择交叉点选择交叉点：在对齐后要选择一个交叉点，交叉点既可以选择在：在对齐后要选择一个交叉点，交叉点既可以选择在 规则之间的边界上，也可以选择在规则内部，系统用一个参数规则之间的边界上

45、，也可以选择在规则内部，系统用一个参数 pc-rb来控制交叉发生在规则边界上的概率。若交叉点在规则边来控制交叉发生在规则边界上的概率。若交叉点在规则边 界上，则可以保证规则本身不发生变化，而仅仅是规则集合发生界上，则可以保证规则本身不发生变化，而仅仅是规则集合发生 了变化；若交叉点选择在规则内部，则规则本身会发生变化，而了变化；若交叉点选择在规则内部，则规则本身会发生变化，而 且规则集合也发生了变化。且规则集合也发生了变化。 (3)(3)交换交换：在确定了交叉点后，就将两个规则集合在交叉点以后的部：在确定了交叉点后，就将两个规则集合在交叉点以后的部 分互换，这样就得到了两个新的规则集合。分互换

46、，这样就得到了两个新的规则集合。 6.5 6.5 学习系统（学习系统（ls-1ls-1） 例如：例如： a：r1 ; r2 ; r3 ; r4 ; b：r5 ; r6 ; r7 ; r8 ; r9 ; r10 ; 对齐：对齐： a： r1 ; r2 ; | r3 ; r4 ; b：r5 ; r6 ; r7 ; | r8 ; r9 ; r10 ; 6.5 6.5 学习系统（学习系统（ls-1ls-1） 交叉：交叉： a： r1 ; | r2 ; r3 ; r4 ; b：r5 ; r6 ; | r7 ; r8 ; r9 ; r10 ; a：r1：r7：r8：r9：r10： b：r5：r6：r2：r

47、3：r4： 6.5 6.5 学习系统（学习系统（ls-1ls-1） 在在ls系统中进行倒序操作时，倒序串的端点必须在规则系统中进行倒序操作时，倒序串的端点必须在规则 边界上。边界上。 r1：r2：| r3：r4：r5：r6：r7：r8：| r9：r10： r1：r2：| r8：r7：r6：r5：r4：r3：| r9：r10： 6.5 6.5 学习系统（学习系统（ls-1ls-1） ls-1的性能：的性能： smith用用ls-1来玩扑克牌游戏以检测系统的学习能力。来玩扑克牌游戏以检测系统的学习能力。 实验结果表明，实验结果表明，ls-1最后的规则集合中最后的规则集合中82的规则与的规则与 已知

48、的著名的扑克牌游戏公理是相符合的，这表明了已知的著名的扑克牌游戏公理是相符合的，这表明了 ls-1确实能够通过学习获取正确的游戏策略。确实能够通过学习获取正确的游戏策略。 组织学习方法组织学习方法 wilcox借鉴了经济学家借鉴了经济学家coase所提出的降低所提出的降低“交易代价交易代价” 的方法，提出了一种的方法，提出了一种“组织学习方法组织学习方法”，这种方法通过，这种方法通过 自适应地搜索一个规模合适的规则集合组织来提高算法自适应地搜索一个规模合适的规则集合组织来提高算法 的性能。的性能。 一、组织的增长一、组织的增长 1、交易代价、交易代价 经济领域中的经济领域中的交易代价理论交易代

49、价理论是用于解释经济某个环境中是用于解释经济某个环境中 组织机构如何形成的一种理论。由于分类器中的交互作组织机构如何形成的一种理论。由于分类器中的交互作 用可以看做是进行交易，那么，就有可能利用交易代价用可以看做是进行交易，那么，就有可能利用交易代价 理论来帮助我们在分类器系统中自动地建立组织结构。理论来帮助我们在分类器系统中自动地建立组织结构。 组织学习方法组织学习方法 交易代价是内于缺乏知识造成的，参与交易的双方都不交易代价是内于缺乏知识造成的，参与交易的双方都不 知道应当与谁进行交易，即使在交易双方会面后，双方知道应当与谁进行交易，即使在交易双方会面后，双方 也不知道对方的真实价格如何。

50、也不知道对方的真实价格如何。 2、降低交易代价的机制、降低交易代价的机制 一些经济学家指出，降低交易代价的努力导致了市场、一些经济学家指出，降低交易代价的努力导致了市场、 组织和一些其他的经济结构的出现和发展，其中，组织和一些其他的经济结构的出现和发展，其中，记录记录 交易者的声誉交易者的声誉和和生成交易组织生成交易组织是降低交易代价的两种最是降低交易代价的两种最 基本的方法。另一种减少交易代价的方法是基本的方法。另一种减少交易代价的方法是建立特殊市建立特殊市 场场以减少交易双方寻找交易对象的代价。以减少交易双方寻找交易对象的代价。 组织学习方法组织学习方法 3、组织增长模型、组织增长模型 w

51、ilcox构造了一种简单的组织增长模型构造了一种简单的组织增长模型ogm来研究如何调节组织增来研究如何调节组织增 长。长。 ogm通过让群体组成多个组织，来对个体和集合同时进行演通过让群体组成多个组织，来对个体和集合同时进行演 化，各个不同的组织为获得适应值而进行竞争，这样，组织的行为化，各个不同的组织为获得适应值而进行竞争，这样，组织的行为 就既具有个体行为的特征，也具有集合行为的特征。这个简化的就既具有个体行为的特征，也具有集合行为的特征。这个简化的 ogm主要包含以下几个组成部分：主要包含以下几个组成部分： (1)个体和组织；个体和组织； (2)适应度函数；适应度函数； (3)组织算子；

52、组织算子； (4)选择算子。选择算子。 组织学习方法组织学习方法 个体和组织个体和组织：组织中包含任意数目的个体。由于构造这个简单的：组织中包含任意数目的个体。由于构造这个简单的 ogm的目的仅仅是为了研究如何调节组织的增长，因此对个体的行的目的仅仅是为了研究如何调节组织的增长，因此对个体的行 为进行了简化，个体不产生任何实质性的动作，唯一的行为只是加为进行了简化，个体不产生任何实质性的动作，唯一的行为只是加 入或脱离一个组织，所以，组织的适应度函数也只是与它所包含的入或脱离一个组织，所以，组织的适应度函数也只是与它所包含的 个体数目有关，而不是与它所包含的个体的行为有关。个体数目有关，而不是

53、与它所包含的个体的行为有关。 适应度函数适应度函数：这个模型的目标是让个体和组织获得最大的利益，而：这个模型的目标是让个体和组织获得最大的利益，而 一个组织的好坏取决于组织中的个体的收益，所以，适应度函数可一个组织的好坏取决于组织中的个体的收益，所以，适应度函数可 以表示为各个组织的资本收益比。以表示为各个组织的资本收益比。 m mcmr f )()( 组织学习方法组织学习方法 在实验中用到了三种类型的收入函数：在实验中用到了三种类型的收入函数： （1）常量）常量r(m) = k。 （2）线性式）线性式r(m) = k0+k1m。 （3）多项式）多项式r(m) = k0+k1m+ k2m2。

54、在实验中用到了三种类型的支出函数：在实验中用到了三种类型的支出函数： （1）常量）常量c(m) = k。 （2）线性式）线性式c(m) = k0+k1m。 （3）多项式）多项式c(m) = k0+k1m+ k2m2。 通过对不同类型的收入函数和支出函数进行组合，可以得到多种不通过对不同类型的收入函数和支出函数进行组合，可以得到多种不 同的适应度函数。同的适应度函数。 组织学习方法组织学习方法 组织算子组织算子：组织算子是用于控制生成新组织的算子。它作用于一对：组织算子是用于控制生成新组织的算子。它作用于一对 被选择的组织上，并且生成一对新的组织。被选择的组织上，并且生成一对新的组织。 （1）增

55、一：这个算子从一个组织中移动一个个体到另一个组织中。）增一：这个算子从一个组织中移动一个个体到另一个组织中。 （2）减一：与增一运算相反，这个算子将一个个体从组织中转移到）减一：与增一运算相反，这个算子将一个个体从组织中转移到 一个空组织中。一个空组织中。 （3）合并：如同增一算子，这个算子从一个组织中移动全部个体到）合并：如同增一算子，这个算子从一个组织中移动全部个体到 另一个组织中，生成一个包含父代组织中所有个体的组织和一个空另一个组织中，生成一个包含父代组织中所有个体的组织和一个空 组织。组织。 （4）剪切：如同减一算子，这个算子将随机数目的个体从组织中转）剪切：如同减一算子，这个算子将

56、随机数目的个体从组织中转 移到一个空组织中。移到一个空组织中。 在实际使用时，在实际使用时，“增一减一增一减一”与与“合并剪切合并剪切”总是成对使用。总是成对使用。 组织学习方法组织学习方法 选择算子选择算子：选择算子使整个种群中的个体数目保持不变。为了达到：选择算子使整个种群中的个体数目保持不变。为了达到 这一目的，后代组织需要与父代组织进行竞争。当一个算子生成一这一目的，后代组织需要与父代组织进行竞争。当一个算子生成一 组后代组织后，选择算子在父代组织和后代组织中进行一次联赛选组后代组织后，选择算子在父代组织和后代组织中进行一次联赛选 择。具有最高适应值的组织进入下一代，其他的组织则被淘汰

57、。由择。具有最高适应值的组织进入下一代，其他的组织则被淘汰。由 于后代组织中所包含的个体数目与父代个体中包含的个体数目相等，于后代组织中所包含的个体数目与父代个体中包含的个体数目相等， 所以，种群中的个体数日保持不变。所以，种群中的个体数日保持不变。 组织学习方法组织学习方法 4、组织增长模型的实验结果、组织增长模型的实验结果 实验结果表明，组织增长模型确实能够产生最优的组织。实验结果表明，组织增长模型确实能够产生最优的组织。 使用使用“合并剪切合并剪切”算子可以缩短系统搜索到第一个最优组织的时算子可以缩短系统搜索到第一个最优组织的时 间，但是并不会缩短系统收敛的时间。间，但是并不会缩短系统收

58、敛的时间。 且当使用且当使用“合并剪切合并剪切”算子时，系统在收敛过程中会产生震荡。算子时，系统在收敛过程中会产生震荡。 而使用而使用“增一减一增一减一”算子，则系统的收敛比较平缓。改变系统的算子，则系统的收敛比较平缓。改变系统的 适应度函数将改变最优组织中所包含的个体数目，但它并不影响系适应度函数将改变最优组织中所包含的个体数目，但它并不影响系 统的收敛能力。统的收敛能力。 组织学习方法组织学习方法 二、自主组织学习二、自主组织学习 1、寄生行为、寄生行为 “桶队算法桶队算法”无法解决无法解决“寄生寄生”现象。所谓现象。所谓“寄生寄生”是是 指不做出贡献而获益。指不做出贡献而获益。smith

59、的研究结果表明，当寄生分的研究结果表明，当寄生分 类器在整个种群中的比例增加时，系统的性能将会迅速类器在整个种群中的比例增加时，系统的性能将会迅速 下降。在一个复杂的分类器系统中，想要找出寄生分类下降。在一个复杂的分类器系统中，想要找出寄生分类 器是非常复杂的一个问题。器是非常复杂的一个问题。 组织学习方法组织学习方法 社会是如何对付社会是如何对付“寄生寄生”行为呢行为呢? 最重要的方式就是通过立法最重要的方式就是通过立法 来保证正常的交易秩序，不遵守交易秩序的就会受到惩罚。除来保证正常的交易秩序，不遵守交易秩序的就会受到惩罚。除 此之外，此之外，“声誉声誉”也会起重要的作用。也会起重要的作用

60、。 可以将分类器系统看做一个市场，分类器在这个市场中交换消可以将分类器系统看做一个市场，分类器在这个市场中交换消 息和信用度。一个分类器所发出消息有可能导致另一个有用的息和信用度。一个分类器所发出消息有可能导致另一个有用的 分类器产生一个无用的动作，这时，就可以认为发出消息的分分类器产生一个无用的动作，这时，就可以认为发出消息的分 类器产生了一次寄生行为。类器产生了一次寄生行为。 因为我们希望系统能够从环境中得到最多的报酬，所以，可以因为我们希望系统能够从环境中得到最多的报酬，所以，可以 将导致系统收益偏离最大化的分类器视为寄生分类器。将导致系统收益偏离最大化的分类器视为寄生分类器。 组织学习