模拟退火与算法研究 .ppt

模拟退火算法原理与应用 报告提纲 一、模拟退火算法概述 二、模拟退火算法特点及改进 三、模拟退火算法的主要应用 一、模拟退火算法概述 1、物理退火 2、模拟退火 1、物理退火 退火是将工件加热到预定温度，保温一定的时间后缓慢冷却的金属热处理工艺。退火的目的在于：①改善或消除钢铁在铸造、锻压、轧制和焊接过程中所造成的各种组织缺陷以及残余应力，防止工件变形、开裂。②软化工件以便进行切削加工。③细化晶粒，改善组织以提高工件的机械性能。④为最终热处理（淬火、回火）作好组织准备。 物理退火 He heats the metal, then slowly cools it as he hammers the blade into shape. ?? If he cools the blade too quickly the metal will form patches of different composition; ?? If the metal is cooled slowly while it is shaped, the constituent metals will form a uniform alloy. 2、模拟退火 模拟退火（Simulated Annealing，简称SA）是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。“模拟退火”的原理和金属退火的原理近似 。 模拟退火 模拟退火 粒子状态 解 能量最低态 问题最优解 熔解过程 设定初温 等温过程 采样过程 冷却 控制参数下降 能量 目标函数 物理退火 模拟退火 二、模拟退火算法原理及改进 1、模拟退火算法原理 2、模拟退火算法要素 3、模拟退火算法特点及改进 1、模拟退火算法原理 模拟退火算法可以分解为解空间、目标函数和初始解三部分。 　　 模拟退火的基本思想: 　　 (1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L 　 (2) 对k=1，……，L做第(3)至第6步： 　　 (3) 产生新解S′。 　　 (4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数 　　 (5) 若Δt′0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解. (6) 如果满足终止条件则输出当前解作为最优解，结束程序。　 终止条件通常取为连续若干个新解都没有被接受时终止算法。 　　 (7) T逐渐减少，且T-0，然后转第2步。 模拟退火算法原理 1) 随机产生一个初始解x0，令xbest＝ x0 ，并计算目标函数值E(x0); 2) 设置初始温度T(0)=To，迭代次数i = 1; 3) Do while T(i) Tmin 1) for j = 1~k 2) 对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目 标函数值E(xnew) ，并计算目标函数值的增量ΔE = E(xnew) - E(xbest) 。 3) 如果ΔE ＜0，则xbest = xnew； 4) 如果ΔE ＞0，则p = exp(- ΔE /T(i)); 1) 如果c = random[0,1] p， xbest = xnew; 否则xbest = xbest。 5) End for 4) i = i ＋ 1； 5) End Do 6) 输出当前最优点，计算结束。 2、模拟退火算法要素 1、状态空间与状态产生函数（邻域函数） 2、状态转移概率（接受概率） p 3、冷却进度表T(t) 4、初始温度T(0) 5、内循环终止准则 6、外循环终止准则 3、模拟退火算法特点及改进 算法设计要素： 编码策略（ “个体表示”与“问题解”的映射关系） 初始解的产生（从什么位置开始搜索） 邻域函数的设计（下一个解的产生概率与当前解之 间距离[包括方向和步长]的关系） 新解产生策略（随机，确定） 接受策略（贪心算法） 模拟退火算法特点及改进 特点： 快速收敛于局部最优解 遇到flat无所适从 模拟退火算法特点及改进 快速收敛于局部最优 模拟退火算法特点及改进 遇到flat则无所适从 模拟退火算法特点及改进 改进： (1) 设计合适的状态产生函数，使其根据搜索进程的需要 表现出状态的全空间分散性或局部区域性。 (2) 设计高效的退火策略。 (3) 避免状态的迂回搜索。 (4) 采用并行搜索结构。 (5) 为避免陷入局部极小，改进对温度的控制方式 (6) 选择合适的初始状态。 (7) 设计合适的算法终止准则。 模拟退火算法特点及改进 也可通过增加某些环节而