遗传算法与机器学习.ppt

《遗传算法与机器学习.ppt》由会员分享，可在线阅读，更多相关《遗传算法与机器学习.ppt（84页珍藏版）》请在三一文库上搜索。

1、第六章 遗传算法与机器学习,概述 分类器系统CS-1（Holland） 学习系统LS-1（Smith） 组织学习方法（Wilcox）,6.1 概 述,“学习”是一个由“未知”到“知”的过程。 “学习”的目的是获得尽可能接近真实的“知识”。 “学习”过程包含了对已有知识的“继承”和对未知知识的“探索”。 “学习”本身是一个进化的过程。 将“进化计算”应用于“学习”是自然的、合理的。,6.1 概 述,概念学习可以看作是对概念描述空间的一种启发式搜索。 概念描述空间是对原始数据（即由教师或环境向学习系统提供的某些概念的实例）使用一定推理规则得到的。 概念学习中所隐含的这种搜索机制以及它所采用的符号表

2、示方法，使得遗传算法在概念学习领域有其用武之地。 遗传算法本身固有的鲁棒性，使得基于遗传算法的概念学习系统具有更少的限制性。,6.1 概 述,1978年Holland等实现了第一个基于遗传算法的机器学习系统：一级认知系统CS-1（Cognitive System Level One）。 1986年，Holland提出桶队算法（Bucket Brigade），整个系统被称为分类器系统。 1980年，Smith提出LS-1系统。在某些重要方面，如染色体的表示、反馈方式等，LS-1和CS-1有明显差异。 1993年，De Jong和Spears提出GABIL系统，实现基于GA的概念学习。,6.1 概

3、 述,从应用角度来说，这些系统对顺序决策这类学习问题较为合适。该类问题可以描述如下：一决策主体以回复方式与一具有离散时间状态的动态系统交互，在每个时间步的开始，系统处于某确定状态。该主体依当前状态，根据决策规则，从有限的动作集中选择一个动作供动态系统执行，并进入到一个新的状态。同时向主体反馈一个补偿（payoff），其目的是发现一决策规则集以使补偿最大化。,6.2 遗传机器学习系统的结构,大多数学习系统都具有一个共同的特性：即它们都能够产生结构上的变化来提高其内部知识结构的一致性和广泛性，发现和利用一些有意义的概念，增强其在环境下完成任务的能力。,6.2 遗传机器学习系统的结构,通常，可以将遗

4、传学习系统分为两个子系统：一个基于GA的用于产生合适的结构变化的学习子系统和一个用于完成外部环境任务的任务子系统。 系统通过任务探测器从外部环境中获取环境信息，任务子系统则对这些信息进行处理，并产生一个对外部环境信息的响应，这个响应通过任务效应器作用到外部环境上。性能探测器对任务子系统对外部环境所产生的影响进行检测，并将所检测到的信息传送到学习子系统中，学习子系统利用这些信息对任务子系统的性能进行评估，并由此改变任务子系统的内部结构，以提高系统的性能。,6.2 遗传机器学习系统的结构,改变任务子系统结构的方式有三种： (1) 用GA改变一组预先定义的控制参数； (2) 改变控制任务子系统行为的

5、更加复杂的数据结构，如“议程表”； (2) 直接修改任务子系统的控制程序，,6.3 匹兹堡方法与密西根方法,将产生式系统引入遗传机器学习领域后产生了两种重要的实现方法：匹兹堡方法和密西根方法。 匹兹堡方法：将整个规则集合表示为一个个体，GA维护一个包含一定数目的候选规则集的种群。由匹兹堡（Pittsburgh）大学的De Jong和他的学生Smith所提出。 密西根方法：认为每个个体就是一条规则，而整个种群就是规则集合。由密西根（Michigan）大学的Holland和他的学生Reitman提出。 一般认为，密西根方法更加适合于在线、实时的环境，在这种环境下，系统行为上的激进的变化是不能容忍的

6、。而匹兹堡方法更适合于离线的环境，在这种环境下，更加从容不迫的搜索和更加激进的变化是可以接受的。,匹兹堡方法,首先要选择适当的表示方法。 一种表示方法将单个规则作为一个基因，而将整个分类器系统作为一个基因串（个体）。 交叉算子提供规则的新的组合方式，而变异算子则提供新的规则。 为了使得交叉算子和变异算子能够产生合法的个体，一种最简单的方法就是将所有的规则用固定长度、固定字段格式的二进制串来表示。这样，这些“IFTHEN”规则就很自然地表示为一组固定数目的待匹配的传感器模式和一个在此模式下的动作。,匹兹堡方法,也可以采用更加灵活的表示方法：用不定长的串来表示规则。这种情况下，需要对遗传算子进行修

7、改才能保证得到合法的个体。一种方式就是在串中加入“标点符号”，并通过这些“标点符号”来区分各条规则和标注规则的内部结构。 和表示方法相关的另外一个问题就是每个个体所包含的规则数目。若将规则集合看做是一个程序或者是一个知识库，那么，规定每个个体包含相同数目的规则是极不自然的。Smith成功地设计了一种GA，这种算法中的个体长度是变化的。,密西根方法,Holland认为，对于一个特定的人（认知实体）的知识（经验）的更自然的观点是将知识看做是一组规则，这组规则在与环境的交互作用下不断改变。这一组知识并不是通过每一代中进行的选择和交叉来进行演变，相反，这一组知识是在个体尽力使自己适应环境的过程中实时积

8、累的。“分类器系统”认知模型 在分类器系统中，GAs所操作的个体不是规则集合而是单独的规则。 分类器系统中最重要也是最困难的问题是信度分配问题，也就是如何将适应度值分配到各条规则上去的问题。 桶队算法,6.4 分类器系统（CS-1）,分类器系统是一种学习系统，它通过学习句法规则，来指导系统在外部环境中的行为。 分类器系统由三部分构成： (1) 规则和消息系统； (2) 信度分配系统； (3) 遗传算法。,分类器系统结构图,6.4 分类器系统（CS-1）,规则和消息系统是一种特殊的产生式系统。规则的一般形式为： IF THEN 其含义是：若满足条件C，则产生动作A。也就是说，若满足条件，则规则被

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

10、 # 0 0)、(0 0 1 0 0)、(# # 1 0 0) 冲突解决机制：分类器系统中通过一种“拍卖”的方式，让所有的候选分类器通过竞争（花钱购买）来获得被“激活”的权利。,6.4 分类器系统（CS-1）,信用分配机制桶队算法 对于分类器系统来说，衡量每个分类器的“性能”非常困难。但是，为了应用GA对分类器进行改进，又必须要对每个分类器在系统中的作用做出一个评价。 从外部环境信息到效应器响应动作之间就形成了一条响应链，这条响应链建立了外部信息到效应器响应之间的映射关系。 分类器之间以“交易”的形式传递消息，消息总是传递给“报价”最高的那个分类器。,6.4 分类器系统（CS-1）,“报价”的

11、计算： “匹配精度”的定义：匹配精度用于衡量消息与分类器的条件的“相似程度”。匹配精度越高，两者之间的相似性越强。若分类器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为一常数，称报价系数。从上述定义中可以看出，候选分类器的报价与它的适应值成正比，与匹配精度成反比。,6.4 分类器系统（CS-1）,也

12、可以将“报价”简单定义为 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）,若一个分类器一直没有被激活，它就可以一直保持它的适应值不变。但是，若一条规则一直不被激发，那么这条规则也就没有存在的必要。所以，必须采用一定的方法来防止出现这种“不思进取”的现象。一种解决方法就是，在每一个时间步对所有的分类器

13、征收“人头税”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 = cbid + ctax。,6.4 分类器系统（CS-1）,分类器重组机制遗传算法 分类器系统用GA来生成新的，可能具有更好性能的分类器，并且淘汰一部分适应值较低的分类器，以使分类器系统的整体性能不断提

14、高。 一般来说，为保证学习系统性能的稳定性，不采用完全取代的方法，而是选取一定比例的染色体来取代。 需要确定一个时间步数Tga，这个参数表示两次调用GA对分类器进行重组间的时间间隔。Tga可以任意确定。在实现时可以设置一些触发条件，当满足这些条件时，就调用GA对规则进行重组。 由于分类器中使用了三元字符表0，l，所以需要对经典变异算子进行一定的修改。当发生变异时，从原来的字符变异到另外两个字符的概率相等。即 P(0l)P(0)、P(l0)P(1)、P(0)P( 1)。,6.4 分类器系统（CS-1）,Holland给出的在分类器中采用遗传算法的核心步骤： 根据分类器的强度从分类器集合中成对挑选

15、分类器，强度越大，被选出的可能性越大； 对选中的分类器对应用交叉、变异算子，生成新的分类器； 用生成的后代替换强度最弱的那些分类器。,6.4 分类器系统（CS-1）,分类器系统中的遗传算法： begin t = 0，随机生成集合Bt，它由M个分类器组成； 计算Bt中全体分类器的平均强度Vt。对每个分类器赋予一个标准化强度值St(Cj)/Vt。 给Bt中的每个分类器Cj赋一个与其标准强度值成正比的概率，并根据Bt中的概率分布，从Bt中选取n对分类器，其中n M； 对每对分类器应用交叉算子，生成2n个新的分类器； 将Bt中的2n个强度值最低的分类器用新生成的2n个取代； t = t + 1，返回步

16、骤2。 end,6.4 分类器系统（CS-1）,生物进化的目的并不是要产生出单一的超级物种，而是要产生出彼此相互适应的物种群组成的生物圈。同理利用遗传算法的目的也不是为了控制个别规则和策略的演变，而是为了控制由许多规则构成的分类系统的演化。竞争的压力并不能孤立地筛选出最优规则，但是可以引起大系统的进化。,6.4 分类器系统（CS-1）,如果按每条规则产生的正确行动的数目对其评分，只会有利于演化出个别超级规则，而不利于寻找到一组相互之间发生有效作用的规则（系统）。所以必须改变策略，强迫这些规则去争夺对行动的控制权。每条满足条件的规则都要与其他满足条件的规则进行竞争，并且由其中最有力的规则来决定系

17、统在某种情况下的行动。如果系统的行动成功了，获胜的规则将被加强，反之，它们将被削弱。,6.4 分类器系统（CS-1）,可以把每条规则看成是关于分类系统的一种假设（hypothesis）。只有当某条规则自称与当前情况有关时，它才参加角逐。它的竞争力取决于它对解决同类问题所做的贡献大小。随着遗传算法的运作，强有力的规则发生组配，形成融合上一代基因块为一体的后代规则，这些后代取代了最弱小的规则，它们相当于一些似乎可能但还未经证实的假设。,6.4 分类器系统（CS-1）,规则之间的竞争为分类系统应付层出不穷的新情况提供了巧妙的手段。如果分类系统具有响应某种情况的有力规则，就等于分类系统的某些假没已经被

18、证实。只有在满足某些条件的有力规则不存在的情况下，也就是只有当分类系统不知所措的时候，那些生来就比上一代弱小的后代规则才有出头之日，可能赢得竞争，并影响分类系统的行为。如果它们的行为对于分类系统有所帮助，它们便生存下去，否则，它们很快就被取代。所以，在分类系统很有经验的情况中，后代并不会干涉分类系统的行为，它只是作为关于在新情况下应该如何行动的假设，在一旁静静地等候着。,6.4 分类器系统（CS-1）,增加这样的竞争对于分类系统的演化有很大的帮助。分类系统在开始运行的初期，先发展出条件简单的规则，即那些把很多情况当作相同情况对待的规则。分类系统把这些规则作为缺省规则。在缺乏更详细信息的情况下，

19、用它们来说明分类系统应采取的某种行动。不过，缺省规则只能作为肤浅的判断，因为它们经常出错，因而强度得不到加强。随着分类系统获得经验，繁殖和交叉使得更复杂和更专用的规则得到发展，这些规则迅速得到增强，很快成为各种特殊情况下分类系统行为的主宰。,6.4 分类器系统（CS-1）,最终分类系统发展成为一种层次结构：处于下层的例外规则层处理大多数情况；当详细规则无法满足情况的条件时，处于层次结构上层的缺省规则就发挥作用。这种缺省层一方面带来了针对新情况的有关经验，同时也使分类系统不至于陷入过于详细的选项之中而不能自拔。 促使进化中的分类系统成为处理新情况的专家的那些特征，同样善于应付某次行动的效果要等到

20、该行动很久之后才能显示出来的情况。,6.5 学习系统（LS-1）,在Holland提出分类器系统之后，De Jong和他的学生Smith也提出了一种基于遗传算法的机器学习系统LS-1。Smith所提出的这种机器学习方法是匹兹堡方法的代表。 LS-1的个体不是表示一条规则，而是表示一个规则集合。 只对规则集合进行操作，可以避开信度分配问题。 但是，缺乏信度分配机制也是LS-1的最大缺陷。由于反馈信息不够充分，LS-1系统的学习速度比较慢，需要进行大量的训练才能够得到较好的效果。但是，通过学习，LS-1系统可以得到很好的性能。,LS-1学习系统的结构,6.5 学习系统（LS-1）,LS是分类器系统

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

22、效应器动作被选中的概率等于它的“得票率”。,6.5 学习系统（LS-1）,规则实例： -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”。 “-”代表逻辑“非”运算，表示对匹配结果取反。,工作存储区状态,6.5 学习系统（LS-1）,工作存储区模式中的字符“X”、“Y”是变量，其第一次出现时要对它赋值，赋值时取相应工作存储区消息的数据区的值。

23、设立数据区变量使得学习系统具有了辨识数据区信息是否相等的基本能力，更重要的是，设立数据区变量使得一条规则可以在它的前件和后件之间传递信息。 对规则进行匹配时，要自左向右对规则进行扫描，首先对环境模式进行匹配，若可以匹配，再对工作存储区模式进行匹配。,6.5 学习系统（LS-1）,若一条规则的前件能够完全匹配，则这条规则被激发。 此时，这条规则首先在工作存储区中搜索一个可用的空位，然后将后件中的消息粘贴到这个空位的信号区中。而后，这条规则将计算后件中数据区的值，再将这个值添加到空位的数据区中。,6.5 学习系统（LS-1）,规则集合的重组 系统对规则集合的重组通过GAs进行，此处GAs使用了四种

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

25、以选择在规则内部，系统用一个参数Pc-rb来控制交叉发生在规则边界上的概率。若交叉点在规则边界上，则可以保证规则本身不发生变化，而仅仅是规则集合发生了变化；若交叉点选择在规则内部，则规则本身会发生变化，而且规则集合也发生了变化。 交换：在确定了交叉点后，就将两个规则集合在交叉点以后的部分互换，这样就得到了两个新的规则集合。,6.5 学习系统（LS-1）,例如： A： R1 ; R2 ; R3 ; R4 ; B： R5 ; R6 ; R7 ; R8 ; R9 ; R10 ; 对齐： A： R1 ; R2 ; | R3 ; R4 ; B： R5 ; R6 ; R7 ; | R8 ; R9 ; R1

26、0 ;,6.5 学习系统（LS-1）,交叉： A： R1 ; | R2 ; R3 ; R4 ; B：R5 ; R6 ; | R7 ; R8 ; R9 ; R10 ; A：R1：R7：R8：R9：R10： B：R5：R6：R2：R3：R4：,6.5 学习系统（LS-1）,在LS系统中进行倒序操作时，倒序串的端点必须在规则边界上。 R1：R2：| R3：R4：R5：R6：R7：R8：| R9：R10： R1：R2：| R8：R7：R6：R5：R4：R3：| R9：R10：,6.5 学习系统（LS-1）,LS-1的性能： Smith用LS-1来玩扑克牌游戏以检测系统的学习能力。实验结果表明，LS-1

27、最后的规则集合中82的规则与已知的著名的扑克牌游戏公理是相符合的，这表明了LS-1确实能够通过学习获取正确的游戏策略。,组织学习方法,Wilcox借鉴了经济学家Coase所提出的降低“交易代价”的方法，提出了一种“组织学习方法”，这种方法通过自适应地搜索一个规模合适的规则集合组织来提高算法的性能。 一、组织的增长 1、交易代价 经济领域中的交易代价理论是用于解释经济某个环境中组织机构如何形成的一种理论。由于分类器中的交互作用可以看做是进行交易，那么，就有可能利用交易代价理论来帮助我们在分类器系统中自动地建立组织结构。,组织学习方法,交易代价是内于缺乏知识造成的，参与交易的双方都不知道应当与谁进

28、行交易，即使在交易双方会面后，双方也不知道对方的真实价格如何。 2、降低交易代价的机制 一些经济学家指出，降低交易代价的努力导致了市场、组织和一些其他的经济结构的出现和发展，其中，记录交易者的声誉和生成交易组织是降低交易代价的两种最基本的方法。另一种减少交易代价的方法是建立特殊市场以减少交易双方寻找交易对象的代价。,组织学习方法,3、组织增长模型 Wilcox构造了一种简单的组织增长模型OGM来研究如何调节组织增长。 OGM通过让群体组成多个组织，来对个体和集合同时进行演化，各个不同的组织为获得适应值而进行竞争，这样，组织的行为就既具有个体行为的特征，也具有集合行为的特征。这个简化的OGM主要

29、包含以下几个组成部分： (1)个体和组织； (2)适应度函数； (3)组织算子； (4)选择算子。,组织学习方法,个体和组织：组织中包含任意数目的个体。由于构造这个简单的OGM的目的仅仅是为了研究如何调节组织的增长，因此对个体的行为进行了简化，个体不产生任何实质性的动作，唯一的行为只是加入或脱离一个组织，所以，组织的适应度函数也只是与它所包含的个体数目有关，而不是与它所包含的个体的行为有关。 适应度函数：这个模型的目标是让个体和组织获得最大的利益，而一个组织的好坏取决于组织中的个体的收益，所以，适应度函数可以表示为各个组织的资本收益比。,组织学习方法,在实验中用到了三种类型的收入函数： （1）

30、常量R(M) = K。 （2）线性式R(M) = K0+K1M。 （3）多项式R(M) = K0+K1M+ K2M2。 在实验中用到了三种类型的支出函数： （1）常量C(M) = K。 （2）线性式C(M) = K0+K1M。 （3）多项式C(M) = K0+K1M+ K2M2。 通过对不同类型的收入函数和支出函数进行组合，可以得到多种不同的适应度函数。,组织学习方法,组织算子：组织算子是用于控制生成新组织的算子。它作用于一对被选择的组织上，并且生成一对新的组织。 （1）增一：这个算子从一个组织中移动一个个体到另一个组织中。 （2）减一：与增一运算相反，这个算子将一个个体从组织中转移到一个空组

31、织中。 （3）合并：如同增一算子，这个算子从一个组织中移动全部个体到另一个组织中，生成一个包含父代组织中所有个体的组织和一个空组织。 （4）剪切：如同减一算子，这个算子将随机数目的个体从组织中转移到一个空组织中。 在实际使用时，“增一减一”与“合并剪切”总是成对使用。,组织学习方法,选择算子：选择算子使整个种群中的个体数目保持不变。为了达到这一目的，后代组织需要与父代组织进行竞争。当一个算子生成一组后代组织后，选择算子在父代组织和后代组织中进行一次联赛选择。具有最高适应值的组织进入下一代，其他的组织则被淘汰。由于后代组织中所包含的个体数目与父代个体中包含的个体数目相等，所以，种群中的个体数日保

32、持不变。,组织学习方法,4、组织增长模型的实验结果 实验结果表明，组织增长模型确实能够产生最优的组织。 使用“合并剪切”算子可以缩短系统搜索到第一个最优组织的时间，但是并不会缩短系统收敛的时间。 且当使用“合并剪切”算子时，系统在收敛过程中会产生震荡。 而使用“增一减一”算子，则系统的收敛比较平缓。改变系统的适应度函数将改变最优组织中所包含的个体数目，但它并不影响系统的收敛能力。,组织学习方法,二、自主组织学习 1、寄生行为 “桶队算法”无法解决“寄生”现象。所谓“寄生”是指不做出贡献而获益。Smith的研究结果表明，当寄生分类器在整个种群中的比例增加时，系统的性能将会迅速下降。在一个复杂的分

33、类器系统中，想要找出寄生分类器是非常复杂的一个问题。,组织学习方法,社会是如何对付“寄生”行为呢? 最重要的方式就是通过立法来保证正常的交易秩序，不遵守交易秩序的就会受到惩罚。除此之外，“声誉”也会起重要的作用。 可以将分类器系统看做一个市场，分类器在这个市场中交换消息和信用度。一个分类器所发出消息有可能导致另一个有用的分类器产生一个无用的动作，这时，就可以认为发出消息的分类器产生了一次寄生行为。 因为我们希望系统能够从环境中得到最多的报酬，所以，可以将导致系统收益偏离最大化的分类器视为寄生分类器。,组织学习方法,2、记忆深度向题 Smith以“记忆深度问题”为例来考察分类器系统如何解决要求记

34、忆深度大于零（非“刺激响应”）的问题。 记忆深度问题是一个要求系统根据以前的状态来决定当前采取的动作的问题。 对于记忆深度问题来说，最关键的一点是，要求分类器同时使用环境状态和内部消息来确定下一步动作。,组织学习方法,一阶记忆深度向题：一阶记忆深度问题要求系统能够“记住”外部环境在前一时刻的状态。分类器系统将外部环境在前一时刻的状态存储在内部消息队列中，这样就使得系统可以“记住”外部环境在前一时刻的状态。 一个分类器只有同时匹配外部环境的当前状态(环境消息)和前一时刻的状态(内部消息)才能够被激发。 分类器被激发后将粘贴一条消息到内部消息队列中，并且对外部环境产生一个动作。,组织学习方法,外部

35、环境含有两个状态变量，一个用于保存前一时刻的状态，另一个是当前状态。 外部环境每次随机地生成一个新的当前状态，然后将原来的当前状态变成前一时刻状态。 若分类器系统所产生的动作消息与前一时刻状态相同，则分类器系统将从外部环境中得到一个报偿。,组织学习方法,环境状态有四个取值：“a”、“b”、“c”、“d”，相应地，分类器消息也有四个取值：“A”、“B”、“C”、“D”。一个典型的分类器为 IF AB THEN AB 它表示“若外部环境状态为A，内部消息为B，则将A粘贴到内部消息队列中，并对环境发送动作消息B”。由于外部环境的前一时刻状态为“b”，而发送到外部环境中的动作消息为“B”，所以分类器系

36、统将从外部环境中得到一个报偿。,显然，由于外部环境和内部消息各有四个取值，那么，分类器总共有16个独立条件部分，同理，分类器总共有16个独立的动作部分，所以总共有256个不同的分类器。对于这个问题，理想的分类器系统只需要16条规则。,组织学习方法,Smith的研究结果表明，系统中存在三种类型的寄生分类器： 第一类寄生分类器：这类分类器可以产生正确的内部消息，但是不能够向外部环境发送正确的动作稍息。 第二类寄生分类器：这类分类器不能够产生正确的内部消息，但是能够向外部环境发送正确的动作消息。 第三类寄生分类器：这类分类器既不能产生正确的内部消息，又不能够向外部环境发送正确的动作稍息。,为了观察寄

37、生分类器对系统性能所造成的影响，Smith进行了一组实验。实验采用了一个简单分类器系统（SCS）来求解上述一阶记忆深度问题。由于实验的目的是为了检验寄生分类器对分类器系统的影响所以实验中SCS没有应用GAs来对规则进行演化。实验中SCS的分类器集合是预先设定的，其中都包含16个理想的分类器。,组织学习方法,实验1：16个理想分类器。 实验2：16个理想分类器加上1个第二类寄生分类器。 实验3：16个理想分类器加上8个第二类寄生分类器。 实验4：16个理想分类器加上5个第一类寄生分类器，6个第二类寄生分类器，5个第三类寄生分类器。 实验5：16个理想分类器加上16个第二类寄生分类器。 实验6：3

38、2个理想分类器加上32个第二类寄生分类器。 实验7：16个理想分类器加上32个第二类寄生分类器。,组织学习方法,设计以上这7个实验主要是为了研究三个因素对系统性能的影响： (1)寄生分类器比例：系统中寄生分类器数目与理想分类器数目的比值。它代表了系统中的“噪声”大小。 (2)寄生类型：三种不同类型的寄生分类器会对系统的性能产生不同的影响。 (3)尺度：系统中的分类器数目。,组织学习方法,Smith用了三个指标来衡量各次实验中分类器的性能： (1)正确率：系统发送到外部环境的动作消息获得报偿的百分比。它衡量一个分类器系统使其收入实现最大化的能力。 (2)错误次数：实验结束后分类器系统中适应值大于

39、1.0的寄生分类器数日。若系统收敛，则错误次数实际上是指成功地欺骗了系统的寄生分类器数目。若系统不收敛，则这个指标没有明确的含义。 (3)收敛时间：分类器系统的正确率收敛到一个稳态值所需要的时间。,增加寄生分类器的比例会降低系统的性能o 第二类寄生分类器比第一、三类寄生分类器更不容易被系统发现，更容易成为系统稳态工作集合小的一部分。 增加分类器的数目会降低系统的收敛能力。,组织学习方法,3、组织分类器系统 在前面的实验中可以看出，SCS不能有效地识别出寄生分类器。 Wilcox提出可以通过“声誉”来识别寄生分类器。 Wilcox认为，声誉就是关于分类器以前的性能的信息。 Wilcox指出，传统

40、的分类器系统只使用一个单独的适应值来估计分类器的性能。若能够在不同的时间尺度上使用不同的值来表示一个分类器的性能，将有可能使得系统更容易识别出寄生分类器的欺骗行为。,组织学习方法,在研究分类器系统时，可以将分类器的适应值看做是一种对于分类器未来性能的预测。 冲突解决机制使用适应值来确定哪一个分类器被激发，并通过斗链式算法来对适应值进行更新。 一个分类器的适应值是一种显示这个分类器为系统带来多少收益的声誉值。所以，冲突解决机制利用适应值来降低它所选择的分类器不能使得系统收益最大化的风险。但是，当系统发生变化时，冲突解决机制就需要探索其他的选择。,组织学习方法,在这种情况下，冲突解决机制有一个在当

41、前形势下查找最佳分类器的短期目标，而同时分类器系统又有一个寻找使得系统本身获得最大收益的分类器集合的长期目标。 在理想状况下，分类器应当选择一个既具有很好的长期性能，又非常适应当前形势的分类器。 不幸的是，适应值所反映的是分类器的长期性能，不能很好地反应分类器在某一时期内的短期性能。在这种情况下，冲突解决机制可能会选择一个并不适应当前形势的分类器。,组织学习方法,针对这种情况，Wilcox提出可以使用两种不同的声誉值：短期声誉(STR)和长期声誉(LTR)。 每一个组织和组织中的个体都既有一个短期声誉值，又有一个长期声誉值。STR代表个体或组织在最近一段时间内表现出的性能，而LTR则代表个体或

42、组织从系统远行开始直到目前为止表现出的性能。 在组织内部，冲突解决机制通过分类器的STR来选择被激发的分类器，最近一段时间表现出性能最好的分类器被激发。,组织学习方法,同时，组织使用分类器LTR来决定是否应当让这个分类器保留在组织中，在整个系统运行期间表现出性能不佳的分类器将被淘汰，LTR使得系统能够生成性能更好的组织。这样，冲突解决机制就既能够满足短期目标，又能够通过LTR来保证冲突机制的贪婪搜索策略不会降低系统的长期效益。,组织学习方法,在系统中，冲突解决机制通过组织的LTR来决定哪一个组织中的分类器可以向外部环境产生一个动作，在整个系统运行期间表现出性能最好的组织，将获得向外部环境产生一

43、个动作的权力。 同时，系统通过组织的STR来决定是否应当增加一个组织中的分类器数目，最近一段时间内表现出高性能的组织将可以增加它所包含的个体数目。 基于这种思想，Wilcox提出了组织分类器系统OCS。OCS将分类器系统和前面所讨论的组织增长模型结合在一起，使得系统可以自主地形成组织结构。,组织学习方法,OCS的主要目的是，要让分类器系统更有效地识别出寄生分类器，从而提高系统性能。 OCS由以下三部分组成： (1)产生式系统； (2)信度分配机制和冲突解决机制； (3)组织增长模块。,OCS的结构,组织学习方法,(1) 产生式系统 OCS与匹兹堡方法的相似之处在于OCS中的个体都是分类器集合。

44、不同之处有两点：a) OCS中的分类器集合可以含有不同数目的规则；b) OCS中的分类器集合是相互作用的。 OCS与密西根方法的相似之处在于，OCS中也具有内部消息队列，分类器可以向消息队列粘贴消息。不同的是，OCS中每个组织都有自己的内部消息队列，分类器只能将消息粘贴到自己所属组织的内部消息队列上。,组织学习方法,(2) 信度分配机制 信度分配机制将信度分别分配到组织和个体上。冲突解决机制则利用LTR和STR来调节分类器之间的相互作用和组织之间的相互作用。与密西根方法不同的是，OCS中每个组织和个体都有两个声誉值：LTR和STR。分类器的声誉值可能来源于外部环境的报偿，也可能来源于购买它所粘

45、贴的内部消息的其他分类器。,组织学习方法,(3) 冲突解决机制 冲突解决机制使用LTR和STR来解决冲突。当一个组织中有多个分类器可以激发时，组织选择STR最大的分类器被激发；而当系统内有多个组织可以向外部环境发送一条动作消息时，系统选择LTR最大的组织向外部环境发送一条动作消息。组织通过选择STR最大的分类器来使得自己的收益最大化，而系统则通过选择LTR最大的分类器来使得自己的收益在整个生命周期中达到最大化。,组织学习方法,(4) 组织增长模块 组织增长模块控制组织所包含的个体数目。组织增长模块通过应用组织规模调整算子来改变组织中分类器的数目。 有两种典型的组织规模调整算子：增长算子和收缩算

46、子。 OCS每次随机地从这两个算子中选择一个算子，对当前种群中的组织进行操作。增长算子增加组织中的分类器数目，收缩算子减少组织中的分类器数目。,组织学习方法,增长算子与前面所提到的“增一”算子相似，每次从一个组织中移动一个分类器到另一个组织中。 记被增长的组织为O1，增长算子首先从系统中所有的分类器中选择一个O1中没有的分类器，并将这个分类器加入到O1中。将加入了一个分类器的被增长组织记为O1，将贡献这个分类器的组织记为O2。然后，增长算于计算O1的适应值，并与O2的适应值进行比较，若O1被增长组织的适应值大于O2的适应值，则保留O1 ，否则将增加的分类器还给O2。,组织学习方法,在选择O1中

47、没有的分类器时有两种方法：第一种方法是随机增长法，这种方法随机地从候选分类器中选择一个分类器；第二种方法是纵向增长法，这种方法需要每个组织建立一个分类器的索引值列表，这个列表中的每一个索引值所对应的分类器所发出的消息，都可以激发这个组织中的某个分类器。每次进行选择时，就从这个列表上选择一个分类器。,组织学习方法,收缩算子可能从一个组织中删除任意数目的分类器。这个算子首先设定一个接近于零的常数c为阈值。当对一个组织运用收缩算子时，所有LTR低于这个阈值的分类器都将被删除。所有这些被删除的分类器组成一个新的组织。 为了检验OCS的性能，Wilcox用OCS来求解了前面所讨论的一阶记忆深度问题。 W

48、ilcox总共进行了7个不同的实验。与Smith相似， Wilcox的OCS在实验中也没有使用GAs来对分类器进行演化，而是使用一个预先设定的分类器集合。这7个实验与Smith所进行的7个实验相同：,(1)一般来说，当寄生分类器比例增加时，OCS相对于SCS具有更高的正确率，但是，OCS的收敛时间则远远长于SCS。 (2)第二种类型的寄生分类器对于OCS和SCS来说，都比其他两种类型的寄生分类器更加难于识别。当使用纵向OCS时，系统性能明显优于SCS，而当使用随机OCS时，系统性能略低于SCS。 (3)当增加系统中分类器数目时，OCS受到的影响不大，性能明显优于SCS，尤其当使用较长的周期时，效果更加明显。,组织学习方法,(4) 组织增长模块 组织增长模块控制组织所包含的个体数目。组织增长模块通过应用组织规模调整算子来改变组织中分类器的数目。 有两种典型的组织规模调整算子：增长算子和收缩算子。 OCS每次随机地从这两个算子中选择一个算子，对当前种群中的组织进行操作。增长算子增加组织中的分类器数目，收缩算子减少组织中的分类器数目。,