基础定义

Simulate Anneal Arithmetic (SAA, 模拟退火算法)

退火算法

根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时 的内能，ΔE为其改变量,k为Boltzmann常数。用固体退火模拟 组合优化问题，将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的 模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

起源

模拟退火算法起源于物理退火。

物理退火过程：

⑴ 加温过程

⑵ 等温过程

⑶ 冷却过程

模型建立

模拟退火算法可以分解为解空间、目标函数和初始解三部分。

模拟退火的基本思想：

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

⑵ 对k=1,……,L做第⑶至第6步：

⑶ 产生新解S′

⑷ 计算增量Δt′=C(S′）-C(S)，其中C(S)为评价函数

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

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