模拟退火算法（SA算法）求解实例---旅行商问题 (TSP)

一、采用SA求解 TSP

求解代码在文中，后续会出其他算法求解TSP问题，你们参加数学建模竞赛只需要会改代码即可。

用来对比此专栏的
遗传算法（GA算法）求解实例—旅行商问题 (TSP)
粒子群算法（PSO算法）求解实例—旅行商问题 (TSP)
注意每次运行SA算法得到的结果可能不太一样。

我知道大家对原理性的东西不感兴趣，我把原理性的东西放在后面，大家如果需要写数模论文可以拿去，但是记得需要改一改，要不然查重过不去。

二、 旅行商问题

2.1 实际例子：求解 6 个城市的 TSP

假设有 6 个城市，其坐标如下：

城市	X 坐标	Y 坐标
0	10	20
1	30	40
2	20	10
3	40	30
4	10	10
5	50	20

目标是找到一个经过所有城市且总距离最短的路径。

2.2 求解该问题的代码

import numpy as np
import random
import math# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):return np.sqrt(np.sum((city1 - city2) ** 2))# 计算总旅行距离
def total_distance(path):distance = 0for i in range(len(path) - 1):distance += calculate_distance(cities[path[i]], cities[path[i + 1]])distance += calculate_distance(cities[path[-1]], cities[path[0]])  # 回到起点return distance# 模拟退火算法主函数
def simulated_annealing(cities, initial_temp=1000, cooling_rate=0.995, max_iter=1000):num_cities = len(cities)# 初始化解和温度current_path = list(np.random.permutation(num_cities))current_distance = total_distance(current_path)best_path = current_path.copy()best_distance = current_distancetemperature = initial_tempfor iteration in range(max_iter):# 生成新解：随机交换路径中的两个城市new_path = current_path.copy()i, j = np.random.choice(num_cities, 2, replace=False)new_path[i], new_path[j] = new_path[j], new_path[i]# 计算新解的距离new_distance = total_distance(new_path)# 接受新解的条件if new_distance < current_distance or random.random() < math.exp((current_distance - new_distance) / temperature):current_path = new_pathcurrent_distance = new_distance# 更新最佳解if current_distance < best_distance:best_path = current_pathbest_distance = current_distance# 降温temperature *= cooling_rate# 输出当前迭代的信息print(f"Iteration {iteration}: Best distance = {best_distance:.2f}, Temperature = {temperature:.2f}")# 如果温度低到一定程度，停止搜索if temperature < 1e-8:breakreturn best_path, best_distance# 运行模拟退火算法
best_path, best_distance = simulated_annealing(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)

2.3 代码运行过程截屏

2.4 代码运行结果截屏（后续和其他算法进行对比）

三、 如何修改代码？

这一部分是重中之重，大家参加数学建模肯定是想跑出自己的结果，所以大家只需要把自己遇到的数学问题，抽象成TSP问题，然后修改代码的城市坐标，然后运行即可。

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])

3.1 减少城市坐标，如下：

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30]
])

3.2 增加城市坐标，如下：

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[30, 40],[20, 10],[10, 10],[50, 20]
])

四、 模拟退火算法 (Simulated Annealing, SA) 原理

4.1 模拟退火算法定义

模拟退火算法 (Simulated Annealing, SA) 是一种基于概率的随机搜索优化算法，由 S. Kirkpatrick 等人在 1983 年提出。模拟退火算法借鉴了固体退火过程的物理原理，通过在解空间中随机搜索和逐步降低“温度”，找到全局最优解或近似最优解。该算法常用于求解组合优化问题，如旅行商问题 (TSP)、生产调度、资源分配等。

4.2 SA算法的基本思想

模拟退火算法的核心思想是模拟物理退火过程中固体的冷却过程。在退火过程中，固体被加热到一个足够高的温度，然后逐渐冷却，使得固体内部的原子能量状态逐渐达到最小值（即晶格结构最稳定）。在优化问题中，这一过程对应于在解空间中随机搜索，并通过概率准则接受劣解，以避免陷入局部最优解。

4.3 SA算法的工作原理

1. 初始化：

   • 随机生成一个初始解，并设定初始温度 T 和降温速率 α（通常为小于 1 的常数）。
   • 计算初始解的目标函数值（或称“能量”）。

2. 迭代过程：

   • 在当前解的邻域内随机生成一个新解。
   • 计算新解的目标函数值。如果新解更优，则接受该解作为当前解。
   • 如果新解不优，以一定概率接受该解：
     [
     P = \exp\left(-\frac{\Delta E}{T}\right)
     ]
     其中，ΔE 是新解和当前解的目标函数值之差，T 是当前温度。
   • 根据冷却速率 α 更新温度：
     [
     T \leftarrow \alpha \cdot T
     ]

3. 终止条件：

   • 当达到最大迭代次数或温度低于某一阈值时，停止搜索，输出当前最优解。

4.4 SA算法的参数

• 初始温度 (T)：初始的高温状态，控制初期的搜索范围和探索能力。温度越高，算法越容易接受劣解，从而有更好的全局探索能力。
• 降温速率 (α)：控制温度的降低速度，通常设为接近 1 的数值（如 0.99）。降温速率过快可能导致过早收敛到局部最优解。
• 迭代次数：算法运行的最大迭代次数。迭代次数越多，算法有更大的机会找到全局最优解。

4.5 SA算法的优缺点

4.5.1 优点

• 跳出局部最优：通过接受劣解的概率机制，SA 算法能够有效跳出局部最优解，逼近全局最优解。
• 简单易实现：算法结构简单，易于实现和应用于多种优化问题。
• 适应性强：SA 算法可以处理非线性、非连续和多峰值的复杂优化问题。

4.5.2 缺点

• 收敛速度较慢：SA 算法在初期的高温阶段具有较强的探索能力，但温度降低后搜索步长缩小，收敛速度较慢。
• 参数敏感：算法性能对初始温度、降温速率等参数较为敏感，需要根据问题特点进行调节。
• 计算开销大：在温度较高和迭代次数较多的情况下，计算开销较大。

4.6 SA算法的应用场景

• 组合优化问题：如旅行商问题 (TSP)、背包问题、图着色问题等。
• 工程设计优化：如集成电路布局优化、结构设计优化等。
• 机器学习：如神经网络训练、特征选择、参数优化等。
• 生产调度与资源分配：如车间调度、任务分配、物流配送等。

4.7 SA算法求解TSP步骤

1. 初始化：随机生成一个初始路径，并计算路径的总旅行距离。
2. 迭代过程：在当前路径的邻域内（如交换两个城市的位置）随机生成一个新路径，计算新路径的总旅行距离。
   • 如果新路径更短，则接受该路径作为当前解。
   • 如果新路径更长，以一定概率接受该解，以避免陷入局部最优。
3. 降温：逐步降低温度，减少接受劣解的概率。
4. 终止条件：当达到最大迭代次数或温度低到一定程度时，停止搜索，输出当前最优路径。