yelp商家数据集上使用火算法求解TSP 问题

先简要回顾下什么是TSP问题，旅行商问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，广泛应用于运筹学、计算机科学和物流等领域。TSP的基本描述如下：

问题描述

定义：假设有一位旅行商需要访问一组城市（或地点），每个城市只能访问一次，最后旅行商需要返回到起始城市。
目标：找到一条最短的路径，使得旅行商能够访问所有城市一次，并返回起点。

yelp 数据集里yelp_academic_dataset_business.json 刚好有饭馆的位置信息

因此在该数据集上求解TSP 问题可以理解为找到最佳路线去吃遍所有馆子，嗯~吃货的最爱

本文就不赘絮退火算法的细节了，直接在yelp数据集上试验退火算法

把店铺的位置信息输出到csv文件总里

# coding=utf-8
import json
import csv  # Ensure this line is present to import the csv module# 读取JSON文件
with open('yelp_academic_dataset_business.json', 'r', encoding='utf-8') as file:businesses = []for line in file:business = json.loads(line)# 筛选出餐厅if 'Restaurants' in business['categories']:businesses.append({'name': business['name'],'latitude': business['latitude'],'longitude': business['longitude'],'id': business['business_id']})# 将餐厅信息输出到CSV文件
with open('restaurants.csv', 'w', newline='', encoding='utf-8') as csvfile:fieldnames = ['name', 'latitude', 'longitude', 'id']writer = csv.DictWriter(csvfile, fieldnames=fieldnames)writer.writeheader()  # 写入表头for business in businesses:writer.writerow(business)  # 写入每一行数据print("餐厅信息已成功输出到 restaurants.csv")

要使用退火算法处理从 restaurants.csv 文件中提取的位置信息，以解决旅行商问题（TSP），可以按照以下步骤进行：

步骤概述

读取CSV文件：加载餐厅位置信息，包括名称、纬度和经度。
计算距离：实现一个函数，计算餐厅之间的距离。
实现退火算法：使用退火算法寻找最佳巡游路径。
输出结果：打印最佳路径及其总距离。

# 计算两个餐厅之间的距离（Haversine公式）
def haversine(coord1, coord2):R = 6371  # 地球半径，单位为公里lat1, lon1 = coord1lat2, lon2 = coord2dlat = np.radians(lat2 - lat1)dlon = np.radians(lon2 - lon1)a = np.sin(dlat/2) ** 2 + np.cos(np.radians(lat1)) * np.cos(np.radians(lat2)) * np.sin(dlon/2) ** 2c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1 - a))return R * c

Haversine公式：

计算地球表面两点（餐厅）之间的距离。
输入为两个坐标（纬度和经度），输出为两点之间的距离（公里）。

# 计算路径总长度
def total_distance(path):dist = 0for i in range(len(path)):dist += haversine((path[i]['latitude'], path[i]['longitude']),(path[(i + 1) % len(path)]['latitude'], path[(i + 1) % len(path)]['longitude']))return dist

路径长度计算：

遍历给定路径，计算从一个餐厅到下一个餐厅的总距离。
使用Haversine公式，确保路径是循环的，即最后一个餐厅回到第一个餐厅。

退火算法实现：

# 退火算法
def simulated_annealing(initial_path, initial_temp, cooling_rate, max_iterations):current_path = initial_pathcurrent_temp = initial_tempcurrent_dist = total_distance(current_path)best_path = current_path[:]best_dist = current_distfor iteration in range(max_iterations):# 生成新解new_path = current_path[:]i, j = random.sample(range(len(new_path)), 2)new_path[i], new_path[j] = new_path[j], new_path[i]  # 交换new_dist = total_distance(new_path)# 接受新解if new_dist < current_dist or random.random() < math.exp((current_dist - new_dist) / current_temp):current_path = new_pathcurrent_dist = new_dist# 更新最佳解if current_dist < best_dist:best_path = current_path[:]best_dist = current_dist# 降温current_temp *= cooling_ratereturn best_path, best_dist

参数：
- initial_path：初始路径（餐厅顺序）。
- initial_temp：初始温度，用于控制接受新解的概率。
- cooling_rate：降温速率，控制温度下降的速度。
- max_iterations：最大迭代次数。
过程：
- 初始化当前路径和距离为初始路径和计算的总距离。
- 进行多次迭代：
  - 生成新路径，通过随机交换路径中的两个餐厅。
  - 计算新路径的总距离。
  - 根据接受准则决定是否接受新路径：
    - 如果新路径更短，则直接接受。
    - 如果新路径更长，则以一定概率接受（根据当前温度计算）。
  - 更新当前路径和最佳路径。
  - 降温，逐步减少温度。

# 初始化参数
initial_path = restaurants[:]  # 使用所有餐厅
random.shuffle(initial_path)  # 随机打乱初始路径
best_path, best_distance = simulated_annealing(initial_path, initial_temp=1000, cooling_rate=0.995, max_iterations=10000)

参数设置：

使用所有餐厅的初始路径。
随机打乱路径顺序以增加多样性。
调用退火算法并获取最佳路径和最短距离。

完整代码如下

import csv
import numpy as np
import random
import math
import matplotlib.pyplot as plt
import seaborn as sns
from tqdm import tqdm  # 导入 tqdm 库# 读取CSV文件
restaurants = []
with open('restaurants.csv', 'r', encoding='utf-8') as csvfile:reader = csv.DictReader(csvfile)for row in reader:restaurants.append({'name': row['name'],'latitude': float(row['latitude']),'longitude': float(row['longitude']),'id': row['id']})def haversine(coord1, coord2):R = 6371  # 地球半径，单位为公里lat1, lon1 = coord1lat2, lon2 = coord2dlat = np.radians(lat2 - lat1)dlon = np.radians(lon2 - lon1)a = np.sin(dlat/2) ** 2 + np.cos(np.radians(lat1)) * np.cos(np.radians(lat2)) * np.sin(dlon/2) ** 2c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1 - a))return R * cdef total_distance(path):dist = 0for i in range(len(path)):dist += haversine((path[i]['latitude'], path[i]['longitude']),(path[(i + 1) % len(path)]['latitude'], path[(i + 1) % len(path)]['longitude']))return distdef simulated_annealing(initial_path, initial_temp, cooling_rate, max_iterations):current_path = initial_pathcurrent_temp = initial_tempcurrent_dist = total_distance(current_path)best_path = current_path[:]best_dist = current_dist# 记录每次迭代的路径和距离distances = []# 使用 tqdm 显示进度条for iteration in tqdm(range(max_iterations), desc="优化进度"):new_path = current_path[:]i, j = random.sample(range(len(new_path)), 2)new_path[i], new_path[j] = new_path[j], new_path[i]  # 交换new_dist = total_distance(new_path)if new_dist < current_dist or random.random() < math.exp((current_dist - new_dist) / current_temp):current_path = new_pathcurrent_dist = new_distif current_dist < best_dist:best_path = current_path[:]best_dist = current_dist# 记录当前距离distances.append(current_dist)current_temp *= cooling_ratereturn best_path, best_dist, distances# 初始化参数
initial_path = restaurants[:]
random.shuffle(initial_path)
best_path, best_distance, distances = simulated_annealing(initial_path, initial_temp=1000, cooling_rate=0.995, max_iterations=10000)# 输出结果
print("最佳路径:")
for restaurant in best_path:print(restaurant['name'])
print("最短距离: {:.2f} 公里".format(best_distance))

添加热力图，热力图将显示每次迭代中路径的总距离，横轴表示迭代次数，纵轴表示路径总距离。通过这种可视化，您可以直观地观察到退火算法在求解过程中如何逐步降低路径总距离。

# 可视化热力图
plt.figure(figsize=(12, 6))
sns.heatmap(np.array(distances).reshape(-1, 1), cmap='YlGnBu', cbar=True)
plt.title('退火算法迭代过程中的路径总距离变化')
plt.xlabel('迭代次数')
plt.ylabel('路径总距离')
plt.show()

记录距离变化：
- 在 simulated_annealing 函数中，增加了一个 distances 列表，用于记录每次迭代的总距离。
绘制热力图：
- 使用 Matplotlib 和 Seaborn 库绘制热力图：将 distances 列表转换为 NumPy 数组，并重塑为适合热力图的形状（这里是单列）。使用 sns.heatmap 绘制热力图，显示路径总距离的变化。