编辑“︁模拟退火算法”︁

{{DISPLAYTITLE:模拟退火算法}}  
{{算法导航}}  

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

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

算法通过以下参数控制搜索过程：  
* '''温度（T）'''：控制接受劣解的概率，初始温度高，逐渐降低。  
* '''冷却率（α）'''：温度下降速度（如 <math>T_{new} = \alpha \times T_{current}</math>）。  
* '''能量函数（E）'''：即目标函数，需最小化的值。  

=== 数学表达 ===  
接受新解的概率由'''Metropolis准则'''决定：  
<math>P = \begin{cases}  
1 & \text{若 } E_{new} < E_{current}, \\  
e^{-\frac{E_{new}-E_{current}}{T}} & \text{否则}.  
\end{cases}</math>  

== 算法步骤 ==  
以下是伪代码实现：  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

== 示例：旅行商问题（TSP） ==  
=== 输入与输出 ===  
* '''输入'''：城市坐标列表（如 <code>[(0,0), (1,2), (3,1)]</code>）。  
* '''输出'''：最短路径及其长度。  

<syntaxhighlight lang="python">  
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}")  
</syntaxhighlight>  

'''输出示例'''：  
<pre>  
最短路径: [(0, 0), (1, 2), (3, 1), (5, 4)], 总距离: 7.41  
</pre>  

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

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

== 可视化 ==  
<mermaid>  
graph LR  
    A[初始解] --> B[生成邻域解]  
    B --> C{接受新解?}  
    C -->|是| D[更新当前解]  
    C -->|否| B  
    D --> E{温度降低}  
    E -->|未终止| B  
    E -->|终止| F[输出最优解]  
</mermaid>  

== 与其他算法对比 ==  
{| class="wikitable"  
|+ 模拟退火 vs 其他优化算法  
! 算法 !! 优点 !! 缺点  
|-  
| 模拟退火 || 避免局部最优 || 参数敏感  
|-  
| 遗传算法 || 并行性强 || 编码复杂  
|-  
| 梯度下降 || 收敛快 || 需可导函数  
|}  

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:随机化算法]]