《模拟退火算法》PPT课件.ppt
《《模拟退火算法》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《模拟退火算法》PPT课件.ppt(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、模模 拟拟 退退 火火 算算 法法(Simulated Annealing)1 1、引子、引子2 2、SASA算法的起源算法的起源3 3、SASA算法的基本思想算法的基本思想4 4、SASA算法的步骤算法的步骤5 5、SASA算法应用范围与一般要求算法应用范围与一般要求6 6、SASA算法的优缺点算法的优缺点1 1、引子、引子 在科学与工程计算中,经常发生的一个问题是在Rn中或者是在一个有界区域上求某个非线性函数f(x)的极小点。在f(x)可导时,一个最基本的算法就是最速下降法。这一方法从某一选定的初值开始,利用如下公式进行迭代,即 然而以速降法为代表的传统算法具有共同的缺点,它们都不保证求得
2、全局极小,只能保证收敛到一个由初值决定的局部极小点。每次都鼠目寸光的选择一个当前最优解,因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。2 2、SASA算法的起源算法的起源 SA算法起源于对固体退火过程的模拟。简单而言,在固体退火时,先将固体加热使其温度充分高,再让其徐徐冷却,其物理退火过程由以下三部分组成:加温过程、等温过程、冷却过程。SA算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术。模拟退火算法与物理退火过程的相似关系3 3、SAS
3、A算法的基本思想算法的基本思想 在搜索最优解的过程中,SA算法除了可以接受优化解外,还基于随机接受准则(Metropolis准则)有限度地接受恶化解,并且接受恶化解的概率慢慢趋向于0。(这使得算法有可能从局部最优中跳出,尽可能找到全局最优解,并保证了算法的收敛)SA的思想最早是由Metropolis等在1953年提出的,Metropolis 等提出了重要性采样法,即以概率接受新状态。SA算法的思想为:由初始解i和控制参数初值t开始,对当前解重复 产生新解 计算目标函数差 接受或舍弃 的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟退火算法 模拟 退火 算法 PPT 课件
限制150内