机器学习：优化算法（五）—— 模拟退火算法

算法背景

模拟退火算法最早的思想由Metropolis（1953）提出，1983年Kirkpatrick等将其应用于组合优化，有以下优点：

1. 解决NP问题
2. 克服局部最优
3. 克服初值依赖性

物理退火

物理退火过程

退火：将固体加热到足够高的温度，使分子呈现随机排列状态，然后缓慢降温，使得分子在每一温度时，能够有足够时间找到稳定状态，最后分子以近似最低能量状态排列，达到某种稳定状态。但如果快速降温（淬火，quenching）会导致不是最低能态的非晶体.

1. 升温过程：增强粒子动能，消除系统可能的非均匀态
2. 等温过程：对于与环境换热而温度不变的封闭系统，系统自发朝着自由能降低的方向变化，当自由能达到最低时，系统达到平衡态
3. 冷却过程：粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构

Boltzman概率分布

在温度T，分子停留在状态r满足Boltzman概率分布，其中$Z(T)$为概率分布的标准化因子：

$$P(E_r) = \frac{1}{Z(T)}e^{-\frac{E_r}{KT}}$$

选定两个状态，分子处于这两个状态的概率差可表示为：

$$P(E_1) - P(E_2) = \frac{1}{Z(T)}e^{-\frac{E_1}{KT}}[1-e^{-\frac{E_2-E_1}{KT}}]$$

1. 同一温度下，能量越小的状态分子处于该状态的概率越大，即分子总是趋向于低能状态；
2. 温度越高，不同能量状态的概率差异性越小，即分子处于各能量状态的随机性越强；
3. 随着温度下降，分子处于低能状态的概率越来越大，当温度趋于0时，分子停留在最低能量状态的概率趋于1；

模拟热平衡——依概率接受新状态

Metropolis准则用于模拟固体在恒温下达到热平衡的过程:

1. 在温度T，当前能量状态i→状态j
2. 若$E_j < E_i$，则直接接收j为新的状态
3. 若$E_j >= E_i$，以$p = e^{-\frac{(E_j - E_i)}{KT}}$的概率接受j为当前状态，以$1-p$的概率保持原始状态

模拟退火

组合优化与物理退货的相似性：

组合优化	物理退货
可行解	金属状态
最优解	能量最低的状态
目标函数	能量
设定初始温度	升温过程
Metropolis抽样	等温过程
参数下降	冷却过程

问题定义

对于最优化问题：

$$\underset{\boldsymbol{ \theta }}{arg}max f(\boldsymbol{ \theta })$$

问题求解

代码实现

关键参数

改进

应用