遗传算法与机器学习学习培训课件.ppt

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

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

3、习系统具有更少的限制性。念学习系统具有更少的限制性。6.1 概概 述述1978年年Holland等实现了第一个基于遗传算法的机器学等实现了第一个基于遗传算法的机器学习系统：一级认知系统习系统：一级认知系统CS-1（Cognitive System Level One）。）。1986年，年，Holland提出桶队算法（提出桶队算法（Bucket Brigade），），整个系统被称为分类器系统。整个系统被称为分类器系统。1980年，年，Smith提出提出LS-1系统。在某些重要方面，如染系统。在某些重要方面，如染色体的表示、反馈方式等，色体的表示、反馈方式等，LS-1和和CS-1有明显差异。有明显

4、差异。1993年，年，De Jong和和Spears提出提出GABIL系统，实现基于系统，实现基于GA的概念学习。的概念学习。6.1 概概 述述从应用角度来说，这些系统对从应用角度来说，这些系统对顺序决策顺序决策这类学习问题这类学习问题较为合适。该类问题可以描述如下：一决策主体以回较为合适。该类问题可以描述如下：一决策主体以回复方式与一具有离散时间状态的动态系统交互，在每复方式与一具有离散时间状态的动态系统交互，在每个时间步的开始，系统处于某确定状态。该主体依当个时间步的开始，系统处于某确定状态。该主体依当前状态，根据决策规则，从有限的动作集中选择一个前状态，根据决策规则，从有限的动作集中选择

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

6、能力。6.2 遗传机器学习系统的结构遗传机器学习系统的结构通常，可以将遗传学习系统分为两个子系统：一个基于通常，可以将遗传学习系统分为两个子系统：一个基于GA的用于产生合适的结构变化的的用于产生合适的结构变化的学习子系统学习子系统和一个用于完成和一个用于完成外部环境任务的外部环境任务的任务子系统任务子系统。系统通过系统通过任务探测器任务探测器从外部环境中获取环境信息，从外部环境中获取环境信息，任务子任务子系统系统则对这些信息进行处理，并产生一个对外部环境信息则对这些信息进行处理，并产生一个对外部环境信息的响应，这个响应通过的响应，这个响应通过任务效应器任务效应器作用到外部环境上。作用到外部环境

7、上。性性能探测器能探测器对任务子系统对外部环境所产生的影响进行检测，对任务子系统对外部环境所产生的影响进行检测，并将所检测到的信息传送到并将所检测到的信息传送到学习子系统学习子系统中，学习子系统利中，学习子系统利用这些信息对任务子系统的性能进行评估，并由此改变任用这些信息对任务子系统的性能进行评估，并由此改变任务子系统的内部结构，以提高系统的性能。务子系统的内部结构，以提高系统的性能。6.2 遗传机器学习系统的结构遗传机器学习系统的结构改变任务子系统结构的方式有三种：改变任务子系统结构的方式有三种：(1)用用GA改变一组预先定义的控制参数；改变一组预先定义的控制参数；(2)改变控制任务子系统行

8、为的更加复杂的数据结构，如改变控制任务子系统行为的更加复杂的数据结构，如“议程表议程表”；(2)直接修改任务子系统的控制程序，直接修改任务子系统的控制程序，6.3 匹兹堡方法与密西根方法匹兹堡方法与密西根方法 将产生式系统引入遗传机器学习领域后产生了两种重要的将产生式系统引入遗传机器学习领域后产生了两种重要的实现方法：实现方法：匹兹堡方法匹兹堡方法和和密西根方法密西根方法。匹兹堡方法：匹兹堡方法：将整个规则集合表示为一个个体，将整个规则集合表示为一个个体，GA维护一维护一个包含一定数目的候选规则集的种群。由匹兹堡个包含一定数目的候选规则集的种群。由匹兹堡（Pittsburgh）大学的）大学的D

9、e Jong和他的学生和他的学生Smith所提出。所提出。密西根方法：密西根方法：认为每个个体就是一条规则，而整个种群就认为每个个体就是一条规则，而整个种群就是规则集合。由密西根（是规则集合。由密西根（Michigan）大学的）大学的Holland和他的和他的学生学生Reitman提出。提出。一般认为，密西根方法更加适合于在线、实时的环境，在一般认为，密西根方法更加适合于在线、实时的环境，在这种环境下，系统行为上的激进的变化是不能容忍的。而这种环境下，系统行为上的激进的变化是不能容忍的。而匹兹堡方法更适合于离线的环境，在这种环境下，更加从匹兹堡方法更适合于离线的环境，在这种环境下，更加从容不迫

10、的搜索和更加激进的变化是可以接受的。容不迫的搜索和更加激进的变化是可以接受的。匹兹堡方法匹兹堡方法首先要选择适当的表示方法。首先要选择适当的表示方法。一种表示方法将单个规则作为一个基因，而将整个分类器一种表示方法将单个规则作为一个基因，而将整个分类器系统作为一个基因串（个体）。系统作为一个基因串（个体）。交叉算子提供规则的新的组合方式，而变异算子则提供新交叉算子提供规则的新的组合方式，而变异算子则提供新的规则。的规则。为了使得交叉算子和变异算子能够产生合法的个体，一种为了使得交叉算子和变异算子能够产生合法的个体，一种最简单的方法就是将所有的规则用固定长度、固定字段格最简单的方法就是将所有的规则

11、用固定长度、固定字段格式的二进制串来表示。这样，这些式的二进制串来表示。这样，这些“IFTHEN”规则就很规则就很自然地表示为一组固定数目的待匹配的传感器模式和一个自然地表示为一组固定数目的待匹配的传感器模式和一个在此模式下的动作。在此模式下的动作。匹兹堡方法匹兹堡方法也可以采用更加灵活的表示方法：用不定长的串来表示规也可以采用更加灵活的表示方法：用不定长的串来表示规则。这种情况下，需要对遗传算子进行修改才能保证得到则。这种情况下，需要对遗传算子进行修改才能保证得到合法的个体。一种方式就是在串中加入合法的个体。一种方式就是在串中加入“标点符号标点符号”，并，并通过这些通过这些“标点符号标点符号

12、”来区分各条规则和标注规则的内部来区分各条规则和标注规则的内部结构。结构。和表示方法相关的另外一个问题就是每个个体所包含的规和表示方法相关的另外一个问题就是每个个体所包含的规则数目。若将规则集合看做是一个程序或者是一个知识库，则数目。若将规则集合看做是一个程序或者是一个知识库，那么，规定每个个体包含相同数目的规则是极不自然的。那么，规定每个个体包含相同数目的规则是极不自然的。Smith成功地设计了一种成功地设计了一种GA，这种算法中的个体长度是变，这种算法中的个体长度是变化的。化的。密西根方法密西根方法Holland认为，对于一个特定的人（认知实体）的知识（经认为，对于一个特定的人（认知实体）

13、的知识（经验）的更自然的观点是将知识看做是一组规则，这组规则验）的更自然的观点是将知识看做是一组规则，这组规则在与环境的交互作用下不断改变。这一组知识并不是通过在与环境的交互作用下不断改变。这一组知识并不是通过每一代中进行的选择和交叉来进行演变，相反，这一组知每一代中进行的选择和交叉来进行演变，相反，这一组知识是在个体尽力使自己适应环境的过程中实时积累的。识是在个体尽力使自己适应环境的过程中实时积累的。“分类器系统分类器系统”认知模型认知模型在分类器系统中，在分类器系统中，GAs所操作的个体不是规则集合而是单所操作的个体不是规则集合而是单独的规则。独的规则。分类器系统中最重要也是最困难的问题是

14、信度分配问题，分类器系统中最重要也是最困难的问题是信度分配问题，也就是如何将适应度值分配到各条规则上去的问题。也就是如何将适应度值分配到各条规则上去的问题。桶队算法桶队算法6.4 分类器系统（分类器系统（CS-1）分类器系统是一种学习系统，它通过学习句法规则，分类器系统是一种学习系统，它通过学习句法规则，来指导系统在外部环境中的行为。来指导系统在外部环境中的行为。分类器系统由三部分构成：分类器系统由三部分构成：(1)规则和消息系统；规则和消息系统；(2)信度分配系统；信度分配系统；(3)遗传算法。遗传算法。分类器系统结构图分类器系统结构图6.4 分类器系统（分类器系统（CS-1）规则和消息系统

15、是一种特殊的产生式系统。规则的一规则和消息系统是一种特殊的产生式系统。规则的一般形式为：般形式为：IF THEN 其含义是：若满足条件其含义是：若满足条件C，则产生动作，则产生动作A。也就是说，。也就是说，若满足条件，则规则被若满足条件，则规则被“激发激发”。分类器所产生的动作，实际上也是一种消息，它可能分类器所产生的动作，实际上也是一种消息，它可能会使得效应器产生一个动作，也有可能激发另一个分会使得效应器产生一个动作，也有可能激发另一个分类器，还有可能不产生任何作用。类器，还有可能不产生任何作用。6.4 分类器系统（分类器系统（CS-1）分类器系统中采用长度一定的字符串表示一条规则分类器系统

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

17、下条件都与它相匹配：配：(0 0#0 0)、(0 0 1 0 0)、(#1 0 0)冲突解决机制：分类器系统中通过一种冲突解决机制：分类器系统中通过一种“拍卖拍卖”的方式，的方式，让所有的候选分类器通过竞争（花钱购买）来获得被让所有的候选分类器通过竞争（花钱购买）来获得被“激激活活”的权利。的权利。6.4 分类器系统（分类器系统（CS-1）信用分配机制信用分配机制桶队算法桶队算法对于分类器系统来说，衡量每个分类器的对于分类器系统来说，衡量每个分类器的“性能性能”非常困非常困难。但是，为了应用难。但是，为了应用GA对分类器进行改进，又必须要对每对分类器进行改进，又必须要对每个分类器在系统中的作用

18、做出一个评价。个分类器在系统中的作用做出一个评价。从外部环境信息到效应器响应动作之间就形成了一条响应从外部环境信息到效应器响应动作之间就形成了一条响应链，这条响应链建立了外部信息到效应器响应之间的映射链，这条响应链建立了外部信息到效应器响应之间的映射关系。关系。分类器之间以分类器之间以“交易交易”的形式传递消息，消息总是传递给的形式传递消息，消息总是传递给“报价报价”最高的那个分类器。最高的那个分类器。6.4 分类器系统分类器系统（CS-1）“报价报价”的计算的计算：“匹配精度匹配精度”的定义：匹配精度用于衡量消息与分类器的条件的的定义：匹配精度用于衡量消息与分类器的条件的“相似程度相似程度”

19、。匹配精度越高，两者之间的相似性越强。若分类。匹配精度越高，两者之间的相似性越强。若分类器器C C的激发条件与消息的激发条件与消息m m相匹配，则匹配精度可以定义为相匹配，则匹配精度可以定义为p p(C,mC,m)=1/1/R R(C C)其中，其中，R(C)R(C)代表代表C C的激发条件中通配符的激发条件中通配符“#”#”的数目。的数目。假定一个分类器假定一个分类器C在在t时刻的适应值为时刻的适应值为Strength(C,t)，那么，当它，那么，当它成为候选分类器时，它给出的成为候选分类器时，它给出的“报价报价”为为Bid(C,t)=cbid*R(C)*Strength(C,t)其中，其中

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

21、trength(C,t+1)=Strength(C,t)-Bid(C,t)+I(t)6.4 分类器系统（分类器系统（CS-1）若一个分类器一直没有被激活，它就可以一直保持它的适应值不若一个分类器一直没有被激活，它就可以一直保持它的适应值不变。但是，若一条规则一直不被激发，那么这条规则也就没有存变。但是，若一条规则一直不被激发，那么这条规则也就没有存在的必要。所以，必须采用一定的方法来防止出现这种在的必要。所以，必须采用一定的方法来防止出现这种“不思进不思进取取”的现象。一种解决方法就是，在每一个时间步对所有的分类的现象。一种解决方法就是，在每一个时间步对所有的分类器征收器征收“人头税人头税”T

22、(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来生成新的，可能具有更好性能的分类器，并来生成新的，可能具有更好性能的分类器，并且淘汰一部分适应值

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

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

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

26、中的每个分类器Cj赋一个与其标准强度值成正比的概率，并赋一个与其标准强度值成正比的概率，并根据根据Bt中的概率分布，从中的概率分布，从Bt中选取中选取n对对分类器，其中分类器，其中n M；(4)对每对分类器应用交叉算子，生成对每对分类器应用交叉算子，生成2n个新的分类器；个新的分类器；(5)将将Bt中的中的2n个强度值最低的分类器用新生成的个强度值最低的分类器用新生成的2n个取代；个取代；(6)t=t+1，返回步骤，返回步骤2。(7)end6.4 分类器系统（分类器系统（CS-1）生物进化的目的并不是要产生出单一的超级物种，生物进化的目的并不是要产生出单一的超级物种，而是要产生出彼此相互适应的

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

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

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

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

31、争，并影响分类系统的行为。如果它们的行为对于分类系统有所帮助，它们便生存下去，果它们的行为对于分类系统有所帮助，它们便生存下去，否则，它们很快就被取代。所以，在分类系统很有经验的否则，它们很快就被取代。所以，在分类系统很有经验的情况中，后代并不会干涉分类系统的行为，它只是作为关情况中，后代并不会干涉分类系统的行为，它只是作为关于在新情况下应该如何行动的假设，在一旁静静地等候着。于在新情况下应该如何行动的假设，在一旁静静地等候着。6.4 分类器系统（分类器系统（CS-1）增加这样的竞争对于分类系统的演化有很大的帮助。增加这样的竞争对于分类系统的演化有很大的帮助。分类系统在开始运行的初期，先发展出

32、条件简单的规分类系统在开始运行的初期，先发展出条件简单的规则，即那些把很多情况当作相同情况对待的规则。分则，即那些把很多情况当作相同情况对待的规则。分类系统把这些规则作为缺省规则。在缺乏更详细信息类系统把这些规则作为缺省规则。在缺乏更详细信息的情况下，用它们来说明分类系统应采取的某种行动。的情况下，用它们来说明分类系统应采取的某种行动。不过，缺省规则只能作为肤浅的判断，因为它们经常不过，缺省规则只能作为肤浅的判断，因为它们经常出错，因而强度得不到加强。随着分类系统获得经验，出错，因而强度得不到加强。随着分类系统获得经验，繁殖和交叉使得更复杂和更专用的规则得到发展，这繁殖和交叉使得更复杂和更专用

33、的规则得到发展，这些规则迅速得到增强，很快成为各种特殊情况下分类些规则迅速得到增强，很快成为各种特殊情况下分类系统行为的主宰。系统行为的主宰。6.4 分类器系统（分类器系统（CS-1）最终分类系统发展成为一种层次结构：处于下层的例最终分类系统发展成为一种层次结构：处于下层的例外规则层处理大多数情况；当详细规则无法满足情况外规则层处理大多数情况；当详细规则无法满足情况的条件时，处于层次结构上层的缺省规则就发挥作用。的条件时，处于层次结构上层的缺省规则就发挥作用。这种缺省层一方面带来了针对新情况的有关经验，同这种缺省层一方面带来了针对新情况的有关经验，同时也使分类系统不至于陷入过于详细的选项之中而

34、不时也使分类系统不至于陷入过于详细的选项之中而不能自拔。能自拔。促使进化中的分类系统成为处理新情况的专家的那些促使进化中的分类系统成为处理新情况的专家的那些特征，同样善于应付某次行动的效果要等到该行动很特征，同样善于应付某次行动的效果要等到该行动很久之后才能显示出来的情况。久之后才能显示出来的情况。6.5 6.5 学习系统（学习系统（LS-1LS-1）在在Holland提出分类器系统之后，提出分类器系统之后，De Jong和他的学生和他的学生Smith也提出了一种基于遗传算法的机器学习系统也提出了一种基于遗传算法的机器学习系统LS-1。Smith所提出的这种机器学习方法是匹兹堡方法的代表。所提

35、出的这种机器学习方法是匹兹堡方法的代表。LS-1的个体不是表示一条规则，而是表示一个规则集合。的个体不是表示一条规则，而是表示一个规则集合。只对规则集合进行操作，可以避开信度分配问题。只对规则集合进行操作，可以避开信度分配问题。但是，缺乏信度分配机制也是但是，缺乏信度分配机制也是LS-1的最大缺陷。由于反馈的最大缺陷。由于反馈信息不够充分，信息不够充分，LS-1系统的学习速度比较慢，需要进行大系统的学习速度比较慢，需要进行大量的训练才能够得到较好的效果。但是，通过学习，量的训练才能够得到较好的效果。但是，通过学习，LS-1系统可以得到很好的性能。系统可以得到很好的性能。LS-1学习系统的结构学

36、习系统的结构 6.5 6.5 学习系统（学习系统（LS-1LS-1）LS是是分类器系统分类器系统和一般的和一般的产生式系统产生式系统的结合，它包含了一个的结合，它包含了一个推理引推理引擎擎和一些和一些规则规则。工作存储区工作存储区由一组无序的固定长度的单元构成，每个工作区单元由一组无序的固定长度的单元构成，每个工作区单元又被细分为又被细分为信号部分信号部分和和数据部分数据部分。产生式规则存储区产生式规则存储区由一组无序的规则构成，其中，每条规则是一由一组无序的规则构成，其中，每条规则是一个固定长度的字符串。个固定长度的字符串。规则的前件规则的前件(条件条件)由由k个固定的模式组成，个固定的模式

37、组成，最初的最初的i个模式与系统探测器所发出的环境消息所匹配，剩下的个模式与系统探测器所发出的环境消息所匹配，剩下的k-i个模式与工作存储区中的信号相匹配。个模式与工作存储区中的信号相匹配。在在LS中，所有匹配的规则同时被激发。但是，若规则导致效应器中，所有匹配的规则同时被激发。但是，若规则导致效应器产生了一个动作，则不能同时激发。产生了一个动作，则不能同时激发。此时，系统对这些规则进行标记，并让这些被标记的规则向它们此时，系统对这些规则进行标记，并让这些被标记的规则向它们将要激活的效应器将要激活的效应器“投票投票”。然后，系统通过随机选择来决定产。然后，系统通过随机选择来决定产生哪一个效应器

38、动作，进行选择时每个效应器动作被选中的概率生哪一个效应器动作，进行选择时每个效应器动作被选中的概率等于它的等于它的“得票率得票率”。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)学习系统中的规则前件被分为了两个部分，一个是学习系统中的规则前件被分为了两个部分，一个是环环境模式部分境模式部分“-1#0 0#0#”，另一个是，另一个是工作存储区工作存储区模式部分模式部分“1#X 0#0#X 0 0 1 Y”。“-”代表逻辑代表逻辑“非非”运算，表示对匹配结果取反。运算，表示对匹配结果

39、取反。工作存储区状态工作存储区状态 6.5 6.5 学习系统（学习系统（LS-1LS-1）工作存储区模式中的字符工作存储区模式中的字符“X”、“Y”是变量，其第一是变量，其第一次出现时要对它赋值，赋值时取相应工作存储区消息次出现时要对它赋值，赋值时取相应工作存储区消息的数据区的值。的数据区的值。设立数据区变量使得学习系统具有了辨识数据区信息设立数据区变量使得学习系统具有了辨识数据区信息是否相等的基本能力，更重要的是，设立数据区变量是否相等的基本能力，更重要的是，设立数据区变量使得一条规则可以在它的前件和后件之间传递信息。使得一条规则可以在它的前件和后件之间传递信息。对规则进行匹配时，要自左向右

40、对规则进行扫描，首对规则进行匹配时，要自左向右对规则进行扫描，首先对环境模式进行匹配，若可以匹配，再对工作存储先对环境模式进行匹配，若可以匹配，再对工作存储区模式进行匹配。区模式进行匹配。6.5 6.5 学习系统（学习系统（LS-1LS-1）若一条规则的前件能够完全匹配，则这条规则被激发。若一条规则的前件能够完全匹配，则这条规则被激发。此时，这条规则首先在工作存储区中搜索一个可用的此时，这条规则首先在工作存储区中搜索一个可用的空位，然后将后件中的消息粘贴到这个空位的信号区空位，然后将后件中的消息粘贴到这个空位的信号区中。而后，这条规则将计算后件中数据区的值，再将中。而后，这条规则将计算后件中数

41、据区的值，再将这个值添加到空位的数据区中。这个值添加到空位的数据区中。6.5 6.5 学习系统（学习系统（LS-1LS-1）规则集合的重组规则集合的重组 系统对规则集合的重组通过系统对规则集合的重组通过GAs进行，此处进行，此处GAs使用了四种使用了四种算子：复制、变异、交叉、倒序。复制和变异算子与一般算子：复制、变异、交叉、倒序。复制和变异算子与一般的的GA算子相同，交叉算子和倒序算子则需要进行一些修改。算子相同，交叉算子和倒序算子则需要进行一些修改。交叉算子：因为规则集合的长度有可能不相同（包含不同交叉算子：因为规则集合的长度有可能不相同（包含不同数目的个体），所以必须保证交叉后生成的后代

42、有合法个数目的个体），所以必须保证交叉后生成的后代有合法个体。体。倒序算子：由于倒序算子：由于LS系统的规则具有一定的格式，所以在应系统的规则具有一定的格式，所以在应用倒序操作时必须要保证生成的后代个体中的规则在语法用倒序操作时必须要保证生成的后代个体中的规则在语法上的合法性。上的合法性。6.5 6.5 学习系统（学习系统（LS-1LS-1）在在LS-I中，交叉通过三个步骤来进行：中，交叉通过三个步骤来进行：对齐、选择交叉点、交换对齐、选择交叉点、交换。(1)对齐对齐：进行对齐时首先要在两个规则集合中随机选择一个分隔符，：进行对齐时首先要在两个规则集合中随机选择一个分隔符，然后将两个规则集合在

43、选定的分隔符处对齐。然后将两个规则集合在选定的分隔符处对齐。(2)选择交叉点选择交叉点：在对齐后要选择一个交叉点，交叉点既可以选择在：在对齐后要选择一个交叉点，交叉点既可以选择在规则之间的边界上，也可以选择在规则内部，系统用一个参数规则之间的边界上，也可以选择在规则内部，系统用一个参数Pc-rb来控制交叉发生在规则边界上的概率。若交叉点在规则边来控制交叉发生在规则边界上的概率。若交叉点在规则边界上，则可以保证规则本身不发生变化，而仅仅是规则集合发生界上，则可以保证规则本身不发生变化，而仅仅是规则集合发生了变化；若交叉点选择在规则内部，则规则本身会发生变化，而了变化；若交叉点选择在规则内部，则规

44、则本身会发生变化，而且规则集合也发生了变化。且规则集合也发生了变化。(3)(3)交换交换：在确定了交叉点后，就将两个规则集合在交叉点以后的部：在确定了交叉点后，就将两个规则集合在交叉点以后的部分互换，这样就得到了两个新的规则集合。分互换，这样就得到了两个新的规则集合。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

45、;|R7;R8;R9;R10;A：R1：R7：R8：R9：R10：B：R5：R6：R2：R3：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来玩扑克牌游戏以检测系统的学习能力。来玩扑克牌游戏以检测系统的学习能力。实验结果表明，实验结果表明，L

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

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

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

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

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