第三篇 模拟退火算法.ppt

1 模拟退火算法 模拟退火算法原理模拟退火算法流程模拟退火算法要素模拟退火算法优缺点模拟退火算法应用 2 引言 爬山算法 HillClimbing 爬山算法是一种简单的贪心搜索算法 该算法每次从当前解的临近解空间中选择一个最优解作为当前解 直到达到一个局部最优解 爬山算法实现很简单 其主要缺点是会陷入局部最优解 而不一定能搜索到全局最优解 3 引言 爬山算法 HillClimbing 如图所示 假设C点为当前解 爬山算法搜索到A点这个局部最优解就会停止搜索 因为在A点无论向那个方向小幅度移动都不能得到更优的解 4 引言 模拟退火算法爬山法是完完全全的贪心法 每次都鼠目寸光的选择一个当前最优解 因此只能搜索到局部的最优值 模拟退火其实也是一种贪心算法 但是它的搜索过程引入了随机因素 模拟退火算法以一定的概率来接受一个比当前解要差的解 因此有可能会跳出这个局部的最优解 达到全局的最优解 5 引言 模拟退火算法仍以下图为例 模拟退火算法在搜索到局部最优解A后 会以一定的概率接受到E的移动 也许经过几次这样的不是局部最优的移动后会到达D点 于是就跳出了局部最大值A 6 模拟退火算法原理 模拟退火算法来源于固体退火原理 将固体加温至充分高 再让其徐徐冷却 加温时 固体内部粒子随温升变为无序状 内能增大 而徐徐冷却时粒子渐趋有序 在每个温度都达到平衡态 最后在常温时达到基态 内能减为最小 物理退火过程 1 加温过程 2 等温过程 3 冷却过程 7 模拟退火算法原理 等温过程等温过程是热力学过程的一种 即是指热力学系统在恒定温度下发生的各种物理或化学过程 在整个等温过程中 系统与其外界处于热平衡状态 例如 与恒温箱接触的一个气筒 可用一活塞对它缓慢地压缩 所做的功表现为流进容器内使气体的温度保持不变的能量 蓄电池在室温下缓慢充电和放电 都是近似的等温过程 8 模拟退火算法提出 等温下热平衡状态可用MonteKarlo方法模拟 但计算量大 蒙特卡罗方法的基本原理及思想如下 当所要求解的问题是某种事件出现的概率 或者是某个随机变量的期望值时 它们可以通过某种 试验 的方法 得到这种事件出现的频率 或者这个随机变数的平均值 并用它们作为问题的解 9 Metropolis准则 固体在恒定温度下达到热平衡的过程可以用MorteCarlo算法方法加以模拟 虽然该方法简单 但必须大量采样才能得到比较精确的结果 因而计算量很大 鉴于物理系统倾向于能量较低的状态 而热运动又妨碍它准确落到最低态 采样时着重选取那些有重要贡献的状态则可较快达到较好的结果 因此 Metropolis等在1953年提出了重要的采样法 即以概率接受新状态 10 模拟退火算法提出 1953年 Metropolis提出重要性采样法 即以概率接受新状态 称Metropolis准则 计算量相对MonteCarlo方法显著减少 1983年 Kirkpatrick Gelatt等提出模拟退火算法 并将其应用于组合优化问题的求解 1985 Cerny也独立提出此算法 11 Metropolis准则 固体在恒定温度下达到热平衡的过程可以用MorteCarol假设在状态xold时 系统受到某种扰动而使其状态变为xnew 与此相对应 系统的能量也从E xold 变成E xnew 系统由状态xold变为状态xnew的接受概率p 12 模拟退火算法与物理退火过程的相似性 13 模拟退火算法 流程 14 模拟退火算法 流程图 15 模拟退火算法 要素 16 模拟退火算法 要素 17 模拟退火算法 要素 18 模拟退火算法 要素 19 模拟退火算法 要素 20 模拟退火算法 要素 21 模拟退火算法 要素 22 模拟退火算法 要素 23 模拟退火算法的优缺点 优点 计算过程简单 通用 鲁棒性强 适用于并行处理 可用于求解复杂的非线性优化问题 缺点 收敛速度慢 执行时间长 算法性能与初始值有关及参数敏感等缺点 经典模拟退火算法的缺点 如果降温过程足够缓慢 多得到的解的性能会比较