模拟退火算法浅尝

简介

其是模拟物理退火过程而演升出的算法，物理退火过程包含加温过程，等温过程，冷却过程。

模拟退火(SA)

初始设定为高温状态，看作是在解空间进行广域搜，处于低温状态时，看作是在解空间中作局部领域搜索，当处于接近零时，得到解空间的全局最优解。其通过Metropolis准则来接受新状态，其描述为：在温度t下，粒子当前状态为i,其能量为$E_i$，当通过扰动方式使粒子状态变为j，其能量为$E_j$，如果$E_i<E_j$,则接受新状态，否则以一定的概率接受状态j，其概率为$p_{ij}={\exp }^{\frac{-(E_j-E_i)}{kt}}$,其中k为玻尔兹曼常量，$p_{ij}$是介于0和1之前的随机数rand，如果$p_{ij}>rand$，则状态j替换掉i状态成为当前状态，否则粒子状态仍为i.