遗传算法 (3)精品文稿.ppt

《遗传算法 (3)精品文稿.ppt》由会员分享，可在线阅读，更多相关《遗传算法 (3)精品文稿.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法算法第1页，本讲稿共21页概述概述遗传算法是一种大致基于模拟进化的学习方法遗传算法是一种大致基于模拟进化的学习方法假设通常被描述为二进制位串，也可以是符号表达式或计假设通常被描述为二进制位串，也可以是符号表达式或计算机程序算机程序搜索合适的假设从若干初始假设的群体或集合开始搜索合适的假设从若干初始假设的群体或集合开始当前群体的成员通过模拟生物进化的方式来产生下一代群当前群体的成员通过模拟生物进化的方式来产生下一代群体，比如随机变异和交叉体，比如随机变异和交叉(crossover)每一步，根据给定的适应度评估当前群体中的假设，而每一步，根据给定的适应度评估当前群体中的假设，而后使用概率方

2、法选出适应度最高的假设作为产生下一代后使用概率方法选出适应度最高的假设作为产生下一代的种子的种子遗传算法已被成功用于多种学习任务和最优化问遗传算法已被成功用于多种学习任务和最优化问题中，比如学习机器人控制的规则集和优化人工题中，比如学习机器人控制的规则集和优化人工神经网络的拓扑结构和学习参数神经网络的拓扑结构和学习参数本章主要介绍了基于位串描述假设的遗传算法和基于计算本章主要介绍了基于位串描述假设的遗传算法和基于计算机程序描述假设的遗传编程机程序描述假设的遗传编程第2页，本讲稿共21页动机动机(1)遗传算法（遗传算法（GA）是一种受生物进化启发的学习方法，）是一种受生物进化启发的学习方法，它不

3、再是从一般到特殊或从简单到复杂地搜索假设，而它不再是从一般到特殊或从简单到复杂地搜索假设，而是通过变异和重组当前已知的最好假设来生成后续的假是通过变异和重组当前已知的最好假设来生成后续的假设设每一步，更新被称为当前群体的一组假设，方法是每一步，更新被称为当前群体的一组假设，方法是使用当前适应度最高的假设的后代替代群体的某个使用当前适应度最高的假设的后代替代群体的某个部分部分这个过程形成了假设的生成测试的柱状搜索，其中若干个这个过程形成了假设的生成测试的柱状搜索，其中若干个最佳当前假设的变体最有可能在下一步被考虑最佳当前假设的变体最有可能在下一步被考虑第3页，本讲稿共21页动机（动机（2）遗传算

4、法的普及和发展得益于下面的因素遗传算法的普及和发展得益于下面的因素在生物系统中，进化被认为是一种成功的自适应方法，在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性具有很好的健壮性遗传算法搜索的假设空间中，假设的各个部分相互作用，遗传算法搜索的假设空间中，假设的各个部分相互作用，每一部分对总的假设适应度的影响难以建模每一部分对总的假设适应度的影响难以建模遗传算法易于并行化遗传算法易于并行化第4页，本讲稿共21页遗传算法遗传算法(1)遗传算法研究的问题是搜索候选假设空间并确定最遗传算法研究的问题是搜索候选假设空间并确定最佳假设佳假设最佳假设被定义为使适应度最优的假设最佳假设被定义为

5、使适应度最优的假设适应度是为当前问题预先定义的数字度量，比适应度是为当前问题预先定义的数字度量，比如：如：如果学习任务是在给定一个未知函数的输入输如果学习任务是在给定一个未知函数的输入输出训练样例后逼近这个函数，适应度可被定义出训练样例后逼近这个函数，适应度可被定义为假设在训练数据上的精度为假设在训练数据上的精度如果是学习下国际象棋的策略，适应度可被定义如果是学习下国际象棋的策略，适应度可被定义为该个体在当前群体中与其他个体对弈的获胜率为该个体在当前群体中与其他个体对弈的获胜率第5页，本讲稿共21页遗传算法（遗传算法（2）遗传算法具有以下的共同结构：遗传算法具有以下的共同结构：算法迭代更新一个

6、假设池，这个假设池称为群体算法迭代更新一个假设池，这个假设池称为群体在每一次迭代中，根据适应度评估群体中的所在每一次迭代中，根据适应度评估群体中的所有成员，然后用概率方法选取适应度最高的个有成员，然后用概率方法选取适应度最高的个体产生新一代群体体产生新一代群体在被选中的个体中，一部分保持原样地进入下一代群在被选中的个体中，一部分保持原样地进入下一代群体，其他被用作产生后代个体的基础，其中应用交叉体，其他被用作产生后代个体的基础，其中应用交叉和变异这样的遗传方法和变异这样的遗传方法第6页，本讲稿共21页遗传算法原型遗传算法原型GA(Fitness,Fitness_threshold,p,r,m)

7、Fitness：适应度评分函数：适应度评分函数Fitness_threshold：指定终止判据的阈值：指定终止判据的阈值p：群体中包含的假设数量：群体中包含的假设数量r：每一步中通过交叉取代群体成员的比例：每一步中通过交叉取代群体成员的比例m：变异率：变异率初始化群体：初始化群体：P随机产生的随机产生的p个假设个假设评估：对于评估：对于P中每个假设中每个假设h，计算，计算Fitness(h)当当 Fitness_threshold，产生新一代，产生新一代PS，做：，做：选择：用概率方法选择选择：用概率方法选择P的的(1-r)p个成员加入个成员加入PS，概率公式是，概率公式是交叉：按概率从交叉：

8、按概率从P中选择中选择rp/2对假设，对于每对假设对假设，对于每对假设，应用交叉算子产，应用交叉算子产生两个后代，把所有的后代加入生两个后代，把所有的后代加入PS变异：使用均匀的概率从变异：使用均匀的概率从PS中选择中选择m%的成员，应用变异算子的成员，应用变异算子更新：更新：PPS评估：对于评估：对于P中每个中每个h计算计算Fitness(h)从从P中返回适应度最高的假设中返回适应度最高的假设第7页，本讲稿共21页遗传算法（遗传算法（3）算法的每一次迭代以算法的每一次迭代以3种方式产生新一代群体种方式产生新一代群体直接从当前群体中选择直接从当前群体中选择在选中的个体中进行交叉操作在选中的个体

9、中进行交叉操作在新群体上进行变异操作在新群体上进行变异操作遗传算法执行一种随机的、并行柱状的搜索，根据遗传算法执行一种随机的、并行柱状的搜索，根据适应度函数发现好的假设适应度函数发现好的假设第8页，本讲稿共21页表示假设表示假设遗传算法中的假设常常被表示成二进制位串，这便于用变异和交遗传算法中的假设常常被表示成二进制位串，这便于用变异和交叉遗传算子来操作叉遗传算子来操作把把if-then规则编码成位串规则编码成位串首先使用位串描述单个属性的值约束首先使用位串描述单个属性的值约束比如考虑属性比如考虑属性Outlook，它的值可以取以下，它的值可以取以下3个中的任一个：个中的任一个：Sunny、O

10、vercast、Rain，因此一个明显的方法是使用一个，因此一个明显的方法是使用一个长度为长度为3的位串，每位对应一个可能值，若某位为的位串，每位对应一个可能值，若某位为1，表示这个，表示这个属性可以取对应的值属性可以取对应的值多个属性约束的合取可以很容易地表示为对应位串的连接多个属性约束的合取可以很容易地表示为对应位串的连接整个规则表示可以通过把描述规则前件和后件的位串连整个规则表示可以通过把描述规则前件和后件的位串连接起来接起来第9页，本讲稿共21页表示假设（表示假设（2）位串的特点位串的特点表示规则的位串对假设空间中的每个属性有一表示规则的位串对假设空间中的每个属性有一个子串，即使该属性

11、不被规则的前件约束。个子串，即使该属性不被规则的前件约束。得到一个固定长度的规则位串表示，其中特定得到一个固定长度的规则位串表示，其中特定位置的子串描述对应特定属性的约束位置的子串描述对应特定属性的约束规则集的表示：单个规则的位串表示连接起来规则集的表示：单个规则的位串表示连接起来有必要让每个句法合法的位串表示一个有意义的假设有必要让每个句法合法的位串表示一个有意义的假设假设也可以用符号描述来表示，而不是位串，比如计算假设也可以用符号描述来表示，而不是位串，比如计算机程序机程序第10页，本讲稿共21页遗传算子遗传算子遗传算法使用一系列算子来决定后代，算子对当前群体中选定的成员进行重组遗传算法使

12、用一系列算子来决定后代，算子对当前群体中选定的成员进行重组列出了用来操作位串的典型遗传算法算子，它们是生物进化中的遗传过列出了用来操作位串的典型遗传算法算子，它们是生物进化中的遗传过程的理想化形式程的理想化形式最常见的算子是交叉和变异最常见的算子是交叉和变异交叉：交叉：从两个双亲串中通过复制选定位产生两个新的后代，每个后代的第从两个双亲串中通过复制选定位产生两个新的后代，每个后代的第i位是从它的某个双亲的第位是从它的某个双亲的第i位复制来的位复制来的双亲中的哪一个在第双亲中的哪一个在第i位起作用，由另一个称为交叉掩码的位串决定：位起作用，由另一个称为交叉掩码的位串决定：单点交叉：前单点交叉：前

13、n位来自第一个双亲，余下的位来自第二个双亲位来自第一个双亲，余下的位来自第二个双亲两点交叉：用一个双亲的中间片断替换第二个双亲的中间片断两点交叉：用一个双亲的中间片断替换第二个双亲的中间片断均匀交叉：合并了从两个双亲以均匀概率抽取的位均匀交叉：合并了从两个双亲以均匀概率抽取的位第11页，本讲稿共21页遗传算子（遗传算子（2）变异：变异：从单一双亲产生后代，对位串产生随机的小变化，从单一双亲产生后代，对位串产生随机的小变化，方法是选取一个位，然后取反方法是选取一个位，然后取反变异经常是在应用交叉之后变异经常是在应用交叉之后其他算子其他算子使规则特化的算子使规则特化的算子直接泛化直接泛化第12页，

14、本讲稿共21页适应度函数和假设选择适应度函数和假设选择适应度函数定义了候选假设的排序准则适应度函数定义了候选假设的排序准则如果学习任务是分类的规则，那么适应度函数中会有一项用来评价如果学习任务是分类的规则，那么适应度函数中会有一项用来评价每个规则对训练样例集合的分类精度，也可包含其他的准则，比如每个规则对训练样例集合的分类精度，也可包含其他的准则，比如规则的复杂度和一般性规则的复杂度和一般性选择假设的概率计算方法选择假设的概率计算方法适应度比例选择（或称轮盘赌选择），选择某假设的概率是适应度比例选择（或称轮盘赌选择），选择某假设的概率是通过这个假设的适应度与当前群体中其他成员的适应度的比通过这

15、个假设的适应度与当前群体中其他成员的适应度的比值得到的值得到的锦标赛选择，先从当前群体中随机选取两个假设，再按照事先定义锦标赛选择，先从当前群体中随机选取两个假设，再按照事先定义的概率的概率p选择适应度较高的假设，按照概率选择适应度较高的假设，按照概率1-p选择适应度较选择适应度较低的假设低的假设排序选择，当前群体中的假设按适应度排序，某假设的排序选择，当前群体中的假设按适应度排序，某假设的概率与它在排序列表中的位置成比例，而不是与适应度概率与它在排序列表中的位置成比例，而不是与适应度成比例成比例第13页，本讲稿共21页举例举例遗传算法可以被看作是通用的最优化方法，它搜索遗传算法可以被看作是通

16、用的最优化方法，它搜索一个巨大的候选假设空间，根据适应度函数查找表一个巨大的候选假设空间，根据适应度函数查找表现最好的假设现最好的假设遗传算法尽管不能保证发现最优的假设，但一般能够发现遗传算法尽管不能保证发现最优的假设，但一般能够发现具有较高适应度的假设具有较高适应度的假设遗传算法的广泛应用遗传算法的广泛应用电路布线电路布线任务调度任务调度函数逼近函数逼近选取人工神经网络的拓扑结构选取人工神经网络的拓扑结构第14页，本讲稿共21页进化和学习模型进化和学习模型(1)有关进化系统的一个有趣问题：单一个体生命期有关进化系统的一个有趣问题：单一个体生命期间的学习与整个物种较长时期内由进化促成的学间的学

17、习与整个物种较长时期内由进化促成的学习，它们的关系是什么？习，它们的关系是什么？拉马克进化拉马克进化拉马克在拉马克在19世纪末提出，多代的进化直接受到个世纪末提出，多代的进化直接受到个别生物体在它们生命期间的经验的影响别生物体在它们生命期间的经验的影响目前的科学证据不支持拉马克模型目前的科学证据不支持拉马克模型但近来的计算机研究表明，拉马克过程有时可以提高但近来的计算机研究表明，拉马克过程有时可以提高计算机遗传算法的效率计算机遗传算法的效率第15页，本讲稿共21页进化和学习模型（进化和学习模型（2）鲍德温效应鲍德温效应通过个体学习改变进化进程的机制通过个体学习改变进化进程的机制基于以下现象基于

18、以下现象如果一个物种在一个变化的环境中进化，那么进如果一个物种在一个变化的环境中进化，那么进化的压力会支持有学习能力的个体，这种学习能化的压力会支持有学习能力的个体，这种学习能力可以使个体在其生命期间执行一种小的局部搜力可以使个体在其生命期间执行一种小的局部搜索，以最大化它的适应度，相反，不学习的个体索，以最大化它的适应度，相反，不学习的个体的适应度完全取决于它的遗传结构，会处于相对的适应度完全取决于它的遗传结构，会处于相对劣势劣势具备学习能力的个体可以通过学习克服遗传代具备学习能力的个体可以通过学习克服遗传代码中的码中的“丢失的丢失的”或或“并非最优的并非最优的”特性，从特性，从而支持更加多

19、样化的基因池，然后促进适应性而支持更加多样化的基因池，然后促进适应性更加快速地进化更加快速地进化提供了一种间接的机制，使个体的学习可以正面提供了一种间接的机制，使个体的学习可以正面影响进化速度影响进化速度第16页，本讲稿共21页进化和学习模型（进化和学习模型（3）人们一直努力开发研究鲍德温效应的计算模型人们一直努力开发研究鲍德温效应的计算模型Hinton&Nowlan1987对一个简单神经网络的群体对一个简单神经网络的群体进行试验进行试验在一个网络个体的在一个网络个体的“生命期生命期”间，它的一些权值是固间，它的一些权值是固定的，而其他权是可被训练的定的，而其他权是可被训练的在群体进化初期的各

20、代中，具有很多可训练权值的个在群体进化初期的各代中，具有很多可训练权值的个体占据较大的比例体占据较大的比例随着进化的进行，群体向着遗传给定权值和较少依赖随着进化的进行，群体向着遗传给定权值和较少依赖个体学习权值的方向进化，正确的固定权值的数量趋个体学习权值的方向进化，正确的固定权值的数量趋于增长于增长第17页，本讲稿共21页并行遗传算法并行遗传算法遗传算法很自然地适合并行实现遗传算法很自然地适合并行实现粗粒度并行方法粗粒度并行方法把群体细分成相对独立的个体群，称为类属，然后为每把群体细分成相对独立的个体群，称为类属，然后为每个类属分配一个不同的计算节点，在每个节点进行标准个类属分配一个不同的计

21、算节点，在每个节点进行标准的的GA搜索搜索类属之间的通信和交叉发生的频率与类属内相比较低，类属类属之间的通信和交叉发生的频率与类属内相比较低，类属之间的交换通过迁移来进行，也就是某些个体从一个类属复之间的交换通过迁移来进行，也就是某些个体从一个类属复制或交换到其他类属制或交换到其他类属这个过程模拟了以下的生物进化方式，即自然界中异体受精可这个过程模拟了以下的生物进化方式，即自然界中异体受精可能发生在分离的物种子群体之间能发生在分离的物种子群体之间这种方法的一个好处是减少了非并行这种方法的一个好处是减少了非并行GA经常碰到的拥挤问经常碰到的拥挤问题题细粒度并行方法细粒度并行方法给每个个体分配一个

22、处理器，然后相邻的个体间发生重组给每个个体分配一个处理器，然后相邻的个体间发生重组第18页，本讲稿共21页小结小结遗传算法用一种随机化的并行爬山搜索来发现使预先定义的适应度函数遗传算法用一种随机化的并行爬山搜索来发现使预先定义的适应度函数最优的假设最优的假设遗传算法基于对生物进化的模拟，维护一个由竞争假设组成遗传算法基于对生物进化的模拟，维护一个由竞争假设组成的多样化群体，在每一次迭代中，选出群体中适应度最高的的多样化群体，在每一次迭代中，选出群体中适应度最高的成员来产生后代，替代群体中适应度最差的成员成员来产生后代，替代群体中适应度最差的成员遗传算法阐明了如何把学习过程看成最优化过程的一个特

23、例，学习任务遗传算法阐明了如何把学习过程看成最优化过程的一个特例，学习任务就是根据预先定义的适应度函数发现最优假设就是根据预先定义的适应度函数发现最优假设遗传编程是遗传算法的变体，在遗传编程中，被操作的假设是计算机程遗传编程是遗传算法的变体，在遗传编程中，被操作的假设是计算机程序而不是位串序而不是位串第19页，本讲稿共21页补充读物补充读物在计算机科学发展的早期，人们就开始探索基于进化的计算方法（在计算机科学发展的早期，人们就开始探索基于进化的计算方法（Box1957、Bledsoe1964）Rechenberg1965,1973、Schwefel1975,1977,1995开发的进化开发的进

24、化策略用来优化工程设计中的数字参数策略用来优化工程设计中的数字参数Folgel&Owens&Walsh1966开发了进化编程，作为进化有限状开发了进化编程，作为进化有限状态机的一种方法态机的一种方法Koza1992介绍了遗传编程，把遗传算法的搜索策略应用到由计算介绍了遗传编程，把遗传算法的搜索策略应用到由计算机程序组成的假设中机程序组成的假设中K.Dejong和他的学生开发了使用和他的学生开发了使用GA学习规则集的方法，每个规则学习规则集的方法，每个规则集是竞争假设组成的群体的一个成员集是竞争假设组成的群体的一个成员Holland和他的学生设定每个规则是群体的一个成员，群体本和他的学生设定每个

25、规则是群体的一个成员，群体本身是一个规则集身是一个规则集第20页，本讲稿共21页补充读物（补充读物（2）Mitchell1996和和Goldberg1986给出了有关遗传算法的两本教材给出了有关遗传算法的两本教材Koza1992关于遗传编程的专著是对遗传算法扩展到操作计算关于遗传编程的专著是对遗传算法扩展到操作计算机程序的标准参考书机程序的标准参考书会议会议遗传算法国际会议（主要会议）遗传算法国际会议（主要会议）自适应行为仿真会议自适应行为仿真会议人工神经网络和遗传算法国际会议人工神经网络和遗传算法国际会议IEEE进化计算国际会议进化计算国际会议杂志杂志进化计算杂志进化计算杂志机器学习机器学习第21页，本讲稿共21页