import math import random import matplotlib.pyplot as plt from collections import deque from typing import List, Tuple class TSPSolver: def __init__(self, cities: List[Tuple[int, int]], max_iter: int = 1000, base_tabu_length: int = 50, candidate_size: int = 50): # 数据初始化 self.cities = cities self.n = len(cities) self.distance_matrix = self._calc_distance_matrix() # 算法参数 self.max_iter = max_iter self.base_tabu_length = base_tabu_length self.candidate_size = candidate_size # 状态变量 self.current_solution = None self.best_solution = None self.best_cost = float('inf') self.tabu_list = deque(maxlen=base_tabu_length) self.history = {'best_cost': [], 'current_cost': []} # 初始化解决方案 self._initialize_solution() def _calc_distance_matrix(self) -> List[List[float]]: """计算距离矩阵""" matrix = [[0.0] * self.n for _ in range(self.n)] for i in range(self.n): for j in range(self.n): if i != j: dx = self.cities[i][0] - self.cities[j][0] dy = self.cities[i][1] - self.cities[j][1] matrix[i][j] = math.sqrt(dx ** 2 + dy ** 2) return matrix def _initialize_solution(self): """生成初始解""" random.seed(100) self.current_solution = list(range(self.n)) random.shuffle(self.current_solution) self.best_solution = self.current_solution.copy() self.best_cost = self._evaluate(self.best_solution) def _dynamic_tabu_length(self) -> int: """动态禁忌长度策略""" current_iter = len(self.history['best_cost']) return int(self.base_tabu_length * (1 + math.log(current_iter + 1) / 10)) def _generate_neighborhood(self) -> List[List[int]]: """混合邻域生成（交换操作+2-opt）""" candidates = [] for _ in range(self.candidate_size): if random.random() < 0.7: # 70%概率使用交换操作 i, j = sorted(random.sample(range(self.n), 2)) new_sol = self.current_solution.copy() new_sol[i], new_sol[j] = new_sol[j], new_sol[i] else: # 30%概率使用2-opt i, j = sorted(random.sample(range(self.n), 2)) new_sol = self.current_solution[:i] + \ self.current_solution[i:j][::-1] + \ self.current_solution[j:] candidates.append(new_sol) return candidates def _evaluate(self, solution: List[int]) -> float: """计算路径长度""" total = 0.0 for i in range(self.n): total += self.distance_matrix[solution[i]][solution[(i + 1) % self.n]] return total def optimize(self): """执行优化主循环""" for iteration in range(self.max_iter): candidates = self._generate_neighborhood() best_candidate_cost = float('inf') best_candidate = None selected_move = None for sol in candidates: cost = self._evaluate(sol) # 移动表示为排序后的城市索引对 move = tuple(sorted(( self.current_solution.index(sol[0]), self.current_solution.index(sol[1])) )) if len(sol) > 1 else (0, 0) # 破禁条件判断 if (move in self.tabu_list and cost < self.best_cost) \ or (move not in self.tabu_list): if cost < best_candidate_cost: best_candidate_cost = cost best_candidate = sol selected_move = move # 更新当前解 if best_candidate is not None: self.current_solution = best_candidate current_cost = best_candidate_cost # 更新最优解 if current_cost < self.best_cost: self.best_solution = best_candidate.copy() self.best_cost = current_cost # 更新禁忌表 self.tabu_list.append(selected_move) self.tabu_list = deque( list(self.tabu_list)[-self._dynamic_tabu_length():], maxlen=self._dynamic_tabu_length() ) # 记录历史数据 self.history['best_cost'].append(self.best_cost) self.history['current_cost'].append(current_cost) # 打印进度 if iteration % 100 == 0: print(f"Iteration {iteration}: Best Cost = {self.best_cost:.2f}") # 绘制收敛曲线 plt.figure(figsize=(10, 6)) plt.plot(self.history['best_cost'], label='Best Cost') plt.plot(self.history['current_cost'], label='Current Cost') plt.xlabel('Iteration') plt.ylabel('Tour Length') plt.title('Convergence Curve') plt.legend() plt.savefig('convergence.png') plt.close() # 绘制收敛曲线（论文规格） plt.figure(figsize=(12, 8), dpi=300) # 提高分辨率和尺寸 plt.plot(self.history['best_cost'], color='#2c7bb6', linewidth=2.5, linestyle='-', label='Best Solution Length') plt.plot(self.history['current_cost'], color='#d7191c', linewidth=1.2, linestyle='--', alpha=0.7, label='Current Solution Length') # 标注最优解 min_idx = self.history['best_cost'].index(min(self.history['best_cost'])) plt.scatter(min_idx, self.best_cost, color='#fdae61', s=120, zorder=5, label=f'Optimal Point ({self.best_cost:.2f})') # 图表格式设置 plt.xlabel('Iteration', fontsize=14, fontweight='bold') plt.ylabel('Tour Length', fontsize=14, fontweight='bold') plt.title('Tabu Search Convergence Profile\n(50-City TSP Instance)', fontsize=16, pad=20) plt.grid(True, linestyle=':', alpha=0.7) plt.legend(fontsize=12, loc='upper right', frameon=True, shadow=True) # 坐标轴范围优化 plt.xlim(0, len(self.history['best_cost'])) buffer = 0.1 * (max(self.history['best_cost']) - self.best_cost) plt.ylim(self.best_cost - buffer, max(self.history['best_cost']) + buffer) # 保存多种格式 plt.savefig('convergence.pdf', bbox_inches='tight') # 矢量格式用于论文 plt.savefig('convergence.png', dpi=300, bbox_inches='tight') # 位图格式用于预览 print(f"convergence saved to convergence.png/.pdg") plt.close() # 输出最终结果 print(f"\nBest Tour Length: {self.best_cost:.2f}") print("Optimal Route:", self.best_solution) def plot_optimal_route(cities, solution, save_path='optimal_route.png'): """在坐标图上绘制TSP最优路径 Args: cities: 城市坐标列表 [(x1,y1), (x2,y2), ...] solution: 最优路径顺序 [idx1, idx2, ..., idxn] save_path: 图片保存路径 """ plt.figure(figsize=(12, 8), dpi=300) # 提取坐标 x = [city[0] for city in cities] y = [city[1] for city in cities] # 绘制城市散点 plt.scatter(x, y, c='red', s=100, edgecolors='black', zorder=10, label='Cities') # 添加城市标签 for i, (xi, yi) in enumerate(zip(x, y)): plt.text(xi + 3, yi + 3, str(i), fontsize=8, ha='center', va='center', bbox=dict(facecolor='white', alpha=0.7, edgecolor='none')) # 绘制路径连线 route_x = [x[i] for i in solution] + [x[solution[0]]] # 闭合路径 route_y = [y[i] for i in solution] + [y[solution[0]]] plt.plot(route_x, route_y, color='#2c7bb6', linewidth=1.5, linestyle='-', marker='o', markersize=6, markerfacecolor='yellow', markeredgecolor='black', label='Optimal Route') # 标注起点和终点 start_x, start_y = x[solution[0]], y[solution[0]] plt.scatter(start_x, start_y, c='green', s=200, edgecolors='black', marker='*', zorder=11, label='Start/End') # 图表美化 plt.title(f'TSP Optimal Route (Total Length: {solver.best_cost:.2f})', fontsize=16, pad=20) plt.xlabel('X Coordinate', fontsize=12) plt.ylabel('Y Coordinate', fontsize=12) plt.grid(True, linestyle='--', alpha=0.3) plt.legend(fontsize=10, loc='upper right') # 保存图像 plt.savefig(save_path, bbox_inches='tight') plt.close() print(f"Optimal route saved to {save_path}") # 实验配置 if __name__ == "__main__": # 固定城市坐标（与论文实验一致） cities = [(60, 200), (180, 200), (80, 180), (140, 180), (20, 160), (100, 160), (200, 160), (140, 140), (40, 120), (100, 120), (180, 100), (60, 80), (120, 80), (180, 60), (20, 40), (100, 40), (200, 40), (20, 20), (60, 20), (160, 20), (50, 150), (110, 150), (170, 150), (70, 130), (130, 130), (190, 130), (30, 110), (90, 110), (150, 110), (10, 90), (80, 90), (160, 90), (40, 70), (120, 70), (200, 70), (20, 50), (100, 50), (180, 50), (60, 30), (140, 30), (90, 170), (170, 170), (30, 150), (150, 150), (50, 130), (130, 130), (10, 110), (70, 110), (190, 110), (110, 90)] # 保持原有坐标数据 import matplotlib.pyplot as plt # 提取x,y坐标 x = [city[0] for city in cities] y = [city[1] for city in cities] plt.figure(figsize=(10, 6)) plt.scatter(x, y, c='red', s=50, edgecolors='black', alpha=0.7) # 添加城市标签 for i, (xi, yi) in enumerate(zip(x, y)): plt.text(xi + 2, yi + 2, str(i), fontsize=8, ha='center', va='center') plt.title('50-City TSP Problem Coordinates', fontsize=14) plt.xlabel('X Coordinate', fontsize=12) plt.ylabel('Y Coordinate', fontsize=12) plt.grid(True, linestyle='--', alpha=0.5) plt.tight_layout() plt.savefig('city_coordinates.png', dpi=300) plt.show() # 初始化求解器 solver = TSPSolver( cities=cities, max_iter=1000, base_tabu_length=int(math.sqrt(len(cities))), candidate_size=2 * len(cities) ) # 执行优化 solver.optimize() plot_optimal_route(cities, solver.best_solution)