模拟退火（浅谈）

写在前面

放眼历史，喧嚣过后终归无声，热寂才是最终归宿。

算法思想

世界上的万事万物总是比较容易稳定在低能量的状态，当物体温度较高时，内能较大，固体内部粒子处于快速无规则运动，在固体温度慢慢降低的过程中，固体内能减小，粒子慢慢趋于有序。
举个现实生活的小栗子：在冶金工业中，通常会把结构不是很稳定的金属矿石（不处于能量最低）加热到一个较高温度，使它的能量变高内能增大，内部粒子平均运动速率变快。相当于把金属大部分粒子先提升到一个比较高能量的位置，再降温，降温之后把温度恒定，停留足够长的一段时间之后，我们就可以认为金属在这个温度下已经达到平衡状态（可能是最低或局部最低的能量状态），结构在这个温度下稳定。接下来再降低温度，再稳定一段时间不变，一次一次的降温，最终我们期望在降到最低的温度的时候金属处于最稳定的状态。
在微观世界中，有时给电子提供一部分能量，让电子跃迁到能量稍微高一点的能及上去，电子在那个能及上是不稳定的，然后就会一下子跳到能量更低的能级上，这个过程释放大量能量，达到更稳定的状态。就是说它最开始的状态相对稳定（处于局部最优状态），给它能量升高的机会，它才会跃迁到能量更低的层级上去。

作用

通过多次迭代，逼近函数的最值。

几个概念

\(T\)：初始温度（数越大，正解概率越高，但是耗时越长）
\(down\): 温度变化率（越大约不准确，但越快），设置这个系数的目的是让\(T\)能以一个合适的速度减小，使得当\(T\)在到达边界时我们已经尝试了足够多组解来使最终解接近最优解，由于越临近结束越接近最优解，可以加快降温速度，通常使\(T_{i}=T_{i-1}\times down\)。
\(x\)：每次随机选择的解。
\(\triangle x\)：\(x\)的变化量，通常（\(x_i=x_{i-1}+\triangle x\)），随机取值的值域与\(T\)成正比（温度越高分子无规则运动越剧烈）。
\(dE\)：熵变，两次函数值的差值。

实现方式

定一个较高温度\(T\)（加热），进入外层循环（由温度决定，控制温度慢慢下降，结束条件为\(T\)小于指定值）。在内层循环中在一定范围内随机找一个\(x_{i+1}\)（一般情况下 $x_{i+1}=x_i+T\times $一个从\(0\)到\(1\)的随机数 ）。判断\(f(x_{i+1})\)是否优于\(f(x_i)\)，若\(dE\)不小于\(0\)，接受\(x_{i+1}\)，替换\(x\)并与全局最优解对比。若\(dE\)小于\(0\)，有一定概率接受\(x_{i+1}\)，\(dE\)越小接受概率越小，通常用函数\(e^{\frac{dE}{kT}}\)（\(e\)为自然对数，\(k\)为玻尔兹曼常数（近似于\(1.3\)））于一个从\(0\)到\(1\)的随机数比较，若函数值大于随机数则接受\(x_{i+1}\)。循环一定次数（或者连续几次\(dE\)接近\(0\)，内能变化小，体系接近稳定）后退出内层循环。继续降温......

随便抓一只伪代码

int T = 114514;
int tempx, tempy, tempans, de;
//下面的x, y, ans为临时最优解
while( T > 1e-15 ){  //T十分接近零
	tempx = x + (rand() * 2 - RAND_MAX) * T;
	tempy = y + (rand() * 2 - RAND_MAX) * T;
	//rand() * 2 - RAND_MA可以生成从 -32767 到 32767 的随机数，以让坐标点转移到一个随机位置，随着不断降温，T会越来越小，所以坐标点转移的范围也会越来越小，逐渐逼近最优点
	tempans = solve( tempx, tempy )
	//solve是用来求内能
	de = tempans - ans;
	if( de < 0 ){//是大于还是小于具体问题判断   
		x = tempx;
		y = tempy;
		w = tempw;
	} else if( exp( -de / T ) * RAND_MAX > rand() ){//以一个概率选择是否接受，但是就算是接受，我们也不会用它来更新最优解，因为我们当前的最优解比它优秀。传如esp函数中的值需为负	
		x = tempx;
		y = tempy;	
	}
	T *= down;//降温
}

写在后面

生命以负熵为食，建立宇宙微秩序。