# 模拟退火算法

> source: 文章/simulated-annealing/index.md

# 模拟退火算法

什么是模拟退火算法？

<!-- more -->

## 简介

模拟退火算法(Simulated Annealing, SA)是一个全局最优化的算法。之前我们使用过梯度下降法，我们很清楚梯度下降法的问题所在，它使用了一种贪心的策略，而正是这种贪心，使得算法在遭遇一个区域中的极值时停了下来，很难寻找全局的最优解

而模拟退火算法则是在梯度下降法的基础之上，引入`模拟退火`的思想，我们通过算法来模拟物理过程，从而来帮助我们寻找**全局最优解**

这里需要注意，模拟退火算法是依赖于概率收敛到全局最优解的

模拟退火算法可用于精确算法失效的高难度计算优化问题，虽然通常只能获得全局最优的近似，但对很多实际问题已经足够，对于大多数实际的数据图像，它们并没有我们想象中的那么光滑、好看，很多都是非常崎岖、充满锯齿的, 在这种情况下, 使用模拟退火算法未尝不是一个好办法

## 算法原理

SA算法依照下面的流程来运行

1. 设定初始温度
2. 对初始值进行采样
3. 退火, 让温度下降
4. 随机采样下一个点
  - 如果随机采样的点比当前的点更好, 更新现在的点
  - 如果随机采样的点比当前的差, 根据温度相关的常数一定概率更新当前的点
5. 重复步骤3-4

使用这种方法, 可以避免困在局部最优解中

<!-- fold -->

<center>
[cooling_rate](../../assets/cooling_rate.png){width="800"}
</center>

但是如果我们总是允许改进以一个确定的概率发生, 那么围绕局部解的中心进行搜索需要很多次计算, 大大降低了效率, 因此我们需要让更新概率(接受率)取决于温度T, 让它的值随着温度T的下降而降低, 这样, 在温度较低的时候, 采样值恶化的概率也会降低, 这就好像现实中温度降低时, 分子的随机运动剧烈程度也会降低

我们可以用下面这个不等式来描述接受操作

$$
U(0, 1) < \exp (- \frac{\Delta E}{T})
$$

$U(0, 1)$是区间0到1上的均匀分布, $\Delta E$ 是当前点和新的采样点的差距, 从上面的方程可以看出, 随着温度 $T$ 的降低, 随机采样的值落小于上面这个结果的机会就更小, 因此上面的方程成立的概率在下降, 因此我们采用这种 [Metropolis](https://en.wikipedia.org/wiki/Monte_Carlo_method) 方法来约束向更坏的点更新的概率

## 源代码

```python title="模拟退火" linenums="1"
import matplotlib.pyplot as plt
import numpy as np

def objective(x):
  return 2 * np.sin(x) + 3 * np.cos(2 * x) + 5 * np.sin(2/3*x)

# 设置步长
n = 10000
data_x = np.linspace(0, 4 * np.pi, n)
data_y = objective(data_x)

# 接受三个参数： 对象， 降温系数， 迭代次数
def simulated_annealing(objective, cooling_rate, n_iter) -> tuple[np.ndarray, np.ndarray]:
  def cool(T, cooling_rate = 0.9):
    return cooling_rate * T
  
  x_iter = np.zeros(n_iter)
  obj_iter = np.zeros(n_iter)
  # 初始化温度
  T = 1.
  # 对初始值进行采样
  index = 7000
  curr_x = data_x[index]
  curr_obj = objective(curr_x)
  
  best_x = curr_x
  best_obj = curr_obj
  
  for i in range(n_iter):
    # 首先让温度下降
    T = cool(T, cooling_rate)
    index = np.random.choice(n, 1) # 这里n表示采样的空间为整段函数， 可以进一步优化
    new_x = data_x[index]
    new_obj = objective(new_x)
    
    # 进行判断，新的点更好或者随机采样的值小于一定概率，则接受新的采样结果
    if (new_obj > curr_obj) or (np.random.rand() < np.exp((new_obj - curr_obj) / T )):
      curr_x = new_x
      curr_obj = new_obj
      
    # 更新最优解
    if new_obj > best_obj:
      best_x = new_x
      best_obj = new_obj
      
    # 保存结果
    x_iter[i] = best_x
    obj_iter[i] = best_obj
    
  return x_iter, obj_iter
    
x_iter, obj_iter = simulated_annealing(objective, 0.9, 1000)

best_index = np.argmax(obj_iter)

print("best x: {}, best objective: {}".format(
    x_iter[best_index], obj_iter[best_index]))

plt.plot(data_x, data_y, label = 'objective')
plt.scatter(x_iter[best_index], obj_iter[best_index], label = 'Simulated annealing', color='red')
plt.xlabel('data_x')
plt.ylabel('data_y')
plt.title('Simulated annealing')
plt.show()
```

运行上面的源代码可以得到下图

<center>
[Simulated annealing](../../assets/Simulated_annealing.png){width="800"}
</center>

可以发现模拟退火正确且较为精准地找到了全局最优解, 当然这只是一个简单的例子, 在遇到真实的情况时, 设置步长, 温度, 接受率等各方面都需要较长时间的优化, 以此来帮助这个算法更高效, 稳定, 准确地工作

## References

- [シミュレーテッド・アニーリング from Scratch](https://qiita.com/meltyyyyy/items/096efb08fb4ec532c330)
