退火算法 是一种启发式优化算法，灵感来源于金属退火过程。在金属退火中，将金属加热到高温然后逐渐冷却，以消除内部结晶缺陷，使其达到更稳定的状态。类比于优化问题，退火算法通过模拟这个过程，从一个高温状态开始，逐渐减小温度，使系统跳出局部最小值，最终趋向全局最优解。
基本思想：
- 初始化： 随机生成初始解。
- 温度控制： 引入温度参数，控制在一定范围内。
- 接受准则： 根据一定准则（如Metropolis准则），接受或拒绝新解。
- 降温策略： 逐渐降低温度，减小接受新解的概率。
- 收敛： 当温度足够低或者满足停止条件时，算法收敛，返回当前解。
算法流程：
- 初始化： 随机生成初始解 x xx。
- 重复迭代过程：
a. 产生当前解的邻域解 x ′ x'x′。
b. 计算目标函数值差 Δ f = f ( x ′ ) − f ( x ) \Delta f = f(x') - f(x)Δf=f(x′)−f(x)。
c. 若 Δ f < 0 \Delta f < 0Δf<0，接受 x ′ x'x′ 作为新解；否则，以概率 e − Δ f / T e^{-\Delta f/T}e−Δf/T 接受 x ′ x'x′。
d. 更新当前解为 x ′ x'x′。
e. 降低温度 T TT。
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准则接受或拒绝新解。随着温度的降低，接受概率减小，最终趋向全局最优解。
