什么是模拟退火算法?

2020-04-27T14:34:00

算法介绍

模拟退火算法最早由Metropolis在1953年提出,Kirkpatrick等人在1983年成功地将模拟退火算法用于组合优化问题求解。作为求解复杂组合优化问题的一种有效方法,模拟退火算法已经在许多工程和科学领域得到广泛的应用。
模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动。退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置。
模拟退火的原理也和金属退火的原理近似:可将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;分子的能量,就是它本身的动能;而搜寻空间内的每一点,也像空气分子一样带有“能量”,以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始:每一步先选择一个“邻居”,然后再计算从现有位置到达“邻居”的概率。
在模拟退火算法中,把某类优化问题的求解过程与统计力学中的热平衡问题进行对比,通过模拟高温物体退火过程的方法,来找到优化问题的全局最优或近似全局最优解。

演算步骤

模拟退火算法新解的产生和接受可分为如下四个步骤:
1.由一个产生函数从当前解产生一个位于解空间的新解;为便于后续的计算和接受,减少算法耗时,通常选择由当前新解经过简单地变换即可产生新解的方法,如对构成新解的全部或部分元素进行置换、互换等,注意到产生新解的变换方法决定了当前新解的邻域结构,因而对冷却进度表的选取有一定的影响。
2.计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生,所以目标函数差的计算最好 按增量计算。事实表明,对大多数应用而言,这是计算目标函数差的最快方法。
3.判断新解是否被接受,判断的依据是一个接受准则,最常用的接受准则是Metropolis准则: 若 Δt′<0 则接受 S′作为新的当前解 S,否则以概率 exp(-Δt′/T) 接受 S′作为新的当前解S。
4.当新解被确定接受时,用新解代替当前解,只需将当前解中对应于产生新解时的变换部分予以实现,同时修正目标函数值即可。此时,当前解实现了一次迭代。可在此基础上开始下一次迭代。而当新解被判定为舍弃时,则在原当前解的基础上继续下一次迭代。
模拟退火算法与问题的初始状态无关,算法求得的解也与初始解状态S(是算法迭代的起点)无关;模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法;模拟退火算法具有并行性。

伪代码

s := s0; e := E(s)                           // 设定目前状态s0,其能量E(s0)
k := 0                                       // 评估次数k
while k < kmax                               // 若还有时间(评估次数k还不到kmax)
  sn := neighbour(s)                         //   随机选取一邻近状态sn
  en := E(sn)                                //   sn的能量为 E(sn)
  if random() < P(en-e, k)) then             //   决定是否移至邻近状态sn
    s := sn; e := en                         //     移至邻近状态sn
  k := k + 1                                 //   评估完成,次数k加一
return s                                     // 回传状态s

参数问题

模拟退火算法的应用广泛,可以求解NP完全问题,但其参数难以控制,其主要问题有以下三点:
(1) 温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一:初始温度高,搜索到全局最优解的可能性大,但因此要花费大量的计算时间;反之,则可节约计算时间,但全局搜索性能可能受到影响。实际应用过程中,初始温度一般需要依据实验结果进行若干次调整。
  (2) 退火速度问题。
  模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说,同一温度下的“充分”搜索(退火)是相当必要的,但这需要计算时间。实际应用中,要针对具体问题的性质和特征设置合理的退火平衡条件。
  (3) 温度下降问题。
  温度下降问题也是模拟退火算法难以处理的问题之一。实际应用中,由于必须考虑计算复杂度的切实可行性等问题,常采用如下所示的降温方式:
T(t+1)=k×T(t)
式中k为正的略小于1.00的常数,t为降温的次数。

当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »