模拟退火算法讲解ppt课件.pptxVIP

模拟退火算法 算法的提出 模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。 算法的目的 解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。 什么是退火： 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。 物理退火过程 加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态； 等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态； 冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。  热力学中的退火现象指物体逐渐降温时发生的物理現象： 温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，annealing）时，可达到最低能量状态；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形。 模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性 从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解 数学表述 在温度T，分子停留在状态r满足Boltzmann概率分布 模拟退火算法基本思想：在一定温度下，有哪些信誉好的足球投注网站从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，有哪些信誉好的足球投注网站过程以概率1停留在最优解。 在同一个温度T，选定两个能量E1E2，有 Boltzman概率分布告诉我们： （1）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率 （2）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。 （3）随着温度的下降，能量最低状态对应概率越来越大；温度趋于0时，其状态趋于1 Metropolis准则（1953）——以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。 Metropolis准则（1953）——以概率接受新状态 若在温度T，当前状态i → 新状态j 若EjEi，则接受 j 为当前状态；否则，若概率 p=exp[-(Ej-Ei)/kBT] 大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立则保留状态 i 为当前状态。 p=exp[-(Ej-Ei)/kBT] 在高温下，可接受与当前状态能量差较大的新状态； 在低温下，只接受与当前状态能量差较小的新状态。 相似性比较 组合优化问题 金属物体 解 离子状态 最优解 能量最低的状态 设定初温 溶解过程 Metropolis抽样过程 控制参数的下降 等温过程 冷却过程 目标函数 能量 基本步骤 给定初温t=t0，随机产生初始状态s=s0，令k=0； Repeat Repeat 产生新状态sj=Genete(s)； if min{1,exp[-(C(sj)-C(s))/tk]}=randrom[0,1] s=sj; Until 抽样稳定准则满足； 退温tk+1=update(tk)并令k=k+1； Until 算法终止准则满足； 输出算法有哪些信誉好的足球投注网站结果。 算法程序核心内容 三个函数 新状态sj=Genete(s) if min{1,exp[-(C(sj)-C(s))/tk]}=randrom[0,1] s=sj; tk+1=update(tk) 两个准则 抽样稳定准则（内循环终止准则） 算法终止准则（外循环终止准则） 状态产生函数 原则 产生的候选解应遍布全部解空间 方法 在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生 状态接受函数的产生 原则 (1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率； (2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小； (3)当温度趋于零时，只能接受目标函数下降的解。 方法 具体形式对算法影响不大 一般采用min[1,exp(-∆C/t)] 初温的设定 收敛性分析 通