简介

模拟退火算法的思想借鉴于固体的退火过程，当固体的温度很高时，内能比较大，固体内的粒子处于快速无序运动状态，当温度慢慢降低，固体的内能减小，粒子逐渐趋于有序，最终固体处于常温状态，内能达到最小，此时粒子最为稳定。

白话理解：一开始为算法设定一个较高的值T（模拟温度），算法不稳定，选择当前较差解的概率很大；随着T的减小，算法趋于稳定，选择较差解的概率减小，最后，T降至终止迭代的条件，得到近似最优解。

算法步骤

1.模拟退火的基本思想:

(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L

(2) 对k=1, …, L做第(3)至第6步：

(3) 产生新解S′

(4) 计算增量ΔT=C(S′)-C(S)，其中C(S)为目标函数,C(S)相当于能量

(5) 若ΔT<0则接受S′作为新的当前解，否则以概率exp(-ΔT/T)接受S′作为新的当前解.

(6) 如果满足终止条件则输出当前解作为最优解，结束程序。

(7) T逐渐减少，且T->0，然后转第2步。
2.模拟退火算法新解的产生和接受可分为如下四个步骤：

第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若ΔT<0则接受S′作为新的当前解S，否则以概率P接受S′作为新的当前解S。

第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
详解博客链接

特点

与爬山法相比，模拟退火通过函数将解进行比较，存在一定概率将小解储存。
退火算法搜索前期概率大，容易接受新解，后期概率小不容易接受新解。
模拟退火算法属于启发式算法的一种，可以大幅减少计算时间。