请在上面的代码的基础上修改实现以2-opt法进行构造邻域、Metropolis准则接受内循环的解以实现等温过程、输出初始解的解值和迭代次数的功能
时间: 2024-02-28 15:57:13 浏览: 108
以下是修改后的代码:
```python
import numpy as np
import pandas as pd
import math
import random
import matplotlib.pyplot as plt
# 读取数据
df = pd.read_csv("data.tsp", sep=" ", skiprows=6, header=None)
city = np.array(range(1, len(df)+1))
city_x = np.array(df[1])
city_y = np.array(df[2])
# 计算两点之间的距离
def distance(city_x, city_y, i, j):
return math.sqrt((city_x[i]-city_x[j])**2 + (city_y[i]-city_y[j])**2)
# 计算路径长度
def path_length(city_x, city_y, path):
length = 0
for i in range(len(path)-1):
length += distance(city_x, city_y, path[i], path[i+1])
length += distance(city_x, city_y, path[len(path)-1], path[0])
return length
# 2-opt邻域搜索
def two_opt(path):
best_path = path
best_length = path_length(city_x, city_y, path)
for i in range(1, len(path)-2):
for j in range(i+1, len(path)-1):
new_path = np.concatenate((path[:i], np.flip(path[i:j+1]), path[j+1:]))
new_length = path_length(city_x, city_y, new_path)
if new_length < best_length:
best_path = new_path
best_length = new_length
return best_path, best_length
# 初始解
path = np.concatenate(([1], np.random.permutation(city[1:]), [1]))
initial_length = path_length(city_x, city_y, path)
print("Initial path length: ", initial_length)
# 初始温度、终止温度、温度衰减率、迭代次数
T0 = 100
T_end = 1e-3
alpha = 0.99
iter_num = 10000
# 记录搜索过程中最优解和对应的路径长度
best_path = path
best_length = path_length(city_x, city_y, path)
length_list = [best_length]
# 模拟退火算法
T = T0
iter_count = 0
while T > T_end and iter_count < iter_num:
new_path, new_length = two_opt(path)
delta = new_length - best_length
if delta < 0 or math.exp(-delta/T) > random.uniform(0, 1):
path = new_path
best_length = new_length
if new_length < length_list[-1]:
best_path = new_path
length_list.append(new_length)
T *= alpha
iter_count += 1
# 打印最优路径长度和路径
print("Best path length: ", best_length)
print("Best path: ", best_path)
print("Number of iterations: ", iter_count)
# 可视化最优路径
plt.plot(city_x[best_path], city_y[best_path], 'o-')
plt.title("TSP Solution with Simulated Annealing and 2-opt")
plt.show()
```
在修改后的代码中,我们首先添加了一个 `two_opt` 函数来实现2-opt邻域搜索。然后,我们在主函数中调用 `two_opt` 函数来搜索邻域中的最优解,然后根据Metropolis准则来决定是否接受新的解。同时,我们还添加了输出初始解的解值和迭代次数的功能。
阅读全文