模拟退火算法应用方法,模拟退火算法的改进方法

图3-2 模拟退火算法流程示意图

在把模拟退火算法应用于最优化问题时，一般可以将温度T当做控制参数，目标函数值f视为内能E，而固体在某温度T时的一个状态对应一个解。然后算法试图随着控制参数Ｔ的降低，使目标函数值f(内能E)也逐渐降低，直至趋于全局最小值(退火中低温时的最低能量状态)，就像固体退火过程一样。

就函数最小值问题来说，模拟退火的主要思想是：在搜索区间（二维平面中）随机游走（即随机选择点），再以Metropolis抽样准则，使随机游走逐渐收敛于局部最优解。而温度即是Metropolis算法中的一个重要控制参数，可以认为这个参数的大小控制了搜索过程向局部或全局最优解移动的快慢。

冷却参数表、领域结构和新解产生器、接受准则和随机数产生器（即Metropolis算法）一起构成算法的三大支柱。

Metropolis是一种有效的重点抽样法：系统从能量一个状态变化到另一个状态时，相应的能量从E1变化到E2，概率为p = exp[ - (E2- E1)/T ]。如果E2 < E1，系统接收此状态，否则，以一个随机的概率接收此或丢弃此状态。这种经常一定次数的迭代，系统会逐渐趋于一引稳定的分布状态。

重点抽样时，新状态下如果向下则接受（局部最优），若向上（全局搜索），以一定机率接受。模拟退火方法从某个初始解出发,经过大量解的变换后,可以求得给定控制参数值时组合优化问题的相对最优解。然后减小控制参数T的值，重复执行Metropolis算法，就可以在控制参数T趋于零时，最终求得组合优化问题的整体最优解。控制参数的值必须缓慢衰减。

其中温度是一个Metropolis的重要控制参数，模拟退火可视为递减控制参数T时Metroplis算法的迭代。开始T值大，可能接受较差的恶化解，随着T的减小，只能接受较好的恶化解，最后在T趋于0时，就不再接受任何恶化解了。

在无限高温时，系统立即均匀分布，接受所有提出的变换。T的衰减越小，T到达终点的时间越长，但可使马可夫链长越小，到达准平衡分布的时间越短，

模拟退火算法使用Metropolis准则产生组合优化问题解的序列，并使用对应的转移概率P确定是否接受当前解到新解的转移。

同样的问题，如果使用蒙特卡洛(MonteCarlo)算法模拟，需要大量采样，工作量很大。因而1953年Metropolis提出了这样一个重要性采样的方法， 即设从当前状态i生成新状态j。若新状态的内能小于状态i的内能(即Ej<Ei)，则接受新状态j作为新的当前状态； 否则，以概率接受状态j， 这就是通常所说的Metropolis准则。

Metropolis准则，其实就是以概率p接受新状态。

若在温度T，当前状态i → 新状态j，则概率p满足：

• 当Ej < Ei时，接受新状态的概率p=1, 即完全接受 j 为当前状态；
• 当Ej ≥ Ei时，若概率 p=exp[-(Ej-Ei)/T]大于[0,1)区间的随机数，则仍接受状态 j 为当前状态；若不成立，则保留状态 i 为当前状态。

温度T越小，则降温概率p就越小；温度越高，降温概率p就越大，p越大，则j状态是重要状态的概率就越大。若j是重要状态，则取代i成为当前状态，否则舍弃新状态。再重复以上新状态产生过程。

很明显，在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。这与不同温度下热运动的影响完全一致，在温度趋于零时，就不能接受任何成立时的新状态j了。

上述接受新状态的准则称为Metropolis准则，相应的算法被称为Metropolis算法。

图6-1

最简单的状态产生函数：ω’ = ω R (R是个随机数）。

模拟退火算法用冷却进度表来控制算法的进程，是算法在控制参数T徐徐降温并趋于零时最终求得组合优化问题的相对全局最优解。其中优化问题的一个解i及其目标函数f(i)分别与固体的一个微观状态ｉ及其能量Ｅi相对应。

模拟退火算法新解的产生和接受可分为如下四个步骤：

第1步，由一个产生函数从当前解产生一个位于解空间的新解。为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第2步，计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第3步，判断新解是否被接受。判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。

第4步，当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率收敛于全局最优解的全局优化算法。

状态空间，即解空间，也称为搜索空间，是经过编码的可能解组成的集合。

应尽可能保证产生的候选解遍布整个状态空间，可采用附加扰动、随机产生、移位、平滑、边界取值等多种算子作为模拟退火的状态产生函数。状态产生函数通常由产生的候选解的方式和候选解产生的概率分布两部分组成。候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等。

• 状态转移概率是指从一个状态向另一个状态的转移概率。
• 通俗的理解是接受一个新解为当前解的概率。
• 它与当前的温度参数T有关，随温度下降而减小。
• 一般采用Metropolis准则。

实验表明，初始温度越高，得到高质量解的概率越大，但算法计算的时间越长。兼顾算法求解的质量和执行效率，选择初温的方法常有:随机产生一组状态，确定最大值和最小值间的差值d，利用函数得到初温，如 T0= dp，其中p为初始接受概率; 或均匀抽样一组状态，以各状态的目标值的方差为初温。

冷却进度表是指从某一高温状态T向低温状态冷却时的降温管理表，也即温度衰减函数，也可称为退火策略。

1. 最简单的控制参数衰减函数（指数降温）为：