退火算法 是一種啓發式優化算法，靈感來源於金屬退火過程。在金屬退火中，將金屬加熱到高温然後逐漸冷卻，以消除內部結晶缺陷，使其達到更穩定的狀態。類比於優化問題，退火算法通過模擬這個過程，從一個高温狀態開始，逐漸減小温度，使系統跳出局部最小值，最終趨向全局最優解。

基本思想：

1. 初始化： 隨機生成初始解。
2. 温度控制： 引入温度參數，控制在一定範圍內。
3. 接受準則： 根據一定準則（如Metropolis準則），接受或拒絕新解。
4. 降温策略： 逐漸降低温度，減小接受新解的概率。
5. 收斂： 當温度足夠低或者滿足停止條件時，算法收斂，返回當前解。

算法流程：

1. 初始化： 隨機生成初始解 $x$。
2. 重複迭代過程：
   a. 產生當前解的鄰域解 $x'$。
   b. 計算目標函數值差 $\Delta f = f(x') - f(x)$。
   c. 若 $\Delta f < 0$，接受 $x'$ 作為新解；否則，以概率 $e^{-\Delta f/T}$ 接受 $x'$。
   d. 更新當前解為 $x'$。
   e. 降低温度 $T$。
   f. 重複直至滿足停止條件。

示例：
考慮一個簡單的旅行商問題（TSP），目標是找到一條路徑，使得訪問每個城市一次，總路徑長度最短。

import numpy as np

# 生成城市座標
np.random.seed(42)
num_cities = 10
cities = np.random.rand(num_cities, 2)

# 計算路徑長度
def calculate_distance(path, cities):
    distance = 0
    for i in range(len(path) - 1):
        distance += np.linalg.norm(cities[path[i]] - cities[path[i+1]])
    distance += np.linalg.norm(cities[path[-1]] - cities[path[0]])  # 回到起點
    return distance

# 退火算法
def simulated_annealing(cities, max_iterations=1000, initial_temperature=1000, cooling_rate=0.95):
    num_cities = len(cities)
    current_path = np.arange(num_cities)
    np.random.shuffle(current_path)
    current_distance = calculate_distance(current_path, cities)

    best_path = np.copy(current_path)
    best_distance = current_distance

    temperature = initial_temperature

    for iteration in range(max_iterations):
        new_path = np.copy(current_path)
        i, j = np.random.choice(num_cities, size=2, replace=False)
        new_path[i], new_path[j] = new_path[j], new_path[i]
        new_distance = calculate_distance(new_path, cities)

        delta_distance = new_distance - current_distance

        if delta_distance < 0 or np.random.rand() < np.exp(-delta_distance / temperature):
            current_path = np.copy(new_path)
            current_distance = new_distance

            if current_distance < best_distance:
                best_path = np.copy(current_path)
                best_distance = current_distance

        temperature *= cooling_rate

    return best_path, best_distance

# 運行算法
best_path, best_distance = simulated_annealing(cities)

print("最優路徑：", best_path)
print("最短路徑長度：", best_distance)

在這個示例中，我們使用退火算法求解TSP問題。算法通過隨機交換城市的順序來生成新解，根據Metropolis準則接受或拒絕新解。隨着温度的降低，接受概率減小，最終趨向全局最優解。