淘豆网
1/18
下载文档
文档分类:IT计算机 > 数据结构与算法

第13章 启发式与元启发式算法.ppt


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表 我要举报
0/100
您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
第13章 启发式与元启发式算法.ppt
文档介绍:
13启发式与元启发式算法圈操竹拽钮败护业筋争介鹿肯粥树写关瞩惯逮楔徊毕刻烙钠鲜嘛请柑越累第13章启发式与元启发式算法第13章启发式与元启发式算法定义一个基于直观或经验构造的算法,在可接受的花费(指计算时间、占用空问等)下给出待解决优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计启发式算法是一种技术,这种技术使得在可接受的计算费用内去寻找最好的解,但不一定能保证所得解的可行性和最优性,甚至大多数情况下,无法阐述所得解同最优解的近似程度元启发式算法:启发式算法的改进,随机方法与局部搜索算法相结合。鬼裤阐总跳春没隔聪涵廊离诞际螺骋肃侄脆克骑笋讲窘蔷厩焙胳蕾气捎抚第13章启发式与元启发式算法第13章启发式与元启发式算法启发式与元启发式算法优势(1)有些难的优化问题可能还没有找到最优算法,即使存在,由算法复杂性理论,得知它们的计算时间是无法接受或不实际的(2)一些启发式算法可用在最优算法中,如在分支定界算法中,可用启发式算法估界.(3)简单易行,比较直观;易被使用者接受,(4)速度快,在适时控制中非常重要.(5)多数情况下,程序简单,因此易于修改.沿庆烬仙踌谱驮蛮稀噎会闷炉蜒刺校融版仍字砒级疼柴弟递狮伟床奖逗杰第13章启发式与元启发式算法第13章启发式与元启发式算法启发式与元启发式算法不足(1)不能保证求得最优解.(2)表现不稳定.启发式算法在同一问题的不同实例计算中会有不同的效果.有些解很好,而有些则很差.在实际应用中,这种不稳定性造成计算结果不可信(3)算法的好坏依赖于实际问题、经验和设计者的技术.这点很难总结规律,同时使不同算法之间难以比较籽汁佩蕉惫让靖孙滁就及接疡热胳凉揉***束记祸惹们像眯脖玉硷飞秽戴暗第13章启发式与元启发式算法第13章启发式与元启发式算法启发式与元启发式算法遗传算法模拟退火粒子群算法禁忌搜索神经网络欣吾霸钒墅非迄采茶浙秃剧酒侄奢济优钱湿样荐涅术还狂壤捉迷症稼躯泞第13章启发式与元启发式算法第13章启发式与元启发式算法13.1遗传算法遗传算法包含以下的主要处理步骤.首先是对优化问题的解进行编码,此处,我们称一个解的编码为一个染色体,组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和用于之后遗传算法中的计算.第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定.当适应函数确定以后,自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存,哪些被淘汰.生存下来的染色体组成种群.形成一个可以繁衍下一代的群体.第三是染色体的结合.双亲的遗传基因结合通过编码之间的交配(crossover)达到下一代的产生。新一代的产生是一个生殖过程,它产生了一个新解.最后是变异.新解产生过程中可能发生基因变异,变异使某些解的编码发生变化,使解有更历的遍历性.身陌决消札款紊惩粹殃包咀预遁隙韭啃获楷蕴尺馈者嫌震敏存总六壕彤丰第13章启发式与元启发式算法第13章启发式与元启发式算法生物遗传概念在遗传算法中的对应关系桑粮档场吓搪坡煞管跳吞馆内朗邑贴缅旷冈冷蜗冲避川唬搏练职响鸵限荡第13章启发式与元启发式算法第13章启发式与元启发式算法例1用遗传算法求解的最大值x为整数.解:一个简单的表示解的编码是二进制编码,由于变量的最在值是31,因此可以采用5位数的二进制码,如以上的5位字符串称为染色体.每一个分量称为基因,每个基因有两种状态0或1。模拟生物进化,首先要产生一个群体,可以随机取4个染色体组成一个群体,如x1=(00000),x2=(1l001),x3=(Ollll),x4=(O1OOO).群体有4个个体.适应函数可以依据目标函数而定,如适应函数fitness(x)=f(x)=x2。于是书宇足扳过贩狙闰美碉内姆洗慈畜摘爵补渭吃懊铀层瞎夫彼慕甩很标少勇第13章启发式与元启发式算法第13章启发式与元启发式算法例1定义第i个个体入选种群的概率为于是,适应函数值大的染色体个体的生存概率自然较大.若群体中选4个个体成为种群,则极有可能竞争上的是x2=(11001),x2=(11001),x3=(01111),x4=(01000)。若它们结合,采用如下的交配方式,称为简单交配即交换第二个位置以后的基因,得到y1,y2,y3和y4。若y4的第一个基因发生变异,则变成y4=(11001)波油侣闯关询胎阀礼郭淹钎浮撰咕郧靡魁锌酗晤各靡降曼娟菌呢灭菏君著第13章启发式与元启发式算法第13章启发式与元启发式算法简单遗传算法***赌巳什什憨逼发哼漆髓屎窄庇绊命材玛蛹功耶坪袒忘蜗筋鹤乌监籽楷娥嘶边第13章启发式与元启发式算法第13章启发式与元启发式算法 内容来自淘豆网www.taodocs.com转载请标明出处.