Simulated Annealing
固体退火的过程:
- 溶解:温度上升,粒子脱离平衡,最终从有序变为完全无序。
- 退火:温度下降,粒子逐渐停留在不同状态,从无序向有序发展。温度很低时,以一定结构排列。
1. Metropolis准则
(温度一定,)从状态
- 若
,转移。 - 若
,则转移的概率: 。
在给定温度下,进行足够多次状态转移后,系统将达到热平衡。
2. 算法框架
达到最小能量状态的三个条件:
- 初始温度足够高;
- 每个温度下进行充分的状态转移;
- 温度 T 的下降足够缓慢。
- 随机选择一个解
;序号 ,初始温度 ; - 判断是否满足「结束条件」;若满足,结束;若不满足:
- 如果在该温度下达到了「平衡条件」,降温到
; - 如果没到平衡条件:
- 随机选择
(邻域); - 如果
,则转移到 ;( ) - 否则,按概率
转移; - 回到判断「平衡条件」的一步;
- 随机选择
- 如果在该温度下达到了「平衡条件」,降温到
3. 参数选取
3.1 起始温度
一个合适的初始温度,应保证平稳分布中每一个状态的概率基本相等。
3.2 温度下降
等比例下降;
其它衰减函数;
3.3 平衡条件
每一温度下,何时认为已到达平衡而停止转移?
- 根据温度固定长度法;
- 某温度下转移次数达到阈值后才停止;
3.4 结束条件
- 阈值法;
- 固定降温次数法;
- 无变化控制法:指标函数值已无变化;
Last update:
June 4, 2021
Authors: