模拟退火算法如何应用于学习？
摘要：1.简介 模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 ——
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为例，讲解模拟退火的实际应用。
题目要使整个系统的能量最小。那么我们只要用模拟退火跑出这个最小值即可。
代码如下：
#include <bits/stdc++.h>
#define re register
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
int n,sx,sy;
double ansx,ansy; //全局最优解坐标
double ans = 1e18,t; //全局最优解，温度t
const double delta = 0.9913;
struct node{
int x,y,w;
}a[1010];
inline double calc_energy(double x,double y){
double rt=0;
for (re int i=1;i<=n;i++) {
double deltax=x-a[i].x,deltay=y-a[i].y;
rt+=sqrt(deltax*deltax+deltay*deltay)*a[i].w;
}
return rt;
}
inline void simulate_anneal(){
double x = ansx,y = ansy;
t = 2000; //设初温
while (t>1e-14){
double X = x+((rand()<<1)-RAND_MAX)*t;
double Y = y+((rand()<<1)-RAND_MAX)*t;
double now = calc_energy(X,Y);
double Delta = now-ans; //当前最优解与新解的差
if (Delta<0){
x = X;
y = Y;
ansx = x,ansy = y,ans = now;
}
else if (exp(-Delta/t)*RAND_MAX>rand()){ //若不是当前最优，则有一定概率接受它
x = X;
y = Y;
}
t*=delta;
}
}
inline void Solve() { //多跑几遍模拟退火，减小误差
ansx=(double)sx/n,ansy=(double)sy/n; //从平均值开始更容易接近最优解
simulate_anneal();
simulate_anneal();
simulate_anneal();
}
int main(){
srand(11451411919); srand(rand()); srand(rand());
n = read();
for (re int i=1;i<=n;i++){
a[i].x = read(),a[i].y = read(),a[i].w = read();
sx+=a[i].x,sy+=a[i].y;
}
Solve();
printf("%.3f %.3f\n",ansx,ansy);
return 0;
}
Over~