第13章启发式与元启发式算法.ppt
《第13章启发式与元启发式算法.ppt》由会员分享,可在线阅读,更多相关《第13章启发式与元启发式算法.ppt(18页珍藏版)》请在三一文库上搜索。
1、13 启发式与元启发式算法,定义,一个基于直观或经验构造的算法,在可接受的花费(指计算时间、占用空问等)下给出待解决优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计,启发式算法是一种技术,这种技术使得在可接受的计算费用内去寻找最好的解,但不一定能保证所得解的可行性和最优性,甚至大多数情况下,无法阐述所得解同最优解的近似程度,元启发式算法:启发式算法的改进,随机方法与局部搜索算法相结合。,启发式与元启发式算法优势,(1)有些难的优化问题可能还没有找到最优算法,即使存在,由算法复杂性理论,得知它们的计算时间是无法接受或不实际的 (2)一些启发式算法可用在最优算法中,如在
2、分支定界算法中,可用启发式算法估界 (3)简单易行,比较直观;易被使用者接受, (4)速度快,在适时控制中非常重要 (5)多数情况下,程序简单,因此易于修改,启发式与元启发式算法不足,(1)不能保证求得最优解 (2)表现不稳定启发式算法在同一问题的不同实例计算中会有不同的效果有些解很好,而有些则很差在实际应用中,这种不稳定性造成计算结果不可信 (3)算法的好坏依赖于实际问题、经验和设计者的技术这点很难总结规律,同时使不同算法之间难以比较,启发式与元启发式算法,遗传算法 模拟退火 粒子群算法 禁忌搜索 神经网络,13.1 遗传算法,遗传算法包含以下的主要处理步骤 首先是对优化问题的解进行编码,此
3、处,我们称一个解的编码为一个染色体,组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和用于之后遗传算法中的计算 第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定当适应函数确定以后,自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存,哪些被淘汰生存下来的染色体组成种群形成一个可以繁衍下一代的群体 第三是染色体的结合双亲的遗传基因结合通过编码之间的交配(crossover)达到下一代的产生。新一代的产生是一个生殖过程,它产生了一个新解 最后是变异新解产生过程中可能发生基因变异,变异使某些解的编码发生变化,使解有更历的遍历性,生物遗传概念在遗传
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 13 启发式 算法
链接地址:https://www.31doc.com/p-2093378.html