购买

¥ 30.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 机器学习课件p3 遗传算法eb

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

机器学习课件p3 遗传算法eb

精品课件库
2019-06-20 0人阅读 举报 0 0 暂无简介

简介:本文档为《机器学习课件p3 遗传算法ebppt》,可适用于高中教育领域

第三部分遗传算法参考书目王晓平曹立明遗传算法理论、应用与软件实现西安交通大学出版社孙增忻智能控制理论与技术清华大学出版社李人厚智能控制理论和方法西安电子科技大学出版社遗传算法简介JohnHenryHolland,AdaptationinNaturalandArtificialSystemsDavidEGoldberg,GeneticAlgorithms遗传算法简介模拟自然界的进化现象:适者生存优胜劣汰把搜索空间映射为遗传空间把每一个可能的解编码为一个向量向量:染色体、个体元素:基因向量的表示:二进制或十进制的串遗传算法简介多个染色体组成种群、群体或集团按预定的目标函数对每个染色体进行评价根据结果给出其适应度新一代的个体不断地在总体性能胜过旧的一代遗传算法的特点适者生存、优胜劣汰鲁棒性在各种不同的环境中通过效率与功能之间的平衡以求生存的能力。启发式搜索适用于复杂问题的优化常规的优化方法解析法枚举法随机法遗传算法的工作原理及操作步骤问题:在整数论域,内求解如下函数的极大值。问题的表述与参数的编码将待寻优的参数编码为有限长度的串位二进制编码定义目标函数极大值确定初始种群step初始种群的数量随机生成初始种群染色体与基因复制(Selection)step计算个体的适配值(Fitness)适配值适配值占整体的比例适配值累加根据适配值确定复制概率复制(选择)策略轮盘赌轮转法、比例选择法轮盘赌示意图复制操作前的有关数据编号初始种群x值适配值适配值累加复制概率期望复制数实际的复制数总计平均最大值unknownunknownunknown交叉(Crossover)step复制后产生的个体随机两两匹配交叉繁殖长度为l的串数字之间的空隙标记为随机产生位置整数从位置k到串尾的子串互相交换形成新串复制操作后的有关数据编号复制后的匹配池匹配对象交叉点新种群x值适配值总计平均最大值unknown变异(Mutation)step以极小的概率随机地改变基因一个串位的值P=:×=无变异满足预定指标退出否则转step标准遗传算法流程遗传算法的数学依据图式、模式定义长度确定位数、图式的阶次图式定理图式描述种群中任意染色体之间相似性的一组符号串由符号和通配符*定义、序列组成图式的固定部分*表示其变化部分整个图式表示有意义的匹配模式图式例图式**可匹配的串图式数二进制最大图式数:其他进制最大图式数:图式数大于串的数量图式的意义GA利用种群中包含的众多的图式及染色体符号串之间的相似性信息进行启发式搜索和问题求解。在产生新一代的过程中GA完成了正比于种群长度的计算量而处理的图式却正比于种群长度的三次方。图式的定义长度与阶次定义长度H左右两端有定义的位置之间的距离***:=确定位数、阶次H中有定义的位的个数***:组块种群中定义长度短、确定位数少和适应度高的图式GA的运算实际上是对组块的操作复制对图式的影响设m(H,t)表示在第t代种群中存在的图式H的数量f(H)为在t时刻包含H的染色体的平均适应度。对于有n个染色体的种群经复制操作在t时刻图式H的数量表示为m(H,t)。复制对图式的影响在复制运算中下一代种群中H的数量正比于种群中H染色体平均适应度与种群平均适应度的比值。 交叉对图式的影响图式因交叉而被破坏的概率交叉的概率染色体的长度变异对图式的影响图式因变异而被破坏的概率变异的概率图式定理在复制、交叉和变异运算的作用下确定位数少、定义长度短和适应度高的图式(组块)将按指数的规律一代一代地增长。遗传算法的有关问题知识的表示适应度函数全局收敛与最优性早期收敛 早熟知识的表示编码编码的基本原理DavidEGoldberg所选编码方式应使确定位数少、定义长度短的图式与所求解的问题相关而同其他固定位的图式与求解问题关系少一些。所选的编码方式应具有最小的字符集自然地表达欲求解的问题。二进制编码与非二进制编码相同的解的数量提供的图式数量多参数优化问题的编码已编码整数的线性映射映射的精度构造多参数的编码按要求将单参数编码连接起来即可每一个码可以有自己的子长度和取值范围。适应度函数适应度函数值非负待优化问题表述为最大化问题目标函数最小化可以当作输入参数、所观测到的最大值、当前或前k代种群中的最大值。目标函数最大化可以当作输入参数、当前或前k代种群中的最小值的绝对值。超级染色体全局收敛与早熟已经证明当采用轮转法时简单的GA都不会以的概率收敛到全局的最优点。只有采用精英选择法和改进的GA可以收敛到全局的最优点。在进化的初期按照轮转法少数具有相对高的适应度的“超常”染色体会获得较多的后代抑制了具有优秀图式的普通染色体的生长造成成熟前收敛。全局收敛与早熟遗传算法的有关问题复制(Selection)方法精英选择法确定性选择法置换式余数随机选择法非置换式余数随机选择法RankbasedRoulettewheelselection复制(Selection)方法StochasticuniversalsamplingLocalselectionTruncationselectionTournamentselection复制的评价指标SelectivepressureprobabilityofthebestindividualbeingselectedcomparedtotheaverageprobabilityofselectionofallindividualsBiasabsolutedifferencebetweenanindividual'snormalizedfitnessanditsexpectedprobabilityofreproduction复制的评价指标SpreadrangeofpossiblevaluesforthenumberofoffspringofanindividualLossofdiversityproportionofindividualsofapopulationthatisnotselectedduringtheselectionphase复制的评价指标SelectionintensityexpectedaveragefitnessvalueofthepopulationafterapplyingaselectionmethodtothenormalizedGaussiandistributionSelectionvarianceexpectedvarianceofthefitnessdistributionofthepopulationafterapplyingaselectionmethodtothenormalizedGaussiandistribution精英选择法把种群中最优秀的个体直接复制到下一代提高优秀个体对种群的控制速度改善局部搜索和GA特性损坏了全局的搜索能力确定性选择法选择概率按常规计算计算期望的后代数目按整数部分分配后代数目染色体按余数降序排列种群其余部分按排序表由高到低依次选择填充置换式余数随机选择法开始部分同确定性选择法余数部分用来计算轮转法中的权值置换式余数随机选择法开始部分同确定性选择法余数部分按概率来处理RankbasedSelectionRankfitnessassignmentLinearrankingNonlinearrankingLinearRankingSP:选择压力Nind:种群规模NonlinearRankingLinearandNonlinearRankingRouletteWheelSelectionStochasticUniversalSampling,NPointerLocalSelectionThefirststepistheselectionofthefirsthalfofthematingpopulationuniformatrandomInsidethisneighborhoodthematingpartnerisselectedLocalSelectionLocalSelectionLocalSelectionTruncationSelectionBeusedbybreedersforlargepopulationsmassselectionIndividualsaresortedaccordingtotheirfitnessOnlythebestindividualsareselectedforparentsTheparameterfortruncationselectionisthetruncationthresholdTruncationSelectionTournamentSelectionTour:numberofindividualsbechosenrandomlyfromthepopulationNind:numberofindividualsinpopulationTourtakesvaluesrangingfromtoNindTournamentSelectionRecombination(Crossover)DiscreteRecombinationCanbeappliedtoallvariablerepresentationsDiscreteRecombinationDiscreteRecombinationindividualindividualsamplesampleoffspringoffspringIntermediateRecombinationIntermediateRecombinationIntermediateRecombinationIntermediateRecombinationindividualindividualsamplesampleoffspringoffspringLineRecombinationLineRecombinationSinglepointRrossoverMultipointcrossoverMultipointCrossoverC:||C:||C’:||C’:||UniformCrossover掩码交换父辈父辈模板(M)子辈子辈MutationRealvaluedmutationBinarymutationBreederGeneticAlgorithmBreederGeneticAlgorithm微种群算法SGA种群规模大~种群小计算简单、速度快、易陷入局部最优随机产生小种群实施精英选择策略微种群算法随机选择规模为的种群或个是随机选择个来自前一次搜索。计算适应度并确定最好的串将其标记为直接传到下一代。按确定性竞赛选择策略选择其余的个串进行复制(选)同时应避免下一代中同一串有两个复制品。按概率进行交叉运算变异概率为零。检验收敛条件。如果收敛转步骤否则转步骤。微种群算法收敛条件最大适应度个体与其他个个体的基因差异率是否低于设定值()微种群算法在进化过程中以合理的间隔通过“启动再启动”过程不断引入恒定数目的新种群寻求好的个体避免早熟且收敛速度快。微种群算法与标准遗传算法比较双种群算法DGA全局种群寻找可能存在最优点的区域局部种群在全局总群划定的区域仔细搜索寻找最优点DGAStep初始化随机生成全局总群Gglobal设定局部最优值DGAStep全局总群搜索最优点与最优值DGAStep局部搜索。在局部种群搜索中心宽度为w的范围内随机产生初始种群Glocal遗传搜索得到当前最优点xlopt与最优值Vlopt。DGAStep如果Vopt满足条件或算法满足条件结束否则返回step。DGAStep如果Vgopt>Vlopt局部种群搜索中心修改xlocal=xgloba局部种群搜索中心不变。TSP问题变异TSP问题交叉TSP问题交叉Inputs:Chromosomesga=(D,H,B,A,C,F,G,E)gb=(B,C,D,G,H,F,E,A)Outputs:Theoffspringg=(H,B,A,C,D,G,F,E)遗传算法的有关问题说明遗传算法易于使用但不易使用得好。如果有其他的方法不要使用遗传算法。遗传算法不能解决所有问题。遗传算法只是进化论算法性能较强的几个分支之一。作业查阅遗传算法的有关文献就遗传算法的改进方法写一篇字左右的综述性论文。

VIP尊享8折文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/95

机器学习课件p3 遗传算法eb

¥30.0

会员价¥24.0

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利