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

《遗传算法与机器学习课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、到的。概念学习中所隐含的这种搜索机制以及它所采用的符号表示方法，使得遗传算法在概念学习领域有其用武之地。遗传算法本身固有的鲁棒性，使得基于遗传算法的概念学习系统具有更少的限制性。6.1概述1978年Holland等实现了第一个基于遗传算法的机器学习系统：一级认知系统CS-1（CognitiveSystemLevelOne）。1986年，Holland提出桶队算法（BucketBrigade），整个系统被称为分类器系统。1980年，Smith提出LS-1系统。在某些重要方面，如染色体的表示、反馈方式等，

3、LS-1和CS-1有明显差异。1993年，DeJong和Spears提出GABIL系统，实现基于GA的概念学习。6.1概述从应用角度来说，这些系统对顺序决策这类学习问题较为合适。该类问题可以描述如下：一决策主体以回复方式与一具有离散时间状态的动态系统交互，在每个时间步的开始，系统处于某确定状态。该主体依当前状态，根据决策规则，从有限的动作集中选择一个动作供动态系统执行，并进入到一个新的状态。同时向主体反馈一个补偿（payoff），其目的是发现一决策规则集以使补偿最大化。6.2遗传机器学习系统的结构大多

4、数学习系统都具有一个共同的特性：即它们都能够产生结构上的变化来提高其内部知识结构的一致性和广泛性，发现和利用一些有意义的概念，增强其在环境下完成任务的能力。6.2遗传机器学习系统的结构通常，可以将遗传学习系统分为两个子系统：一个基于GA的用于产生合适的结构变化的学习子系统和一个用于完成外部环境任务的任务子系统。系统通过任务探测器从外部环境中获取环境信息，任务子系统则对这些信息进行处理，并产生一个对外部环境信息的响应，这个响应通过任务效应器作用到外部环境上。性能探测器对任务子系统对外部环境所产生的影响进

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

6、护一个包含一定数目的候选规则集的种群。由匹兹堡（Pittsburgh）大学的DeJong和他的学生Smith所提出。密西根方法：认为每个个体就是一条规则，而整个种群就是规则集合。由密西根（Michigan）大学的Holland和他的学生Reitman提出。一般认为，密西根方法更加适合于在线、实时的环境，在这种环境下，系统行为上的激进的变化是不能容忍的。而匹兹堡方法更适合于离线的环境，在这种环境下，更加从容不迫的搜索和更加激进的变化是可以接受的。匹兹堡方法首先要选择适当的表示方法。一种表示方法将单个规则

7、作为一个基因，而将整个分类器系统作为一个基因串（个体）。交叉算子提供规则的新的组合方式，而变异算子则提供新的规则。为了使得交叉算子和变异算子能够产生合法的个体，一种最简单的方法就是将所有的规则用固定长度、固定字段格式的二进制串来表示。这样，这些“IF—THEN”规则就很自然地表示为一组固定数目的待匹配的传感器模式和一个在此模式下的动作。匹兹堡方法也可以采用更加灵活的表示方法：用不定长的串来表示规则。这种情况下，需要对遗传算子进行修改才能保证得到合法的个体。一种方式就是在串中加入“标点符号”，并通过这些

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