模拟退火算法

大概是实习阶段学习的，现在补发一下吧8

模拟退火原理

模拟退火原理博客园

温度（T）：控制搜索的随机性。
能量（E）：评估解的质量。

重点：Metropolis准则

算法随机执行，额外搜索候选解的领域，以一定概率接受比当前解更差的解，避免陷入局部最优。

对于新解和当前解：

重点：温度冷却

1. 指数冷却（几何退火）：

   • 公式：
   • 冷却系数，一般
   • 优点：实现简单，参数少，收敛速度可控。
   • 缺点：降温过快可能导致提前收敛，需调参。

2. 线性冷却：

   • 公式：
   • 优点：直观易理解。
   • 缺点：若 选取不当可能变为负数或降温太慢/太快。

3. 对数冷却（理论保证）：

   • 公式：
   • 优点：在理论上可保证全局收敛（需无限时间）。
   • 缺点：降温极慢，实际问题中不常单独使用。

4. Cauchy 冷却：

   • 公式：
   • 性能介于指数与对数之间，折中选择。

模拟退火例子

求解有两个自变量函数的最小值

模拟退火算法来求解函数的最小值
函数:

import os

import matplotlib

matplotlib.use('TkAgg')  # 设置后端为 TkAgg
import numpy as np
import matplotlib.pyplot as plt

plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

"""
目标函数：Rastrigin函数的最小值
"""


def objective_function(x: list):
    A = 10
    n = len(x)
    return A * n + sum([xi ** 2 - A * np.cos(2 * np.pi * xi) for xi in x])


def simulated_annealing(initial_state: list, objective_function,
                        initial_temperature: float = 100, cool_rate: float = 0.95,
                        num_iterations: float = 1000, perturbation_scale: float = 0.1):
    """
    模拟退火函数
    :param initial_state:初始状态
    :param objective_function:目标函数
    :param initial_temperature:初始温度
    :param cool_rate:冷却系数
    :param num_iterations:迭代次数
    :param perturbation_scale:扰动大小
    :return:结果
    """
    current_state = initial_state.copy()  # 当前状态
    best_state = initial_state.copy()  # 最优状态
    current_energy = objective_function(current_state)  # 当前能量
    best_energy = current_energy  # 最好能量

    energies = [current_energy]  # 观察所有能量状况
    temperatures = [initial_temperature]  # 观察温度状况
    states = [current_state.copy()]  # 观察状态状况
    best_states = []  # 最优解
    temperature = initial_temperature  # 当前温度

    for iteration in range(num_iterations):  # 迭代
        neighbor = current_state + np.random.normal(0, perturbation_scale, len(current_state))  # 正态分布生成一个新的邻居状态
        neighbor_energy = objective_function(neighbor)  # 邻居状态的能量
        delta_energy = neighbor_energy - current_energy  # 能量变化量
        if delta_energy < 0 or np.random.rand() < np.exp(-delta_energy / temperature):  # 更好的状态，或者以一定概率接受比当前解更差的解
            current_state = neighbor  # 选取邻居为当前状态
            current_energy = neighbor_energy

            if current_energy < best_energy:
                best_state = current_state.copy()
                best_energy = current_energy
        temperature *= cool_rate  # 冷却
        energies.append(current_energy)
        temperatures.append(temperature)
        states.append(current_state.copy())

        best_states.append(best_state.copy())
        # 每100次迭代记录全局最优解
        if (iteration + 1) % 100 == 0:
            print(f"Iteration {iteration + 1}/{num_iterations}, "
                  f"Current Energy: {current_energy:.4f}, "
                  f"Best Energy: {best_energy:.4f}, "
                  f"Temperature: {temperature:.4f}")

    return {
        'best_state': best_state,
        'best_energy': best_energy,
        'energies': np.array(energies),
        'temperatures': np.array(temperatures),
        'states': np.array(states),
        'best_states_every_10': np.array(best_states)  # 新增返回值
    }


seed = int.from_bytes(os.urandom(4), byteorder='big', signed=False)  # 随机种子
print("种子", seed)
np.random.seed(seed)
initial_state = np.random.uniform(-5.12, 5.12, 2)  # 随机取一个点坐标作为起始点
print("initial_state", initial_state)
result = simulated_annealing(
    initial_state,
    objective_function,
    initial_temperature=100,
    cool_rate=0.99,
    num_iterations=2000,
    perturbation_scale=0.5
)

best_state = result['best_state']
print("最终结果", best_state, "误差", np.sqrt(best_state[0] ** 2 + best_state[1] ** 2))

best_states = result['best_states_every_10']
x_opt = best_states[:, 0]
y_opt = best_states[:, 1]

# 绘制函数图像
x = np.linspace(-5.12, 5.12, 200)
y = np.linspace(-5.12, 5.12, 200)
X, Y = np.meshgrid(x, y)
Z = objective_function([X.ravel(), Y.ravel()]).reshape(X.shape)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(18, 6))

# 第一个子图：等高线 + 轨迹
contour = ax1.contourf(X, Y, Z, levels=20, cmap='coolwarm')
fig.colorbar(contour, ax=ax1, label='目标函数值')
ax1.set_title(f'Rastrigin函数等高线图，种子={seed}')
ax1.set_xlabel('x1')
ax1.set_ylabel('x2')

# 绘制轨迹与点
ax1.scatter(result['best_state'][0], result['best_state'][1], c='green', s=100,
            label='最终最优解', edgecolors='black', zorder=3)
ax1.scatter(initial_state[0], initial_state[1], c='yellow', s=100,
            label='初始点', edgecolors='black', zorder=3)
ax1.plot(x_opt, y_opt, 'r-o', linewidth=2, markersize=4, label='优化路径', zorder=2)
for i, (xi, yi) in enumerate(best_states):
    ax1.text(xi + 0.5, yi, f'{i + 1}', color='purple', fontsize=10,
             ha='center', va='center', bbox=dict(facecolor='white', alpha=0.7), zorder=1)

# 关键：设置纵横比为 1:1，并确保 x/y 范围一致
ax1.set_aspect('equal', adjustable='box')
ax1.set_xlim(-5.12, 5.12)
ax1.set_ylim(-5.12, 5.12)

ax1.legend()
ax1.grid(True)

# 第二个子图：能量曲线（不需要等比例）
ax2.plot(result['energies'], label='能量变化', color='blue', linewidth=1)
ax2.set_title('能量变化')
ax2.set_xlabel('迭代次数')
ax2.set_ylabel('能量值')
ax2.legend()
ax2.grid(True)

plt.tight_layout()
plt.show()

结果如下：