模拟退火算法.pptx

文档介绍：模拟退火算法(Simulation Annealing)及其改进
目录
搜索算法简介
模拟退火算法的原理
模拟退火算法的应用
英文文献介绍
参考文献
搜索问题
最小最优解的搜索
局部最优
全局最优
除对当前的位置外,对环境无任何感知。
搜索算法
盲目搜索与启发式搜索
按照预定的控制策略实行搜索,在搜索过程中获取的中间信息不用来改进控制策略,称之为盲目搜索,反之,称为启发式搜索。
盲目搜索
深度优先、广度优先、代价优先、向前、向后、双向等
启发式搜索
爬山法、模拟退火算法、遗传算法、蚁群算法、粒子蚁群算法等等
贪心算法
222
模拟退火算法的起源
物理退火过程
加温过程
等温过程
冷却(退火过程)
1953年,由Metropolis最早提出模拟退火算法的思想
1983年,由kirkpatrick等将模拟退火的思想成功引入组合优化领域。
目前,模拟退火算法已经应用到各门学科中以解决非线性系统的优化问题。
理论上已证明,模拟退火算法是一个全局最优算法,而且以概率1接近最优值。
Metropolis接受准则
Metropolis
模拟退火算法与物理退火的关系
模拟退火算法
物理退火
解
粒子状态
最优解
能量最低态
设定初温
熔解过程
Metropolis采样过程
等温过程
控制参数T下降
冷却
目标函数
能量
模拟退火算法的基本流程
流程图及伪代码