模拟退火算法PPT课件

最低能态？
2020/1/7
降温图像
离散函数图像
6
组合优化与物理退火的相似比较
• 从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在 解空间中随机寻找全局最优解
组合优化问题
金属物体
解 最优解 设定初温 Metropolis抽样过程 控制参数的下降 目标函数
粒子状态 能量最低的状态
熔解过程 等温过程
模拟退火算法
LOREM IPSUM DOLOR
2020/1/7
1
导论
• 模拟退火算法（Simulated Annealing，SA)是一种通用的优化算法。 目前，已在：生产调度、控制工程、计算机视觉、神经网络、图像 处理等工程领域中得到了广泛应用。
• 最早的思想是由N.Metropolis等人于1953年提出。1983年,S. Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于 Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物 理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟 退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率 突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最 优解能概率性地跳出并最终趋于全局最优。
退火的作用
(1) 降低硬度，改善切削加工性.
(2)消除残余应力，稳定尺寸，减少变形与裂纹倾向；
(3)细化晶粒，调整组织，消除组织缺陷。
(4)均匀材料组织和成分，改善材料性能或为以后热处理做组织准备。
2020/1/7
4
模拟退火算法的设计与原理猜想
• 物质自动趋向的最低能态与函数最小值之间有相似性！！！ • 我们能不能设计一种算法求函数最小值，就像物质”自动”地趋向
2020/1/7
11
模拟退火算法的流程图
初使化设定
随机产生一个初始解
扰动产生一个新解 No
是否接受? Yes
修改目前解 Yes
降温
缩减温度
No
No 是否达到中止条件?
Yes
2020/1/7
最佳解
12
2020/1/7
13
算法的关键参数和操作的设定
状态产生函数： 原则：设计状态产生函数（邻域函数）的出发点应该是 尽可能保证产生的候选解遍布全部的解空间。通常，状 态产生函数由两部分组成，即产生候选解的方式和候选 解产生的概率分布 方法：在当前状态的邻域结构内以一定概率方式（均匀 分布、正态分布、指数分布等）产生
高温
缓慢下降
高能状态
低温
低能状态
2020/1/7
3
模拟退火算法的思想
物理退火过程
加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态； 等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化 总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态； 冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到 低能的晶体结构。
exp(-(E(rt)-E(r))/t)>random(0,1), 则令r=rt. Step2.2 不满足内循环停止条件时12..，达达到到重终迭复止代S温次te度数p2.1
Step3 外循环
3. 最优值连续若干步

Step3.1 降温t = decrease(t)
保持不变
Step3.2 如不满足外循环停止条件，则转Step2；否则算法结束
• 模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突 跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结 构的优化算法。
2020/1/7
2
模拟退火算法的思想
• 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其 徐徐冷却；加温时，固体内部粒子随温升变为无序状，内能增大， 而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常 温时达到某种稳定状态，基态，内能减为最小。
2020/1/7
8
基本步骤
给定初温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 算法终止准则满足； 输出算法搜索结果。
冷却 能量
2020/1/7
7
模拟退火算法原理
• 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其 徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大， 而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常 温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时 趋于平衡的概率为exp（-Δ E/(kT)），其中E为温度T时的内能，Δ E 为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将 内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合 优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当 前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并 逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于 蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却 进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子 Δ t、每个t值时的迭代次数L和停止条件S。
2020/1/7
9
影响优化结果的主要因素
给定初温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 算法终止准则满足； 输出算法搜索结果。
2020/1/7
10
模拟退火算法具体步骤
Step1 设定初始温度t = tmax, 任选初始解r = r0
Step2 内循环
1. 目标函数均值稳定 2. 连续若干步的目标
Step2.1 从r的邻域中随机选一个值解变r化t,较计小 算r和rt对应目标函 数值, 如
rt对应目标函数值较小，则令r =3.r固t;定否的则抽样若步数