模拟退火

模拟退火是模拟物理实验中对于材料温度的把控,每次下降多少,直到温度下降到底端的时候,材料的物理性质趋于稳定,每次活动的空间也越来越小,这个时候我们一般认为收敛的位置是极小值

个人认为比较困难的点是如何”渐进地”生成新的逼近的随机答案,否则模拟退火就是单纯的随机数碰答案.

二元函数求最值

三分xy的情况

我们以吊打xxx为例.加入x值定死,势能变化随y是一个单峰函数.

也就是说,我们可以三分y从而达到理想效果.

考虑一个单峰,假如落在三分中间,那么怎么收缩都是涵盖的.
假如没有,我们三分的两个点会是一个明显递增或者递减的趋势,此时收紧,也就是说一次收缩大概1/3,剩下的2/3接着三分即可.

Flu的常用参数

//	起始温度	最终温度	每次下降多少
double t=5000,EPS=1e-10,down=0.9112;
	round=200;	//进行多少轮退火
double t=3000,EPS=1e-10,down=0.996;
	round=1000;	//进行多少轮退火

模拟退火怎么用?

我们要模拟温度减小的过程,所以尝试在题中找到一些”会变小的量”,然后慢慢退火.

1. 洛谷p1337
   最裸的模拟,让坐标变化随着温度减小慢慢减小,直到最后动不了统计答案.
   多退几次火,因为一次退火可能收敛到极小值,但不是最小值.

2. 洛谷p3878
   每次退火前先shuffle一下原序列,确保和之前的退火没多大关系.
   然后每次从两个集合中选一个数交换,如果小就保留,如果变大或不变则有多少的概率保留.(套板子)