目录
- 一、采用SA求解 TSP
- 二、 旅行商问题
- 2.1 实际例子:求解 6 个城市的 TSP
- 2.2 ==**求解该问题的代码**==
- 2.3 代码运行过程截屏
- 2.4 代码运行结果截屏(后续和其他算法进行对比)
- 三、 ==如何修改代码?==
- 3.1 减少城市坐标,如下:
- 3.2 增加城市坐标,如下:
- 四、 模拟退火算法 (Simulated Annealing, SA) 原理
- 4.1 模拟退火算法定义
- 4.2 SA算法的基本思想
- 4.3 SA算法的工作原理
- 4.4 SA算法的参数
- 4.5 SA算法的优缺点
- 4.5.1 优点
- 4.5.2 缺点
- 4.6 SA算法的应用场景
- 4.7 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算法的工作原理
-
初始化:
- 随机生成一个初始解,并设定初始温度
T
和降温速率α
(通常为小于 1 的常数)。 - 计算初始解的目标函数值(或称“能量”)。
- 随机生成一个初始解,并设定初始温度
-
迭代过程:
- 在当前解的邻域内随机生成一个新解。
- 计算新解的目标函数值。如果新解更优,则接受该解作为当前解。
- 如果新解不优,以一定概率接受该解:
[
P = \exp\left(-\frac{\Delta E}{T}\right)
]
其中,ΔE
是新解和当前解的目标函数值之差,T
是当前温度。 - 根据冷却速率
α
更新温度:
[
T \leftarrow \alpha \cdot T
]
-
终止条件:
- 当达到最大迭代次数或温度低于某一阈值时,停止搜索,输出当前最优解。
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步骤
- 初始化:随机生成一个初始路径,并计算路径的总旅行距离。
- 迭代过程:在当前路径的邻域内(如交换两个城市的位置)随机生成一个新路径,计算新路径的总旅行距离。
- 如果新路径更短,则接受该路径作为当前解。
- 如果新路径更长,以一定概率接受该解,以避免陷入局部最优。
- 降温:逐步降低温度,减少接受劣解的概率。
- 终止条件:当达到最大迭代次数或温度低到一定程度时,停止搜索,输出当前最优路径。