模拟退火算法 - 浅层

模拟退火算法(Simulated Annealing，SA) - 属于启发式搜索

什么是启发式搜索 ？ 

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的。又或者说，在搜索最优解的过程中利用到了原来搜索过程中得到的信息，且这个信息会改进我们的搜索过程。

模拟退火算法

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

//前期我们希望搜索范围大一些，后期希望搜索范围小一些，这么做有利于找到全局最优解，而非陷入局部最优解。

基本流程(以最小值为例)

 

假设求最大值问题

(1)随机生成一个解A，计算解A对于的目标函数值F(A)。

(2)在A附近随机生成一个解B，计算解B对于的目标函数值F(B)。

(3)如果F(B)>F(A)，则将解B赋值给解A，然后重复上面步骤。<爬山法思想>

    如果F(B)<= F(A)，那么我们计算接收B的概率p，然后生成一个[0,1]之间的随机数r，如果r<p，将解B赋值给解A，然后重复上述步骤；否则返回(2)，在原来的A附近再重新生成一个解B，然后继续。

得到全局最优的条件

(1)初始温度足够高

(2)迭代次数足够大

(3)终止温度足够低

(4)降温过程足够缓慢

什么时候停止搜索？

(1)达到指定的迭代次数。

(2)达到指定的温度。

(3)找到最优解连续M次迭代都没有变化。

模拟退火算法的优缺点

优点 - 能够处理具有任意程度的非线性、不连续性、随机性的目标函数，目标函数可以具有任意边界条件和约束。

        - 比起其他的非线性优化算法，模拟退火的编程工作量小，且易于实现，统计上可以保证找到全局最优解。

缺点 - 找到最优解要耗费非常多的时间。

        - 参数调整到最适合比较困难。

        - 使用不当(如降温过快等)会找到误差很大的结果。