智能优化算法之模拟退火算法SA

发展历史和算法思想

模拟退火算法（Simulated Annealing, SA）是一种基于热力学原理的随机优化算法，最早由 S. Kirkpatrick, C. D. Gelatt 和 M. P. Vecchi 于 1983 年提出。算法的灵感来自于固体物理学中的退火过程：通过加热和缓慢冷却金属，可以减少其结构中的缺陷，使其达到低能量的稳定状态。

数学原理

模拟退火算法的核心思想是通过模拟退火过程来搜索最优解。在优化过程中，算法允许在一定概率下接受较差的解，以避免陷入局部最优解。该概率由以下公式给出：

其中：

• 是当前解的能量（目标函数值）。

• 是新解的能量。

• 是当前温度。

• 是指数函数。

当温度逐渐降低时，算法更倾向于接受更优的解。通过适当的降温策略，算法可以逐步逼近全局最优解。

主要步骤：

1. 初始化：设定初始温度 和初始解 。

2. 邻域搜索：从当前解 的邻域中随机选择一个新解 。

3. 能量差计算：计算当前解和新解的能量差 。

4. 接受准则：如果 ，则接受新解；否则，以概率 接受新解。

5. 降温：逐渐降低温度 。

6. 重复步骤 2-5，直到达到停止条件（如温度过低或迭代次数达到上限）。

应用场景

模拟退火算法适用于求解各种组合优化问题和连续优化问题，主要包括但不限于：

• 旅行商问题（TSP）

• 背包问题

• 车辆路径问题

• 图着色问题

• 生产调度问题

• 函数优化

可视化Python示例

以下是一个使用模拟退火算法解决旅行商问题（TSP）的Python可视化示例：

import numpy as np
import matplotlib.pyplot as plt# 计算路径长度
def path_length(path, distance_matrix):return sum(distance_matrix[path[i], path[i+1]] for i in range(len(path)-1)) + distance_matrix[path[-1], path[0]]# 模拟退火算法
def simulated_annealing_tsp(distance_matrix, n_iterations, temp, cooling_rate):num_cities = len(distance_matrix)best_path = np.arange(num_cities)np.random.shuffle(best_path)best_eval = path_length(best_path, distance_matrix)curr_path, curr_eval = best_path.copy(), best_evalscores = [best_eval]for i in range(n_iterations):candidate_path = curr_path.copy()l, r = np.random.randint(0, num_cities, size=2)if l > r:l, r = r, lcandidate_path[l:r+1] = np.flip(candidate_path[l:r+1])candidate_eval = path_length(candidate_path, distance_matrix)if candidate_eval < best_eval:best_path, best_eval = candidate_path.copy(), candidate_evalscores.append(best_eval)print(f"Iteration {i}, Best Score: {best_eval}")diff = candidate_eval - curr_evalt = temp / float(i + 1)metropolis = np.exp(-diff / t)if diff < 0 or np.random.rand() < metropolis:curr_path, curr_eval = candidate_path.copy(), candidate_evaltemp *= cooling_ratereturn best_path, best_eval, scores# 参数设置
num_cities = 20
n_iterations = 1000
temp = 100
cooling_rate = 0.995# 生成随机城市坐标
coords = np.random.rand(num_cities, 2)
distance_matrix = np.linalg.norm(coords[:, np.newaxis] - coords[np.newaxis, :], axis=2)# 运行模拟退火算法
best_path, best_eval, scores = simulated_annealing_tsp(distance_matrix, n_iterations, temp, cooling_rate)
print(f"Best Path: {best_path}, Best Path Length: {best_eval}")# 可视化
plt.figure()
plt.subplot(2, 1, 1)
plt.scatter(coords[:, 0], coords[:, 1], c='red')
for i in range(num_cities):plt.annotate(str(i), (coords[i, 0], coords[i, 1]))
for i in range(num_cities):plt.plot([coords[best_path[i], 0], coords[best_path[(i + 1) % num_cities], 0]],[coords[best_path[i], 1], coords[best_path[(i + 1) % num_cities], 1]], 'b-')
plt.title('Best Path')plt.subplot(2, 1, 2)
plt.plot(scores, label='Best Path Length')
plt.xlabel('Iteration')
plt.ylabel('Path Length')
plt.legend()plt.tight_layout()
plt.show()'''
输出:
...
Iteration 896, Best Score: 4.171655916012842
Iteration 993, Best Score: 4.137952785183053
Best Path: [ 0 13 12 18  8 14  5 11 16  7 10  2  3 15 19  4  6  9 17  1], Best Path Length: 4.137952785183053
'''

可视化结果：

代码说明

1. 计算路径长度函数：计算给定路径的总长度。

2. 模拟退火算法：

   • 初始化当前路径、最佳路径及其评价值。

   • 在每次迭代中，从当前路径的邻域中随机选择一个新路径。

   • 通过反转路径段来生成邻域解。

   • 计算新路径的长度，并根据接受准则决定是否接受新路径。

   • 逐步降低温度，并记录最佳路径的长度。

3. 参数设置：设置城市数量、迭代次数、初始温度和降温率。

4. 生成随机城市坐标：生成随机城市坐标并计算距离矩阵。

5. 运行算法：调用模拟退火算法，并输出最佳路径和最佳路径长度。

6. 可视化：绘制城市坐标图和优化过程中最佳路径长度的变化曲线。

以上内容总结自网络，如有帮助欢迎转发，我们下次再见！