模拟退火算法

模板:算法导航

模拟退火（Simulated Annealing, SA）是一种受金属退火工艺启发的随机化算法，用于解决组合优化问题。它通过模拟物理退火过程中的温度下降和能量最小化，逐步逼近全局最优解，尤其适用于NP难问题或存在多个局部最优解的复杂场景。

核心原理[编辑 | 编辑源代码]

模拟退火的核心思想源于热力学中的退火过程： 1. 高温阶段：系统处于高能量状态，允许原子大幅移动（对应算法中的“随机跳跃”）。 2. 降温阶段：温度逐渐降低，原子趋于稳定（对应算法收敛到最优解）。

算法通过以下参数控制搜索过程：

温度（T）：控制接受劣解的概率，初始温度高，逐渐降低。
冷却率（α）：温度下降速度（如 $T_{n e w} = α \times T_{c u r r e n t}$ ）。
能量函数（E）：即目标函数，需最小化的值。

数学表达[编辑 | 编辑源代码]

接受新解的概率由Metropolis准则决定： $P = {\begin{cases} 1 & 若 E_{n e w} < E_{c u r r e n t}, \\ e^{- \frac{E_{n e w} - E_{c u r r e n t}}{T}} & 否则 . \end{cases}$

算法步骤[编辑 | 编辑源代码]

以下是伪代码实现：

  
def simulated_annealing(initial_solution, initial_temp, cooling_rate, max_iterations):  
    current_solution = initial_solution  
    current_energy = calculate_energy(current_solution)  
    best_solution = current_solution  
    best_energy = current_energy  
    temp = initial_temp  

    for i in range(max_iterations):  
        new_solution = generate_neighbor(current_solution)  
        new_energy = calculate_energy(new_solution)  

        if new_energy < current_energy or random() < exp((current_energy - new_energy) / temp):  
            current_solution = new_solution  
            current_energy = new_energy  

        if new_energy < best_energy:  
            best_solution = new_solution  
            best_energy = new_energy  

        temp *= cooling_rate  

    return best_solution

示例：旅行商问题（TSP）[编辑 | 编辑源代码]

输入与输出[编辑 | 编辑源代码]

输入：城市坐标列表（如 [(0,0), (1,2), (3,1)]）。
输出：最短路径及其长度。

  
import math  
import random  

def distance(city1, city2):  
    return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)  

def total_distance(path):  
    return sum(distance(path[i], path[i+1]) for i in range(len(path)-1))  

def generate_neighbor(path):  
    i, j = sorted(random.sample(range(len(path)), 2))  
    return path[:i] + path[i:j+1][::-1] + path[j+1:]  

# 模拟退火主函数  
def tsp_simulated_annealing(cities, initial_temp=10000, cooling_rate=0.995, max_iterations=10000):  
    current_path = cities.copy()  
    random.shuffle(current_path)  
    current_distance = total_distance(current_path)  
    best_path = current_path.copy()  
    best_distance = current_distance  
    temp = initial_temp  

    for _ in range(max_iterations):  
        new_path = generate_neighbor(current_path)  
        new_distance = total_distance(new_path)  

        if new_distance < current_distance or random.random() < math.exp((current_distance - new_distance) / temp):  
            current_path, current_distance = new_path, new_distance  

            if new_distance < best_distance:  
                best_path, best_distance = new_path, new_distance  

        temp *= cooling_rate  

    return best_path, best_distance  

# 示例运行  
cities = [(0, 0), (1, 2), (3, 1), (5, 4)]  
path, dist = tsp_simulated_annealing(cities)  
print(f"最短路径: {path}, 总距离: {dist:.2f}")

输出示例：

  
最短路径: [(0, 0), (1, 2), (3, 1), (5, 4)], 总距离: 7.41

参数调优[编辑 | 编辑源代码]

关键参数对算法性能的影响：

初始温度：过高导致计算浪费，过低可能陷入局部最优。
冷却率：通常选择 0.9~0.999，过小收敛快但可能错过全局最优。
停止条件：可设为温度阈值或固定迭代次数。

实际应用[编辑 | 编辑源代码]

VLSI设计：优化芯片布局布线。
调度问题：如工厂任务排程。
机器学习：超参数调优。

可视化[编辑 | 编辑源代码]

与其他算法对比[编辑 | 编辑源代码]

模拟退火 vs 其他优化算法
算法	优点	缺点
模拟退火	避免局部最优	参数敏感
遗传算法	并行性强	编码复杂
梯度下降	收敛快	需可导函数

总结[编辑 | 编辑源代码]

模拟退火通过引入随机性和渐进的“冷却”策略，在复杂搜索空间中高效寻找近似全局最优解。尽管其性能依赖参数选择，但在组合优化领域仍被广泛应用。