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 设计工作
  • 神经网络:模拟退火算法能够跳出局部最优解
  • 图像处理:用于进行图像恢复工作
  • 其他问题:还可以用于其他各种组合优化问题
Author

UBeaRLy

Posted on

2019-07-21

Updated on

2019-07-21

Licensed under

Comments