SAA

模拟退火算法

命名：

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

原理：

如上图所示，从A点开始下降，寻找最低点，若经过B点，由于B点的梯度为0，故在此点可能误将极值点作为最指点，退火算法正是为了解决这一问题。
算法中规定了有限次的循环上限，在每一次循环中，更新当前点的位置并获得下一次点的坐标,新旧两点坐标将满足以下一种关系：

1. 若下一点的函数值$E_{new}<E_{old}$，即dE<0，则当前点比不是最值点，则更新点的几率 P=1.
2. 若$E_{new}>E_{old}$，即dE>0，则可能当前点位于B点或C点，此时以一定几率P继续更新。

即P满足：

注意设定初始温度T在一较高值，设定结束温度，并且每次不要忘记更应温度t=t*r，r为降低率。
由该式可看出，随着T增大，P越来越小，最终达到平衡，也符合自然规律。
下贴上伪代码：