import matplotlib.pyplot as plt import numpy as np import pandas as pd import seaborn as sns import copy import math import random import time from multiprocessing import Pool as ThreadPool path1='att48.tsp' path2='eil76.tsp' path3='pcb442.tsp' path4='rd100.tsp' path5='tsp225.tsp' def readcity(path): df = pd.read_csv("C:\\文件\\现代优化算法\\TSP训练数据集\\"+path, sep=" ", skiprows=6, header=None) return df df = readcity(path4) city = np.array(range(1,len(df[0][0:len(df)-1])+1)) city_x = np.array(df[1][0:len(df)-1]) city_y = np.array(df[2][0:len(df)-1]) city_pos = np.stack((city_x, city_y), axis=1) def distance(city1, city2): return math.sqrt((city1[0]-city2[0])**2 + (city1[1]-city2[1])**2) def path_length(path): length = 0 for i in range(len(path)-1): length += distance(city_pos[path[i]-1], city_pos[path[i+1]-1]) length += distance(city_pos[path[-1]-1], city_pos[path[0]-1]) return length def initial_solution(): unvisited_cities = list(range(1, len(city)+1)) current_city = random.choice(unvisited_cities) solution = [current_city] unvisited_cities.remove(current_city) while unvisited_cities: next_city = min(unvisited_cities, key=lambda city: distance(city_pos[current_city-1], city_pos[city-1])) unvisited_cities.remove(next_city) solution.append(next_city) current_city = next_city return solution def two_opt_swap(path, i, k): new_path = path[:i] + path[i:k + 1][::-1] + path[k + 1:] return new_path 请以上述代码为开头，输出一段以模拟退火算法解决tsp问题的代码，输入为.tsp文件，要求实现用2-opt法构造邻域、在内循环中用Metropolis准则接受解、用最近邻居构造启发式贪心算法构造初始解、输出初始解和解值、最优解和解值、迭代次数和迭代过程的功能

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
import copy
import math
import random
import time
from multiprocessing import Pool as ThreadPool

path = 'rd100.tsp'

def readcity(path):
df = pd.read_csv("C:\\文件\\现代优化算法\\TSP训练数据集\\"+path, sep=" ", skiprows=6, header=None)
return df

df = readcity(path)

city = np.array(range(1,len(df[0][0:len(df)-1])+1))
city_x = np.array(df[1][0:len(df)-1])
city_y = np.array(df[2][0:len(df)-1])
city_pos = np.stack((city_x, city_y), axis=1)

def distance(city1, city2):
return math.sqrt((city1[0]-city2[0])**2 + (city1[1]-city2[1])**2)

def path_length(path):
length = 0
for i in range(len(path)-1):
length += distance(city_pos[path[i]-1], city_pos[path[i+1]-1])
length += distance(city_pos[path[-1]-1], city_pos[path[0]-1])
return length

def initial_solution():
unvisited_cities = list(range(1, len(city)+1))
current_city = random.choice(unvisited_cities)
solution = [current_city]
unvisited_cities.remove(current_city)
while unvisited_cities:
next_city = min(unvisited_cities, key=lambda city: distance(city_pos[current_city-1], city_pos[city-1]))
unvisited_cities.remove(next_city)
solution.append(next_city)
current_city = next_city
return solution

def two_opt_swap(path, i, k):
new_path = path[:i] + path[i:k + 1][::-1] + path[k + 1:]
return new_path

def simulated_annealing(path):
df = readcity(path)

city = np.array(range(1,len(df[0][0:len(df)-1])+1))
city_x = np.array(df[1][0:len(df)-1])
city_y = np.array(df[2][0:len(df)-1])
city_pos = np.stack((city_x, city_y), axis=1)

T = 1000 # 初始温度
Tmin = 1 # 终止温度
alpha = 0.95 # 降温速率
path = initial_solution() # 初始化路径
best_path = copy.deepcopy(path) # 最优路径
best_length = path_length(best_path) # 最优路径长度
length_list = [best_length] # 记录每个温度下的路径长度
iter_num = 0 # 迭代次数

while T > Tmin:
i = random.randint(0, len(city)-1)
k = random.randint(0, len(city)-1)
new_path = two_opt_swap(path, i, k) # 产生新路径
new_length = path_length(new_path) # 计算新路径长度
delta = new_length - best_length # 计算路径长度差

if delta < 0:
path = copy.deepcopy(new_path)
best_path = copy.deepcopy(new_path)
best_length = new_length
else:
p = math.exp(-delta/T) # 计算概率
if random.random() < p: # 根据概率接受新解
path = copy.deepcopy(new_path)

length_list.append(best_length)
T *= alpha # 降温

iter_num += 1

print("初始解路径：", initial_solution())
print("初始解路径长度：", path_length(initial_solution()))
print("最优解路径：", best_path)
print("最优解路径长度：", best_length)
print("迭代次数：", iter_num)
plt.plot(range(len(length_list)), length_list)
plt.title("Simulated Annealing")
plt.xlabel("Iteration")
plt.ylabel("Length")
plt.show()

simulated_annealing(path)