学习笔记--模拟退火

**模拟退火（Simulated Annealing）**是一种随机搜索算法，用于求解优化问题，特别是组合优化问题。它的名字和灵感来源于物理学中的退火过程，即将物质加热到高温，然后逐渐冷却，以达到低能量状态。

模拟退火算法的工作原理如下：

  1. 初始化：选择一个初始解和一个较高的初始“温度”。

  2. 迭代搜索：在每次迭代中，根据一定规则生成一个新的解。

  3. 接受准则：比较新解和当前解的优劣。如果新解更优，那么通常会接受它。如果新解较差，根据一个概率准则（通常基于Metropolis准则）决定是否接受。这个概率与当前的“温度”和解的优劣差有关。

  4. 降温：随着迭代的进行，逐渐降低“温度”，这导致接受较差解的概率下降。

  5. 终止：当“温度”降到一个设定的阈值以下，或者达到预定的迭代次数时，算法终止。

模拟退火算法的关键在于它允许在搜索过程中暂时接受较差的解，这有助于跳出局部最优，从而有可能找到全局最优解。同时，通过逐渐降低“温度”，算法逐渐聚焦于搜索空间中的高质量区域。

###在模拟退火中，Metropolis准则如下：

  • 如果新生成的解比当前解更好（即，目标函数值更低），那么总是接受这个新解。

  • 如果新生成的解比当前解更差，那么以一定的概率接受这个新解。这个概率是基于目标函数值的差异和当前的“温度”计算的，具体为 exp(-(新解的目标函数值 - 当前解的目标函数值) / 当前温度)。

接受更差的解的能力是模拟退火算法的一个关键特性，它允许算法有可能跳出局部最优解，并在搜索空间中更广泛地搜索。然而，随着“温度”的降低，接受更差解的概率也逐渐降低，使算法更加倾向于在潜在的最优区域内进行搜索。

还是那个例题。
假设我们要优化函数 f(x) = x^2，在范围 [-10, 10] 内找到使得函数取得最小值的 x。

import math
import random

# 目标函数
def f(x):
    return x**2

# 模拟退火算法
def simulated_annealing():
    # 参数设置
    x = random.uniform(-10, 10)  # 初始解
    T = 1000  # 初始温度
    T_min = 0.01  # 最小温度
    alpha = 0.95  # 降温系数
    
    # 主循环
    while T > T_min:
        # 生成新的解
        x_new = x + random.uniform(-1, 1)
        
        # 确保新解在 [-10, 10] 范围内
        x_new = max(-10, min(10, x_new))
        
        # 计算目标函数值的差
        delta_f = f(x_new) - f(x)
        
        # Metropolis 准则
        if delta_f < 0 or random.random() < math.exp(-delta_f / T):
            x = x_new
        
        # 降温
        T = T * alpha

    # 返回找到的解
    return x

# 执行模拟退火算法
result = simulated_annealing()
print(f"找到的解: x = {result}, f(x) = {f(result)}")

多跑几次我们会发现，使用模拟退火算法求出的解可能在不同的运行中是变化的。这是因为模拟退火是一种随机算法，它包含随机性在内。算法的随机成分包括初始解的选择、新解的生成以及根据Metropolis准则以一定的概率接受较差的解。

由于这些随机因素，每次运行模拟退火算法时，搜索路径和找到的解可能是不同的。这也是模拟退火算法的一个优点，因为它能够通过多次运行来探索解空间的不同区域。

为了提高找到好解的概率，可以采取以下措施：

  1. 多次运行：多次运行算法并记录每次运行的结果。从这些结果中选择最好的解。

  2. 参数调整：调整模拟退火算法的参数，如初始温度、降温率等，以找到适合问题的设置。

  3. 更好的邻域搜索策略：优化生成新解的方法，可能更加有效地搜索解空间。

请注意，由于模拟退火是一种近似算法，它不能保证找到全局最优解，但通常可以找到一个相当不错的解。另外，这个例子是为了学习算法的工作原理，模拟退火对这种简单问题可能是不必要的。在实际应用中，模拟退火通常用于解决更复杂的优化问题。