Simulated Annealing Algorithm

Simulated Annealing Algorithm

模拟退火算法

• 来源于固体退火原理

  • 将固体加热至充分高，固体内部粒子随之变为无序状，内能 增加
  • 再让固体徐徐冷却，内部例子随之有序
  • 到达常温状态时，内能减为最小

• 用固体退火模拟组合优化问题

  • 目标函数值f视为内能E，控制参数t视为温度T
  • 由初始解i、控制参数初值t开始，对当前解重复 产生新解->计算目标函数增量->接受或舍弃的迭代，并 逐步衰减t值
  • 算法终止时，当前解即为所得近似最优解

• 退火过程由Cooling Schedule控制，包括控制参数初值t、衰减 因子$\Delta t$、迭代次数L、停止条件S

算法

• 初始化：初始温度$t_0$（充分大）、初始解$i_0$、迭代次数L
• 产生新解$i_1$，计算目标函数增量$\Delta f=f(i_1)-f(i)$
• 若$\Delta f<0$则接受$i_1$作为新解，否则以概率 $\exp^{\Delta f/f(i_0)}$接受$i_1$作为新解
• 若满足终止条件则算法结束
  • 若干次新解都不被接受：当前解“能量”低
  • 迭代次数达到上限
• 否则减小温度为$t_1$继续迭代

说明

• 解生成器：应该可以通过简单变换即可产生新解，便于减少每次 迭代计算新解耗时

  • 比如对新解全部、部分元素进行置换、互换等
  • 需要注意的是，这决定了新解的领域结构，对冷却的进度表 选取有影响

• 新解是否被接受采用的是Metropolis准则

模拟退火算法性质

• 与初值无关
• 具有渐进收敛性
• 具有并行性
• 在理论上被证明是以概率1收敛于全局最优解的算法
• 能够跳出局部最优解

应用

• VLSI：目前退火模拟算法的应用实例，几乎可以完成所有VLSI 设计工作
• 神经网络：模拟退火算法能够跳出局部最优解
• 图像处理：用于进行图像恢复工作
• 其他问题：还可以用于其他各种组合优化问题