模拟退火算法：原理与Python实现

模拟退火算法（Simulated Annealing，SA）是一种用于全局优化问题的随机算法，尤其适用于大规模、复杂的组合优化问题。该算法受启发于物理冶金学中的退火过程，通过缓慢降低系统温度来寻找最优解。在优化过程中，模拟退火允许以一定概率接受比当前解更差的解，从而避免陷入局部最优解。

一、模拟退火算法原理

1. 退火过程

在物理学中，退火是指加热金属或玻璃材料到高温，使其分子能够自由移动，然后通过缓慢降低温度，使其达到一个较低能量的稳定状态。模拟退火算法通过模拟这一过程，在高温下允许系统在解空间内大幅度地随机跳跃（甚至接受较差的解），而在低温时趋于收敛，找到接近全局最优解。

2. 算法流程

模拟退火算法的核心步骤包括：

初始解与初始温度：从一个随机解开始，温度设为一个较高的初值。
邻域搜索：在当前解的邻域中生成一个新的解。
接受准则：
- 若新解优于当前解，则接受新解；
- 若新解不如当前解，则以一定的概率接受该解。这个概率与温度和解的质量差有关，通常使用Metropolis准则：
  [
  P(\text{接受新解}) = \exp \left( \frac{f_{\text{new}} - f_{\text{current}}}{T} \right)
  ]
  其中 ( T ) 是当前温度，( f_{\text{new}} ) 和 ( f_{\text{current}} ) 分别是新解和当前解的目标函数值。
降温：逐步降低温度，一般使用指数降温方式 ( T_{k+1} = \alpha T_k )，其中 ( 0 < \alpha < 1 )。
终止条件：当温度降到一定阈值或者达到设定的迭代次数时，停止搜索。

3. 关键要素

温度控制：温度的下降速度直接影响算法的收敛性。过快的降温可能导致算法早早陷入局部最优，而过慢的降温则会增加算法的运行时间。
接受概率：在较高温度下，算法允许较大范围的随机搜索，而在低温时则趋向于搜索更优解。

二、模拟退火算法Python实现

我们通过一个简单的实例来展示如何在Python中实现模拟退火算法。假设我们要优化一个二维函数，例如著名的 Rastrigin 函数：

[
f(x, y) = 20 + x^2 + y^2 - 10 (\cos(2 \pi x) + \cos(2 \pi y))
]

Rastrigin函数具有多个局部最优点，是测试全局优化算法的经典例子。

1. 模拟退火算法代码

import numpy as np
import matplotlib.pyplot as plt# 定义Rastrigin函数
def rastrigin(x, y):return 20 + x**2 + y**2 - 10 * (np.cos(2 * np.pi * x) + np.cos(2 * np.pi * y))# 退火算法参数设置
T_init = 1000  # 初始温度
T_min = 1e-6   # 最低温度
alpha = 0.9    # 降温系数
max_iter = 1000  # 每个温度下的最大迭代次数# 邻域内随机产生新解
def neighbor(x, y):x_new = x + np.random.uniform(-1, 1)y_new = y + np.random.uniform(-1, 1)return x_new, y_new# 模拟退火算法
def simulated_annealing():# 随机生成初始解x_current = np.random.uniform(-5, 5)y_current = np.random.uniform(-5, 5)f_current = rastrigin(x_current, y_current)x_best, y_best = x_current, y_currentf_best = f_currentT = T_init  # 初始温度while T > T_min:for _ in range(max_iter):# 产生邻域内的新解x_new, y_new = neighbor(x_current, y_current)f_new = rastrigin(x_new, y_new)# 判断是否接受新解if f_new < f_current:x_current, y_current = x_new, y_newf_current = f_new# 更新全局最优解if f_new < f_best:x_best, y_best = x_new, y_newf_best = f_newelse:# 根据接受概率决定是否接受差的解delta_f = f_new - f_currentaccept_prob = np.exp(-delta_f / T)if np.random.rand() < accept_prob:x_current, y_current = x_new, y_newf_current = f_new# 降温T *= alphareturn x_best, y_best, f_best# 运行模拟退火算法
x_opt, y_opt, f_opt = simulated_annealing()print(f"最优解: x = {x_opt}, y = {y_opt}, 最优函数值: f(x, y) = {f_opt}")# 可视化Rastrigin函数与最优点
x = np.linspace(-5, 5, 400)
y = np.linspace(-5, 5, 400)
X, Y = np.meshgrid(x, y)
Z = rastrigin(X, Y)plt.figure(figsize=(8, 6))
plt.contourf(X, Y, Z, levels=50, cmap='viridis')
plt.colorbar()# 标记最优解
plt.plot(x_opt, y_opt, 'ro', label='Optimal Point')
plt.legend()
plt.title("Simulated Annealing on Rastrigin Function")
plt.xlabel('x')
plt.ylabel('y')
plt.show()