模拟退火是模拟物理上退火方法，通过N次迭代（退火），逼近函数的上的一个最值（最大或者最小值）。比如在下面函数去逼近最大值C点
模拟退火算法得益于材料统计力学的研究成果。
鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。
如果用粒子的能量定义材料的状态，退火算法用一个简单的数学模型描述了退火的过程。假设材料在状态i下的能量为E(i),那么材料在温度T时从状态i进入状态j就应该遵从以下规律：
（1）如果E(j)<=E(i)，那么级接收该状态。
（2）如果E(j)>E(i),那么就以一定的概率进入该状态：exp{(E(i)-E(j))/KT}
K为物理学中的玻尔兹曼常数，T为材料的温度
代码架构
double T=2000; //表示初始的温度为0.99
double dt=0.999; //表示降温系数
double eps=1e-14; //相对于1的负14次方，就是最后退出循环的温度
while(T<eps)
{
//------------------
//进行一次退火操作
//------------------
T*=dt; //降低温度
}
我们要求的目标无法是两个：自变量x和对应的目标函数最值f(x)
刚才我们说了x0相当于是一个粒子，所以我们会进行一个无序运动，也就是向左或者向右随机移动：移动的幅度和当前的温度T有关。
温度T越大，移动的幅度越大。温度T越小，移动的幅度就越小。这是在模拟粒子无序运动的状态。
假设我们移动到了x1处，那么这个点对应的f(x1)很明显答案是优于（大于）当前的f(x0)。
因此我们将答案进行更新。也就是将初始值进行替换：x0=x1,f(x0)=f(x1)。这是一种贪心的思想。
以一定概率接受(Accept)更差的状态
为什么需要按照一定的概率接受更差的状态。因为可能在一个较差的状态旁边会出现一个更加高的山峰
如果我们鼠目寸光，只盯着右半区，很容易随着温度的下降、左右跳转幅度的减小而迷失自己，最后困死在小山丘中。
而我们如果找到了左边山峰的低点，以一定的概率接受了它（概率大小和温度以及当前的值的关键程度有关），会在跳转幅度减少之前，尽可能找到最优点。
那么我们以多少的概率去接受它呢？我们用一个公式表示：exp{ Δf / KT }
注意
- 如果随机后的函数值如果结果更好，我们一定选择它(即x0=x1,f(x0)=f(x1));
- 随机后的函数值如果结果更差，我们以exp{ Δf / KT }的概率接受它
- e是自然对数，约等于2.71。我们可以把右上角这一坨 Δf / KT值看成一个整体x:
而exp{x}的函数图像为：
而如果需要用exp{x}表示一个概率，那么x【Δf / KT】的取值范围只能为负数。
负数部分的值域是在(0,1)开区间内，x越小，越接近0，越大越靠近1。
K其实是个物理学玻尔兹曼常数，我们在代码中不会用到。
T就是当前的温度。所以实际上这个分母就是T，K当做1使用。
Δf：
关于接受概率e{x}和KT以及Δf的关系：
当T越大时(温度越高)，由于是Δf一个负数，所以Δf / KT算出来的值会越大。比如-1 / 1000 等于 -0.001，很明显-0.001 > -1，由于e{x}是个单调递增函数，所以温度越高时，接受的概率就越大。
Δf越小【负的越多】，说明答案越糟糕，那么接受的概率就越小。
①对rand()函数
- rand()函数可以默认拿到[0,32767]内的随机整数
- RAND_MAX = 32767，可以看作常量。本质是宏定义: #define RAND_MAX 32767
- rand() * 2 的范围是[0,32767 * 2]
- rand() * 2 - RAND_MAX 的范围是[-32767, 32767]
②对exp()函数
- exp(x)代表e的x次方
③关于exp((df - f) / T) * RAND_MAX > rand()
- 目的是要概率接受，但是exp{x}是个准确值，所以从理论上我们可以生成一个（0,1）的随机数，如果exp{x}比(0,1)这个随机数要大，那么我们就接受。
- 但是由于rand()只能产生[0,32767]内的随机整数，化成小数太过麻烦。所以我们可以把左边乘以RAND_MAX（也就是把概率同时扩大32767倍），效果就等同exp{x}于比(0,1)了。
double T = 20000; //代表开始的温度
double dT = 0.999; //代表系数delta T
double eps = 1e-14; //相当于0.0000000000000001
//用自变量计算函数值,这里可能存在多个自变量对应一个函数值的情况，比如f(x,y)
double func(int x, ... ) {
//这里是对函数值进行计算
double ans = .......
return ans;
}
//原始值
double x = rand(); //x0取随机值
double f = func(x,...); //通过自变量算出f(x0)的值
while(T > eps) {
//--------------
//这里是每一次退火的操作
//x1可以左右随机移动，幅度和温度T正相关，所以*T
//注意这里移动可以左右移动，但是也可以单向移动
//关于rand()详细见开头注的①
double dx = x+(2*rand() - RAND_MAX) * T;
//让x落在定义域内，如果没在里面，就重新随机。
// ================
while(x > ? || x < ? ...) { //保证x在作用域中
double dx = (2*rand() - RAND_MAX) * T;
}
// ================
//求出f(x1)的值
double df = func(dx);
//这里需要具体问题具体分析，我们要接受更加优秀的情况。可能是df < f(比如求最小值）
if(f < df) {
f = df; x = dx; [...,y = dy;] // 接受，替换值，如果多个自变量，那么都替换
}
//否则概率接受，注意这里df-f也要具体问题具体分析。
//详细见开头注的②③
else if(exp((df - f) / T) * RAND_MAX > rand()) {
f = df; x = dx; [...y = dy;] // 接受，替换值，如果多个自变量，那么都替换
}
//--------------
T = T * dT; //温度每次下降一点点， T * 0.999
}
//最后输出靠近最优的自变量x值，和函数值f(x)
cout << x << " " << f << endl;
我们试图通过退火找出一个值x0，使得x0的平方的值更加接近于n
所以我们的目标函数就可以知道：f(x)=|x0^2-n|;
//n代表我们最后函数要逼近的值
double n;
//x表示我们随机产生的那个数的平方和n的靠近程度
double func(double x) {
return fabs(x * x - n);
}
退火函数SA()
double T = 20000; //初始温度，初始温度主要是看题目开始需要跳转的幅度。
double dT = 0.995; //变化率，这里需要速度稍微慢一点，写0.999 或者 0.997都可以，但是越靠近1速度就越慢
const double eps = 1e-14; //10的-14次方已经非常小了，写这个大概率没问题
void SA() {
//首先随机生成一个点x0，这里我用0代替。
double x = 0;
//算出x平方和n的差距f(x0)
double f = func(x);
while(T > eps) {
//这里x0既可以变小，也可以变大，所以我们正负都要进行一个跳转,算出变换后的点dx
double dx = x + (2 * rand() - RAND_MAX) * T;
//但是请注意，dx很明显要保证 >= 0才行，因为算术平方根的定义域是>=0，因此小于0就重新随机
while(dx < 0)
{
dx = x + (2 * rand() - RAND_MAX) * T;
}
//算出变换后的点dx的平方和n的差距，f(dx)
double df = func(dx);
//这里就是关键的地方了，很明显我们需要算出来的function值越小，自变量x更加接近那个根号值。
//所以如果新来的值df 比 f更小，我们百分百接受
if(df < f) {
//注意更新所有变量
f = df; x = dx;
}
//否则我们概率接受，这里的需要写 f - df了，因为这样才是负值。负值说明我们并不是贪心接受的，他是不太好的值。
else if(exp((f - df)/T) * RAND_MAX > rand()) {
//注意更新所有变量
f = df; x = dx;
}
//温度下降一下
T *= dT;
}
printf("%.8lf",x);
}
题目描述
给出平面上N（N<=100）个点，你需要找到一个这样的点，使得这个点到N个点的距离之和尽可能小。输出这个最小的距离和（四舍五入到最近的整数）。
Input输入
第一行N，接下来N行每行两个整数，表示N个点
Output输出
一行一个正整数，最小的距离和。
Sample Input样例输入
4
0 0
0 10000
10000 10000
10000 0
Sample Output样例输出
28284
将所有的点存放入一个结构体point数组中
const int N = 1e5 + 5;
struct Point {
double x, y;
}e[N];
//main函数中输入N个点
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
scanf("%lf%lf", &e[i].x, &e[i].y);
}
关键的函数
//输入我们随机生成的点A 坐标 x0, y0
double func(double x, double y) {
double ans = 0;
for(int i = 1; i <= n; i++) {
double xx = e[i].x, yy = e[i].y; // xx 就是 xi ，yy 就是 yi
double p = fabs(e[i].x - x); // x0 - xi
double q = fabs(e[i].y - y); // y0 - yi
ans += (sqrt((p * p + q * q))); // ans加上到随机点A到点i的距离
}
return ans;
}
然后套用上面的公式，我们写出SA()模拟退火
double T = 2000; //初始温度
double dT = 0.993; //变化率，这里需要速度稍微慢一点，写0.995 或者 0.997都可以，但是越靠近1速度就越慢
const double eps = 1e-14; //10的-14次方已经非常小了，写这个大概率没问题
void SA() {
//随机生成点A(x0,y0)，这里我直接赋值为了0。当然也可以写rand()，差别都不大。
double x = 0, y = 0;
//生成的点A(x0,y0)对应的函数值f(x0, y0)
double f = func(x, y);
while(T > eps) {
//这里对x和y同时进行一个偏移，很明显在一个平面中，上下左右都可以移动，所以我们选择了rand() * 2 - RAND_MAX
//对于每个点，我们的偏移幅度都要 * T,温度越高，偏移量越大
double dx = x + (rand() * 2 - RAND_MAX) * T;
double dy = y + (rand() * 2 - RAND_MAX) * T;
//算出偏移后的点B(dx, dy)对应的函数值f(dx, dy)
double df = func(dx, dy);
//这里就是关键的地方了，很明显我们需要算出来的function值越小，就更加优秀
//所以如果新来的值df 比 f更小，我们百分百接受
if(df < f) {
//注意更新所有变量
f = df; y = dy; x = dx;
}
//否则我们概率接受，这里的需要写 f - df了，因为这样才是负值
else if(exp((f - df) / T) * RAND_MAX > rand()) {
//注意更新所有变量
f = df; y = dy; x = dx;
}
//降低温度
T = T * dT;
}
//输出答案
printf("%.f\n", f);
}