模拟退火

发布于 2019-11-29  27 次阅读


模拟退火算法(Simulate Anneal,SA)是一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Černý在1985年也独立发明此演算法。模拟退火算法是解决TSP问题的有效方法之一。
要讲模拟退火,首先要知道金属退火。
简单来说,就是将金属加热到一定温度,保持足够时间,然后以适宜速度冷却。
模拟退火的原理也和金属退火的原理近似:将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始:每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。
状态空间与状态产生函数
1)搜索空间也称为状态空间,它由经过编码的可行解的集合组成。
  2)状态产生函数(邻域函数)应尽可能保证产生的候选解遍布全部解空间。通常由两部分组成,即产生候选解的方式和候选解产生的概率分布。
  3)候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得。
  4)概率分布可以是均匀分布、正态分布、指数分布等。
状态转移概率
1)状态转移概率是指从一个状态向另一个状态的转移概率。
  2)通俗的理解是接受一个新解为当前解的概率。
  3)它与当前的温度参数T有关,随温度下降而减小。
  4)一般采用Metropolis准则。
内循环终止准则
也称Metropolis抽样稳定准则,用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括:
  1)检验目标函数的均值是否稳定。
  2)连续若干步的目标值变化较小。
  3)按一定的步数抽样。
外循环终止准则
即算法终止准则,常用的包括:
  1)设置终止温度的阈值。
  2)设置外循环迭代次数。
  3)算法搜索到的最优值连续若干步保持不变。
  4)检验系统熵是否稳定。
模拟退火算法新解的产生和接受可分为如下四个步骤:
第一步是由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis准则: 若Δt′


花开花败总归尘。 阴阳化生,清浊自分。