「学习笔记」模拟退火

Posted on Edited on

引用：浅谈$SA-M$_$sea$

$SA$学习笔记-$99NL$

退火流程：

$1.$由上一次接受的解$pre$出发，随机得到一个可能解$x$。

$2.$若当前解优于最优解$ans$，覆盖最优解。

$3.$否则$x$将会以$exp(delta/T)$的概率成为下一次的$pre$。

$4.T*\Delta$降温。

$\Theta(???)$

“一般降温系数 $\Delta$ 与 $1$ 的差减少一个数量级, 耗时大约多 $10$ 倍；$T_0$和$T_k$变化一个数量级, 耗时不会变化很大。”

$by\;M$_$sea$

实现细节

$1.$降温系数取$[0.95,0.997]$左右。

$2.$如何生成新解？

坐标系内：随机生成一个点，或者生成一个向量。

序列问题：$random\;shuffle$ 或者随机交换两个数。

网格问题：可以看做二维序列，每次交换两个格子即可。

$by\;M$_$sea$

$3.$如果想多跑几次….

1
2
MAX_TIME = 0.7~0.8
while ((double)clock()/CLOCKS_PER_SEC<MAX_TIME) SA();

实测$P1337[JSOI2004]$平衡点 / 吊打$XXX$评测记录 $0.6->TLE$

$4.WA?$

不同的$\Delta$、$T_0$、$T_k$甚至$srand()$和$SA$的次数都会影响到答案。

$by\;M$_$sea$

$About:srand()$

你可以这样写：

$srand((unsigned)time(NULL))/srand(19260817)$

再$srand(rand())$几次。

例题

$P1337[JSOI2004]$平衡点 / 吊打$XXX$

$1.$势能的计算：$len*w$（$len:$绳在桌面上的长度）

原理：绳子总长不变，$len$越大，物体越高。

$2.$横纵坐标的增量：$((rand() << 1) - RAND$_$MAX) * T$

$((rand() << 1) - RAND$$MAX)$得到介于$[-RAND$ $MAX,RAND$ _ $MAX-1]$之间的随机数。

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
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>

const double eps = 1e-14, del = 0.992;
const int MAXN = 1010;
int N;
double ansx, ansy, ans = 1e18;
int x[MAXN], y[MAXN], w[MAXN];

double calcEp(double nx, double ny)
{
	double ret = 0;
	for (int i = 1; i <= N; i++)
	{
		double dx = nx - x[i], dy = ny - y[i];
		ret += sqrt(dx * dx + dy * dy) * (double)w[i];
	}
	return ret;
}

void SA()
{
	double T = 1926, tx = ansx, ty = ansy;
	while (T > eps)
	{
		double nx = tx + ((rand() << 1) - RAND_MAX) * T;
		double ny = ty + ((rand() << 1) - RAND_MAX) * T;
		double c = calcEp(nx, ny); double d = c - ans;
		if (d < eps) {ansx = nx, ansy = ny; ans = c; tx = nx, ty = ny;}
		else if (exp(-d / T) * RAND_MAX > rand()){tx = nx, ty = ny;}
		T *= del;
	}
}

void calc()
{
	for (int i = 1; i <= N; i++) ansx += x[i], ansy += y[i];
	ansx /= N, ansy /= N;
	SA(); SA(); SA(); SA(); 
}

int main()
{
	srand(19260817); srand(rand());
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d%d%d", &x[i], &y[i], &w[i]);
	calc();
	printf("%.3lf %.3lf\n", ansx, ansy);
	return 0;
}