模拟退火算法求解TSP问题
发布时间
阅读量：
阅读量
模拟退火算法（Simulated Annealing, SA）是一种典型的全局搜索优化方法，在处理具有复杂约束条件下的组合优化问题方面具有显著优势。例如旅行商问题（TSP），该算法旨在找到一条闭合回路路径，在满足所有城市节点必须被遍历且仅访问一次的前提下，并使总行程距离达到最小值。
模拟退火算法求解 TSP 问题的基本步骤：
初始化温度和初始解 ：
首先随机初始化一个城市排列。
设置初始温度TTT并设定降温系数。
在每个迭代周期中执行以下步骤：
- 选择下一个候选解；
- 计算候选解的成本函数值；
- 比较新旧解的成本并决定是否接受新解；
- 根据当前温度计算接受概率；
- 根据设定的降温系数更新当前温度；
- 当达到终止条件时退出循环。
循环降温过程 ：
- 按照给定的温度 TTT 值，在给定的温度下进行若干次迭代。
- 每一次迭代过程中，在当前解的基础上施加一次扰动（如随机互换两个城市的位置），从而生成新的解。
评价新解 ：
- 评估新解的总路径长度。
- 求取能量差 \Delta E = E_{\text{new}} - E_{\text{old}}（基于两路径之间的总距离差异）。
- 当能量差小于等于零时（即新路径更优），接受该新解。
- 当能量差为正时，则按照概率 p = \exp(-\Delta E / T) 接受该新解；同时，在初始阶段时态与当前状态越接近时被接受的可能性越大。
.
降低温度 ：
在每一轮循环结束后通过降温公式对温度进行更新，并根据降温比值调整当前温度值。
终止条件 ：
当温度降至设定的最小值以下或达到预先设定的最大循环次数时（T_{\text{min}}），该算法终止运行并输出当前找到的最优解
模拟退火算法代码示例 (Python)
import numpy as np
import matplotlib.pyplot as plt
import os
class TSPSimulatedAnnealing:
def __init__(self, filename, save_dir='results', initial_temperature=1000, min_temperature=1e-5, cooling_rate=0.999, max_iterations=100000000):
self.coords = self.read_tsp_file(filename)
self.distance_matrix = self.calculate_distance_matrix(self.coords)
self.initial_temperature = initial_temperature
self.min_temperature = min_temperature
self.cooling_rate = cooling_rate
self.max_iterations = max_iterations
self.save_dir = save_dir
os.makedirs(self.save_dir, exist_ok=True)
def read_tsp_file(self, filename):
"""读取 TSP 文件并返回城市坐标列表"""
coords = []
with open(filename, 'r') as file:
for line in file:
if line.strip() == 'NODE_COORD_SECTION':
break
for line in file:
if line.strip() == 'EOF':
break
parts = line.strip().split()
coords.append((float(parts[1]), float(parts[2])))
return np.array(coords)
def calculate_distance_matrix(self, coords):
"""计算城市之间的欧几里得距离矩阵"""
return np.sqrt(((coords[:, np.newaxis] - coords) ** 2).sum(axis=2))
def calculate_total_distance(self, route):
"""计算给定路线的总距离"""
return sum(self.distance_matrix[route[i - 1], route[i]] for i in range(len(route)))
def perturbation(self, route):
"""使用反转区间法扰动生成新解"""
new_route = np.copy(route)
i, j = sorted(np.random.choice(len(route), 2, replace=False))
new_route[i:j+1] = new_route[i:j+1][::-1]
return new_route
def simulated_annealing(self):
"""使用模拟退火算法求解 TSP 问题"""
num_cities = len(self.distance_matrix)
current_solution = np.arange(num_cities)
np.random.shuffle(current_solution)
current_distance = self.calculate_total_distance(current_solution)
T = self.initial_temperature
best_solution = np.copy(current_solution)
best_distance = current_distance
iteration = 0
no_improve_count = 0
while T > self.min_temperature and iteration < self.max_iterations:
new_solution = self.perturbation(current_solution)
new_distance = self.calculate_total_distance(new_solution)
delta = new_distance - current_distance
if delta < 0 or np.random.rand() < np.exp(-delta / T):
current_solution = new_solution
current_distance = new_distance
no_improve_count = 0
if current_distance < best_distance:
best_solution = np.copy(current_solution)
best_distance = current_distance
else:
no_improve_count += 1
if no_improve_count > 500:
T *= (self.cooling_rate + 0.001)
no_improve_count = 0
else:
T *= self.cooling_rate
iteration += 1
# 保存最佳路径和最短距离
self.save_results(best_solution, best_distance)
return best_solution, best_distance
def save_results(self, best_solution, best_distance):
"""保存最优路径、最短距离和图像"""
# 保存路径数据
with open(os.path.join(self.save_dir, 'best_path.txt'), 'w') as file:
file.write("最优访问路径: " + ' '.join(map(lambda x: str(x + 1), best_solution)) + "\n")
file.write(f"最短总距离: {best_distance}\n")
# 保存路径图
self.plot_path(best_solution, os.path.join(self.save_dir, 'best_path.png'))
def plot_path(self, path, save_path=None):
"""绘制城市及其路径并保存图像"""
city_coords = self.coords
plt.figure(figsize=(20, 15))
path = np.append(path, path[0])
x = [city_coords[i][0] for i in path]
y = [city_coords[i][1] for i in path]
plt.plot(x, y, linestyle='--', linewidth=2, markersize=10, color='red')
plt.plot(x, y, marker='o', markersize=10, linewidth=0, color='black')
for idx, i in enumerate(path[:-1]):
if idx == 0:
plt.text(city_coords[i][0], city_coords[i][1], str(i + 1), fontsize=20, ha='right', color='red')
else:
plt.text(city_coords[i][0], city_coords[i][1], str(i + 1), fontsize=15, ha='right')
plt.title('SA_TSP Optimal Path', fontsize=20)
plt.xlabel('X ', fontsize=20)
plt.ylabel('Y ', fontsize=20)
plt.xticks(fontsize=20)
plt.yticks(fontsize=20)
plt.grid(True)
if save_path:
plt.savefig(save_path)
plt.close()
# 示例
filename = 'kroB100.tsp'
solver = TSPSimulatedAnnealing(filename)
best_solution, best_distance = solver.simulated_annealing()
print("最佳路径:", best_solution)
print("最短距离:", best_distance)
python
全部评论 (0)
还没有任何评论哟~