模拟退火算法如何应用于学习？

1.简介 模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 　　 ————百度百科 简而言之，模拟退火是一种随机化算法，常用于信息学竞赛中骗取高分，但因为其为随机化算法，所以不是很稳定，少则10分，多则AC，这取决于你的RP了（doge）。它与爬山算法最大的不同是，在寻找到一个局部最优解时，赋予了它一个跳出去的概率，也就有更大的机会能找到全局最优解。 2.原理 原理在这里就不过多说了，因为可能对于程序的编写没有多大的影响，下面直接给出百度百科的原理介绍： 模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。 简单来说就是，随机生成一个新的解，然后将其与先前的最优解进行比较，若生成的新解更优，则更新最优解，否则以exp（-ΔT/T）的概率接受它，exp是计算以自然底数为底的指数的函数，而这里的接受并不是指将新解作为最优解，而是更新步骤。 3.过程 　　1）降温 　　　　模拟退火有三个重要的参数，分别为初温t、降温系数ΔT和终温Tk，这三个参数关系到你的程序结果的准确性，当然，如何选择恰当的参数需要你的经验和RP了。其中，t是一个比较大的数，ΔT 是一个略小于 1 的正数，Tk 是一个略大于 0 的正数。我们先设当前温度T为初温，然后每次降温时 T 乘上 ΔT，直到 T≤Tk 为止 　　　　大致过程如下： 　　　　可以看出，随着温度的降低，解逐渐稳定下来，并逐渐集中在最优解附近。 　　2）生成新解 　　　　生成新解的基本思想就是使用rand随机生成一个值，并带入对应的计算函数就可以得出一个新解了，而计算函数是根据对应题目来决定的，往往都不相同。 　　3）调参 　　　　这可能是模拟退火中最重要的一步了，一个好的参数可一让你AC你所作的题，而一个坏的参数，可能让你的分数比暴力还低，一般来讲，如果答案不是最优，有以下几种调法：调大ΔT，调整t和Tk或多跑即便退火，如果太非的话，这边还是建议您直接打正解吧（ 　　4）调整 　　　　如果新解更优，接受这个解。否则我们以一定概率接受这个解。设ΔW为新解和当前解的差 ΔW>0 。我们希望的是：T越大时概率越大，ΔW越小时概率越小。个随机数。当然，如果 ΔW很大或很小的话这样子就可能会出问题。我们可以通过合理选择r的范围来解决问题。 　　5）其他 　　　　模拟退火中，还有一件重要的事就是选好随机数种子，和调参一样，种子选好了收益整个比赛，种子太臭，像11451419就会出事，下面是我的惨痛教训 　　　　 　　　　 　　　　程序开始时，我们要先srand(一个常数)。这个常数可以决定分数。你可以使用 233333，2147483647，甚至某个八位质数。 　　　　可以用一个全局变量记录所有跑过的模拟退火的最优解，每次从那个最优解开始继续模拟退火，可以减小误差。 4.实际应用 　　这里以洛谷1337 [JSOI2004]平衡点 / 吊打XXX为例，讲解模拟退火的实际应用。 　　题目要使整个系统的能量最小。那么我们只要用模拟退火跑出这个最小值即可。