模拟退火算法算法.ppt

文档介绍：模拟退火算法
Simulated Annealing Algorithm
SAA
模拟退火算法是什么?是怎样提出来的?
模拟退火算法(Simulated Annealing,SA)
是一种模拟物理退火的过程而设计的优化算法。
它的基本思想最早在1953年就被Metropolis提出,
但直到1983年Kirkpatrick等人才设计出真正
意义上的模拟退火算法并进行应用。
模拟退火算法的基本思想是怎样的?
模拟退火算法采用类似于物理退火的过程,
先在一个高温状态下(相当于算法随机搜索),然后逐渐退火,
在每个温度下(相当于算法的每一次状态转移)徐徐冷却
(相当于算法局部搜索),最终达到物理基态
(相当于算法找到最优解)。
简介
模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。
该算法在系统向着能量减小的趋势变化过程中,偶尔允许系统跳到能量较高的状态,以避开局部最小,最终稳定在全局最小。
简介
SAA属于随机模拟算法
模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法,意图是避免陷入局部极小解,早期用于组合优化,后来发展成一种通用的优化算法。
基本思想
SAA是基于Mente Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。另一方面,结合爬山法和随机行走。
SAA在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部优解能概率性地跳出并最终趋于全局最优。
模拟退火算法是一种通用的优化算法,目前已在工程中得到了广泛应用。
基本思路
首先在高温下进行搜索,此时各状态出现概率相差不大,可以很快进入“热平衡状态”,这时进行的是一种“粗搜索”,也就是大致找到系统的低能区域;
随着温度的逐渐降低,各状态出现概率的差距逐渐被扩大,搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。
一、模拟退火算法概述
二、模拟退火算法的马氏链描述及收敛性
三、模拟退火算法关键参数和操作设计
四、模拟退火算法的改进及其并行性
五、模拟退火算法的实现及应用
固体退火过程
Metropolis准则
组合优化与物理退火的相似性
模拟退火算法的步骤
第一节模拟退火算法概述
1 模拟退火算法概述
算法的提出
模拟退火算法最早的思想由Metropolis等(1953)提出,1983年Kirkpatrick等将其应用于组合优化。
—Optimization by simulated annealing, IBM Research Report
算法的目的
解决NP复杂性问题提供有效近似算法;
克服优化过程陷入局部极小;
克服初值依赖性。
固体退火过程
1、源于对固体退火过程的模拟;
2、采用Metropolis接受准则;
3、用冷却进度表控制算法进程,使算法在多项式时间里给出一个近似解。
固体退火过程的物理图像和统计性质是SAA的物理背景;Metropolis接受准则使算法跳离局部最优“险井”;而冷却进度表的合理选择是算法应用的前提。
1 模拟退火算法概述
固体退火过程
算法的基础