模拟退火

说文解字

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置

讲得真好啊。

模拟退火的原理也和金属退火的原理近似:我们将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始:每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。

可以证明,模拟退火算法所得解依概率收敛到全局最优解。

退火、正火、淬火和回火

  • 淬火硬化
  • 淬cuì火,俗称蘸(zhàn)火,金属和玻璃的一种热处理工艺。把合金制品或玻璃加热到一定温度,随即在含有矿物质的水、油或空气中急速冷却,一般用以提高合金的硬度和强度。淬火可增强钢与铸铁的强度和硬度。急速冷却的速率也会影响物质表面硬度和心部硬度。淬火后物质会变脆,所以通常会再进行回火处理,目的是降低物质的脆度。螺丝、齿轮、转动轴、金属块等物品常使用淬火处理。
    淬火后得到马氏体,组织变硬,也就是晶粒变得粗大。
  • 回火可以稍微降低硬度和强度,使钢不太脆
  • 淬火后,钢变硬但是太脆了,动不动就断,那么好,我们在加热它,这个温度要温和的多了,然后再慢慢冷却下来,目的是组织变得细小,记住,晶粒细小的组织性能好,放在钢上,就是硬度高、强度大、塑形好。
  • 退火
  • 将钢加热、保温后缓慢冷却

为什么不模拟淬火呢?急速冷却一下。

简介

模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。以图1为例,模拟退火算法在搜索到局部最优解A后,会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点,于是就跳出了局部最大值A。

模拟退火算法描述:

  • 若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解),则总是接受该移动
  • 若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)

随着温度T的降低,P(dE)会逐渐降低。

我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(dE)来接受这样的移动。

参考

https://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html