深⼊理解模拟退⽕算法（SimulatedAnnealing） 本⽂将对模拟退⽕算法（Simulated Annealing)进⾏介绍，深⼊理解这个算法。
模拟退⽕算法和上⼀篇⽂章中的Metropolis算法有着紧密的联系，在这⾥将详细探讨这种关系。
我们先从这个算法要解决的问题出发，逐步引出相应的算法。（pku， sewm，shinning）
⼀. 问题
⼈们经常遇到这样的问题：在某个定义域S内，求某个函数f(x)的最⼩值，形式化为Min f(x)，x属于S。这是⼀个优化问题，根据f(x)的形式不同，有很多的优化算法来解决这类问题，简单的有穷举法（适⽤于定义域⼩的情况），图解法，数学分析法（求导数法）等精确算法，如果很难精确求得，还有很多的近似求解法，如贪⼼法（如爬⼭法，最速下降法，梯度下降法），随机模拟⽅法（MCMC等）。本⽂将介绍的模拟退⽕⽅法属于随机模拟⽅法，但是是可以求得精确解的（概率为1求得全局优化解），神奇吧！
⼆. 算法的基本思想
那怎么求解f(x)的最⼩值呢？它的思想是利⽤Gibbs分布：S中的⼀个点x的概率满⾜分布：p(x, T) = EXP(-f(x)/T)/Z，Z是归⼀化因⼦。现在假设T-> 0，可以看到f(x)越⼩，p(x,T)越⼤，意味着f(x)以⾮常⼤ 的概率取得最⼩值，这就是基本思想。现在是怎么操作的问题，这个分布是确定的，T已知，f(x)的表达式已知（对⼀个值，就是可以计算出来量），p(x,T)这个分布的形式就已知了，这时候我们利⽤去对这个分布抽样，在样本中，出现最多的⾮常有可能就是我们要求的最⼩值。似乎问题都解决了，然⽽如果直接把T设为很⼩，这个算法的计算时间太长了，因为S可能太⼤！不实⽤！ 因此，我们采⽤了层层推进的办法，我们先把T设为⼀个较⼤的值Ti，然后在这个Ti的情况下采样，这个时候由于约束条件的限制，p(x，Ti)的定义域只是S的⼦集，因此速度较快，在采样分布稳定之后，再通过⼀个T的控制函数g(Ti, Tj)（是⼀个单调不增函数，T>=0）得到⼀个更⼩的Tj，然后在Tj的情况下，再对分布p(x, Tj)采样，直到达到稳定分布，我们可以知道这个时候f(x)⽐起Ti时候的f(x)变得更加⼩了，直到达到较⼩T的时候（⾃⼰设定）我们可以认为达到了优化解的情况。
三.模拟退⽕算法（simulated annealing)
在这⼀节，我们把算法总结在这⾥：
设定起始值T0，T的控制函数g(Ti, Tj)
甘氨酸亚铁
他有个二弟汉寿亭侯while(T还没有达到我们设定的最⼩值）
{
对这时的T情况下的Gibbs分布p(x, T)⽤Metropolis模拟算法进⾏采样x(t)，直到达到稳定状态为⽌, 然后进⼊下⼀次循环（这句话的伪代码描述见下⾯）
}粘罕
循环中对p(x,T)进⾏Metropolis采样的算法我们放在这⾥，它也是⼀个循环
已知T，当前的样本x(t)(来⾃上⼀次循环的最后⼀个样本)，建议分布h(x(t), x(t+1))
while(未达到稳定状态）
中国和声{
先抽取⼀个建议样本y ~ h(x(t), x(t+1))
if( f(y) < f(x(t) ) { 令x(t+1) = y; }
else
邵玥
{
全球紧急卫生事件令a = min{1， p(x(t+1), T)/p(x(t), T)};
然后抽取u ~ Uniform(0, 1);
if( u < a) {x(t+1) = y};
else { x(t+1) = x(t) };
}
}
上⾯这个循环完全就是Metropolis算法，详细的解释可以看我的上⼀篇⽂章： 。
（pku， sewm，shinning）
⾄于，这个算法的名字：模拟退⽕，来⾃于我们这个过程和物理学中打造钢铁时候的加热-等温-降温过程，这⾥的T为温度，f(x)可以令为能量，上述的Metropolis过程就相当于等温过程，p(x, T)就是在T时候系统所处状态的概率分布，可以明显的看到，这个概率与系统的能量和温度密切相关，⼤部分的资料都是先将这个物理过程，然后再讲算法本⾝，如果⼈们不熟悉这个物理过程，简单的介绍反⽽会使得⼤家对这个算法搞不清楚。因此，本⽂为了叙述清楚，没有描述这个过程，反⽽更加的清楚！ （pku， sewm，shinning）
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议