信念，是会化不可能为可能的。——《笨蛋，测验，召唤兽》

模拟退火

模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。它是基于 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

算法从某一较高温度初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如 、生产调度、控制工程、机器学习、神经网络、信号处理等领域（为什么百度百科里这块东西记录的这么全啊）

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

我是某函数！（好吧其实我也不知道它是啥）

要学习模拟退火，先要了解金属退火。

退火是一种金属热处理工艺，指的是将金属缓慢加热到一定温度，保持足够时间，然后以适宜速度冷却（目的这边不是很重要，想了解的左转百度百科，右转 欢迎你，（如果你只是来问怎么打过机械公敌（英雄联盟的一个英雄）的，我无能为力）。

每次随机出了一个新解，如果这个解更优，则接受它，否则以一个与温度和最优解的差相关的概率接受它。

设这个新的解与最优解的差为 ，温度为 ， 为一个随机数，那么这个概率为 。

模拟退火的食用

降温

模拟退火时会用到三个参数，分别是初始温度 、降温系数 和终止温度 。

其中， 是一个比较大的数， 是一个略小于 的正数， 是一个略大于 的正数。

我们先让温度 ，然后每次降温时 ，直到 为止。

来偷偷放一张老生常谈的 ：

我是模拟退火的过程

可以看出，随着温度的降低，解逐渐稳定下来，并逐渐集中在最优解附近。

玄学

在程序开始之前，要先取随机参数。即：

1
srand ();

可以使用的是随机时间参数，可以使用各种奇怪的质数，一遍 往往无法跑出最优解，所以可以多跑几遍，可以用一个全局变量记录所有 的最优解，每次从那个最优解开始，可以减小误差。

至于时间复杂度，应该是这个数：

就很玄学。

一般降温系数 与 の差减少一个数量级，耗时大约多 倍； 和 变化一个数量级，耗时不会变化很大。

调参

这里讲的不是：

如何穿着潜水服去深海里捕捉昂贵的用于调养身体的充满营养的海参

也不是：

如何在紧张激烈的骑士大赛前调整状态做好参加一场殊死搏斗的准备

而是：

如何在非常玄学的模拟退火算法中合理科学地使用各种方法调整参数

至于上面那个你要不去问问斯卡蒂（是明日方舟的一位干员，而且最近快要出浊心·斯卡蒂了诶，好耶！）。

谁还不是一条坐吃等死的咸鱼呢

至于中间那个你要不去问问玛利亚·瑕光（是明日方舟的一位干员），她对这个应该挺懂的（反正我不懂）。

不畏苦难！

这里是 的一条插播喜报：刚在插头 那里吐槽了 教授，然后回来看到这个突然想到当时明日方舟二周年周年庆的那个池子， 教授当时抽了 多发，就是娶不到浊心斯卡蒂，结果那天回初中学校的时候他在办公室里玩的时候碰到六星了！

然后抽出了个瑕光哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，还被初二的小朋友（我爸的学生）听到了我们说的：“不会*（我）也玩明日方舟吧”，最后 教授强娶了。

至于下面这个现在……算了还是我来继续一本正经的胡说八道吧。

答案如果不是最优的，可以调大 、调整 和 ，以及多跑几遍 ，特别是程序跑得像萨卡兹穿刺手（是明日方舟的一位敌人）一样快的时候，而 和 的值需要根据值域对应调整，从而保证每次随机出的变化幅度不会太大。

生成新解

1、在坐标系中，随机生成一个点，或生成一个向量。

2、序列问题中， 或者随机交换两个数。

3、网格问题中，看做一个二维序列，每次交换两个鸽子。

模拟退火的应用

先从一道烫得不彳亍的例题开始：

平衡点

有 个重物挂在足够长的绳子上，每条绳子都穿过桌子的一个洞，然后系在一起，在理想状态下，问绳结最终平衡于何处？

官方图好丑

那很简单了，随机出一个坐标，然后去算能量总和，总和越小越稳定。

完整代码如下（建议多交几次，很看欧气，我交了三页提交记录）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3 + 1;
const double Delta = 0.998;
const double eps = 1e-18;

struct Node {
	double x, y, w;
} e[N];

int n;
double ansx, ansy;

double f (double x, double y) // 计算能量总和 
{
	double tot = 0;
	for (int i = 1; i <= n; i ++)
	{
		double delx = x - e[i].x;
		double dely = y - e[i].y;
		tot += sqrt (delx * delx + dely * dely) * e[i].w;
	}
	return tot;
}

void SA ()
{
	double T = 5300;
	while (T > eps) // 在零度前结束  
	{
		double nowx = ansx + (rand () * 2 - RAND_MAX) * T;
		double nowy = ansy + (rand () * 2 - RAND_MAX) * T;
		double delta = f (nowx, nowy) - f (ansx, ansy);
		if (delta < 0) // 如果更优就接受  
		{
			ansx = nowx;
			ansy = nowy;
		}
		else if (exp (-delta / T) * RAND_MAX > rand ()) // 以概率接受  
		{
			ansx = nowx;
			ansy = nowy;
		}
		T *= Delta; // 模拟徐徐降温  
	}
}
int main ()
{
	srand ((int) time (NULL)); // 阿弥陀佛  
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%lf %lf %lf", &e[i].x, &e[i].y, &e[i].w);
		ansx += e[i].x;
		ansy += e[i].y;
	}
	ansx /= (double)n; // 从平均值开始 
	ansy /= (double)n;
	SA ();
	printf ("%.3lf %.3lf\n", ansx, ansy);
	return 0;
}

至于分块模拟退火，对于一些峰比较多的数据，先把一整段区间分为一坨一坨，然后每个都跑一遍模拟退火，再取最优解。

然后可以用以下方法来在不会 飞~的情况下多跑几次 ：

1
2
while ((double)clock () / CLOCKS_PER_SEC < MAX_TIME) 
	SA();

用 来返回程序运行时间， 就可以取个 到 之间的数。

当然还有一些 的问题，这个之后再讲吧。